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

Bearbeiten

Ein gerichteter Graph  , der stark zusammenhängend ist, heißt k-fach bogenzusammenhängend oder k-bogenzusammenhängend, wenn der Graph   für alle Kantenmengen   der Mächtigkeit   stark zusammenhängend ist.

Das größte  , so dass   k-fach bogenzusammenhängend ist, heißt Bogenzusammenhangszahl und wird mit   bezeichnet.

Ist   trivial oder nicht stark zusammenhängend, so nennt man ihn 0-fach bogenzusammenhängend und setzt  

Beispiel

Bearbeiten
 
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  ), 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  , da der Graph 0-bogenzusammenhängend und 1-bogenzusammenhängend ist.

Algorithmen

Bearbeiten

Zur Bestimmung der Bogenzusammenhangszahl gibt es polynomielle Algorithmen. Dazu kann man beispielsweise Flussalgorithmen verwenden. Ist als   der Aufwand, einen minimalen Schnitt im Graphen bestimmen, so hat dieser naive Ansatz immerhin einen Aufwand von  . Es gibt noch deutlich effizientere, aber auch kompliziertere Algorithmen.

Verwandte Begriffsbildungen

Bearbeiten

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

Bearbeiten