Kantenzusammenhang

Der Kantenzusammenhang e​ines Graphen i​st ein wichtiger Begriff i​n der Graphentheorie u​nd eine Verallgemeinerung d​es Zusammenhangs. Anschaulich i​st der Kantenzusammenhang e​in Maß dafür, w​ie schwer e​s ist, e​inen Graphen d​urch Löschen v​on Kanten i​n 2 Komponenten z​u zerlegen. Ist d​er Kantenzusammenhang groß, s​o müssen v​iele Kanten gelöscht werden.

Definition

Ein einfacher Graph ${\displaystyle G=(V,E)}$ heißt k-fach kantenzusammenhängend, wenn es keinen Trenner ${\displaystyle Z=(X,Y)}$ mit maximal ${\displaystyle (k-1)}$-elementiger Kantenmenge ${\displaystyle Y}$ und leerer Knotenmenge ${\displaystyle X=\emptyset }$ in ${\displaystyle G}$ gibt (in Multigraphen kann man Kanten entsprechend ihrer Vielfachheit mehrfach entfernen). Äquivalent dazu ist, dass ${\displaystyle G'=(V,E\backslash U)}$ für alle Kantenmengen der Mächtigkeit ${\displaystyle k-1}$ zusammenhängend ist. Als Kantenzusammenhangszahl ${\displaystyle \lambda (G)}$ eines Graphen ${\displaystyle G}$ bezeichnet man das größte ${\displaystyle k}$, sodass ${\displaystyle G}$ ${\displaystyle k}$-fach kantenzusammenhängend ist. Äquivalent dazu ist, dass die Kantenzusammenhangszahl die kleinste Mächtigkeit eines Trenners von ${\displaystyle G}$ mit leerer Knotenmenge ist.

Beispiel

Das ist das Haus vom Nikolaus

Betrachte als Beispiel das rechts dargestellte Haus vom Nikolaus. Es ist 2-kantenzusammenhängend, da keine Trenner existieren, die nur aus einer Kante bestehen. Äquivalent dazu ist, dass keine Brücke existiert. Betrachtet man aber nun z. B. den Knoten 5, so zerfällt der Graph beim Löschen der beiden zum Knoten 5 inzidenten Kanten in 2 Zusammenhangskomponenten: den Knoten 5 selbst und alle anderen Knoten. Das Haus ist also 1-fach und 2-fach kantenzusammenhängend und seine Kantenzusammenhangszahl ist ${\displaystyle \lambda (G)=2}$. In diesem Fall stimmt die Kantenzusammenhangszahl also mit dem Minimalgrad des Graphen überein.

Eigenschaften

• 

  Ein 2-kantenzusammenhängender Graph
  Ist ${\displaystyle |G|\geq 2}$, so gilt ${\displaystyle \delta (G)\geq \lambda (G)\geq \kappa (G)}$, wobei ${\displaystyle \kappa (G)}$ die Knotenzusammenhangszahl und ${\displaystyle \delta (G)}$ der Minimalgrad des Graphen ${\displaystyle G}$ ist.
• ${\displaystyle G}$ ist genau dann 2-fach kantenzusammenhängend, wenn ${\displaystyle G}$ keine Brücke enthält.
• ${\displaystyle G}$ ist genau dann ${\displaystyle k}$-fach kantenzusammenhängend, wenn ${\displaystyle G}$ zwischen je zwei Ecken ${\displaystyle k}$ kantendisjunkte Wege enthält. Diese Aussage ist auch als die globale Version des Satzes von Menger bekannt.

Verwandte Begriffe

Der k-Zusammenhang i​st ein z​um Kantenzusammenhang ähnlicher Begriff, bloß d​ass nur Trenner m​it leerer Kantenmenge u​nd eine beliebige Knotenmenge betrachtet werden. Der k-Zusammenhang g​ibt also e​in Maß dafür an, w​ie viele Knoten a​us einem Graphen entfernt werden müssen, s​o dass dieser i​n verschiedene Komponenten zerfällt. Ein z​um Kantenzusammenhang ähnlicher Begriff für gerichtete Graphen i​st der Bogenzusammenhang.

Algorithmen

Es gibt einen Algorithmus, der in polynomieller Laufzeit das größte ${\displaystyle k}$ bestimmt, für das ein Graph ${\displaystyle k}$-kantenzusammenhängend ist. Ein einfacher Algorithmus würde für jedes Paar ${\displaystyle (u,v)}$ von Knoten den maximalen Fluss von ${\displaystyle u}$ nach ${\displaystyle v}$ bestimmen, wobei die Kapazität aller Kanten des Graphen für beide Richtungen auf 1 gesetzt wird. Ein Graph ist genau dann ${\displaystyle k}$-kantenzusammenhängend, wenn der maximale Fluss von ${\displaystyle u}$ nach ${\displaystyle v}$ für jedes Paar ${\displaystyle (u,v)}$ mindestens ${\displaystyle k}$ beträgt, also ist ${\displaystyle k}$ der minimale ${\displaystyle u}$-${\displaystyle v}$-Fluss unter allen Knotenpaaren ${\displaystyle (u,v)}$.

Wenn ${\displaystyle n}$ die Anzahl der Knoten des Graphen ist, würde dieser einfache Algorithmus ${\displaystyle O(n^{2})}$ Iterationen des Problems des maximalen Flusses Maximum-Flow-Problems ausführen, das in der Laufzeit ${\displaystyle O(n^{3})}$ gelöst werden kann. Daher ist die Komplexität des oben beschriebenen einfachen Algorithmus insgesamt ${\displaystyle O(n^{5})}$.

Ein verbesserter Algorithmus löst das Problem des maximalen Flusses für jedes Paar ${\displaystyle (u,v)}$, wobei ${\displaystyle u}$ willkürlich festgelegt ist, während ${\displaystyle v}$ über alle Knoten variiert. Dies reduziert die Komplexität auf ${\displaystyle O(n^{4})}$. Es kann durch einen Algorithmus von Gabow weiter verbessert werden, der im Worst Case die Laufzeit ${\displaystyle O(n^{3})}$ hat.[1]

Die Karger-Stein-Variante des Algorithmus von Karger bietet einen schnelleren randomisierten Algorithmus zur Bestimmung der Zusammenhangs des Graphen mit der erwarteten Laufzeit ${\displaystyle O(n^{2}\cdot \log ^{3}(n))}$.[2]

Das verwandte Problem, einen minimalen ${\displaystyle k}$-kantenzusammenhängenden spannenden Teilgraphen eines Graphen zu finden, ist NP-schwer für ${\displaystyle k\geq 2}$. Dabei muss der Teilgraph alle Knoten, aber möglichst wenige Kanten enthalten, sodass er nach dem entfernen von ${\displaystyle k-1}$ Kanten immer noch zusammenhängend ist.[3]

Literatur

• Reinhard Diestel: Graphentheorie. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 Seiten).

Einzelnachweise

1. Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci., 50(2):259–273, 1995.
2. David R. Karger, Clifford Stein: A new approach to the minimum cut problem. In: Journal of the ACM. 43, Nr. 4, 1996, S. 601. doi:10.1145/234533.234534.
3. M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979.