Bogenzusammenhang

Der Bogenzusammenhang ist ein Grundbegriff der Graphentheorie und eine Verallgemeinerung des Zusammenhangs für gerichtete Graphen (Digraphen). Anschaulich ist der Bogenzusammenhang ein Maß dafür, wie schwer es ist, einen Digraphen durch Löschen von gerichteten Kanten in zwei oder mehr Komponenten zu zerlegen. Ist der Bogenzusammenhang groß, so müssen viele gerichtete Kanten entfernt werden.

Definition

Ein gerichteter Graph $D=(V,A)$, der stark zusammenhängend ist, heißt k-fach bogenzusammenhängend oder k-bogenzusammenhängend, wenn der Graph $D':=(V,A\setminus U)$ für alle Kantenmengen $U$ der Mächtigkeit $k-1$ stark zusammenhängend ist.

Das größte $k$, so dass $D$ k-fach bogenzusammenhängend ist, heißt Bogenzusammenhangszahl und wird mit $\lambda (D)$ bezeichnet.

Ist $D$ trivial oder nicht stark zusammenhängend, so nennt man ihn 0-fach bogenzusammenhängend und setzt $\lambda (D)=0$

Beispiel

Der Beispielgraph ist ein Turniergraph

Betrachte als Beispiel den rechts abgebildeten gerichteten Graphen. Dieser ist nicht trivial und stark zusammenhängend, also ist der Graph auf jeden Fall 1-bogenzusammenhängend. Beginnt man mit dem Löschen von einelementigen Kantenmengen (z. B. der Kante $(4,3)$), so wird der starke Zusammenhang zerstört (Nach dem Löschen der Kante kann der Knoten 1 nicht mehr vom Knoten 4 aus erreicht werden). Demnach ist der Graph nicht 2-bogenzusammenhängend und es ist $\lambda (D)=1$, da der Graph 0-bogenzusammenhängend und 1-bogenzusammenhängend ist.

Algorithmen

Zur Bestimmung der Bogenzusammenhangszahl gibt es polynomielle Algorithmen. Dazu kann man beispielsweise Flussalgorithmen verwenden. Ist als $F(n,m)$ der Aufwand, einen minimalen Schnitt im Graphen bestimmen, so hat dieser naive Ansatz immerhin einen Aufwand von ${\mathcal {O}}(nF(n,m))$. Es gibt noch deutlich effizientere, aber auch kompliziertere Algorithmen.

Verwandte Begriffsbildungen

Ein Analogon des Bogenzusammenhangs für ungerichtete Graphen ist der Kantenzusammenhang. Hier werden ungerichtete Kanten entfernt, bis der Graph in seine Zusammenhangskomponenten zerfällt. Des Weiteren gibt es den Begriff des k-Zusammenhangs, welcher ein Maß dafür ist, wie viele Ecken aus einem Graphen entfernt werden müssen, damit er in seine Komponenten zerfällt.

Literatur

• Lutz Volkmann: Fundamente der Graphentheorie, Springer (Wien) 1996, ISBN 3-211-82774-9 (neuere, Online-Version "Graphen an allen Ecken und Kanten"; PDF; 3,7 MB)
• Alexander Schrijver: Combinatorial optimization. polyhedra and efficiency. Springer, Berlin 2003, ISBN 978-3-540-44389-6 (3 Bände, 1881 Seiten).