Eine Brücke (englisch bridge, auch cut-edge oder Schneidekante) ist in einem ungerichteten Graphen eine Kante, deren Entfernung den Graphen in zwei Teile zerlegt: Aus einer Zusammenhangskomponente werden zwei. Fällt eine Brücke aus, ist das Netzwerk nicht mehr zusammenhängend — es gibt dann Knotenpaare, zwischen denen kein Weg mehr existiert.
Woran erkennt man eine Brücke?
Eine Kante ist genau dann eine Brücke, wenn sie in keinem Kreis liegt. Liegt eine Kante auf einem Kreis, gibt es immer einen zweiten Weg zwischen ihren Endknoten — sie kann keine Brücke sein. Daraus folgen praktische Beobachtungen:
- In einem Baum ist jede Kante eine Brücke, denn ein Baum enthält per Definition keine Kreise.
- Eine Kante ist genau dann eine Brücke, wenn sie in jedem Spannbaum vorkommt.
- Ein Graph ohne Brücken heißt 2-kantenzusammenhängend (bridgeless): Selbst nach dem Ausfall einer beliebigen Kante bleibt alles verbunden.
Berechnung: der Tarjan-Algorithmus
Brücken findet man in Linearzeit mit einer Tiefensuche. Der Algorithmus von Robert Tarjan (1974) vergibt dabei für jeden Knoten eine Entdeckungszeit tin[v] und berechnet den Lowlink-Wert low[v]: die kleinste Entdeckungszeit, die man von v aus über Baumkanten und genau eine Rückwärtskante erreichen kann.
Zu Beginn: low[v] = tin[v]
Beim Rückkehren: low[v] = min(low[v], low[to])
Rückwärtskante: low[v] = min(low[v], tin[to])Eine Baumkante (v, to) ist genau dann eine Brücke, wenn low[to] > tin[v] gilt — von to aus führt also kein Umweg zurück zu v oder zu einem Vorfahren von v. Die Laufzeit ist O(V + E).
Brückenbaum und Redundanz
Kondensiert man alle 2-kantenzusammenhängenden Komponenten eines Graphen zu je einem Knoten und verbindet sie über die Brücken, erhält man einen Baum — den Brückenbaum (bridge tree). Er zeigt auf einen Blick, welche Verbindungen kritisch sind und wo Redundanz fehlt.
- Netzwerke: Ein ausgefallenes Kabel zwischen zwei Gebäuden trennt alle dahinter liegenden Geräte — die Kante ist eine Brücke.
- Verkehr: Eine gesperrte Flussbrücke zerlegt ein Straßennetz, wenn es keine Ausweichroute gibt.
- Stromnetze: Eine einzelne Leitung, die ein Umspannwerk versorgt, ist eine Brücke im Versorgungsgraphen.
Der Name stammt vom berühmten Königsberger Brückenproblem, mit dem Leonhard Euler 1736 die Graphentheorie begründete: Er untersuchte, ob sich alle Brücken der Stadt genau einmal überqueren lassen. Das heutige Konzept der „Brücke“ als kritische Kante setzt diese Idee fort — eine Brücke ist die Verbindung, deren Verlust alles trennt.
Verwandte Grundlagen: Knoten, Ungerichteter Graph, Artikulationspunkt (das Knoten-Pendant), Starke Zusammenhangskomponenten (gerichtete Erreichbarkeit).