Kantenzusammenhang

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Der Kantenzusammenhang eines Graphen ist ein wichtiger Begriff in der Graphentheorie und eine Verallgemeinerung des Zusammenhangs. Anschaulich ist der Kantenzusammenhang ein Maß dafür, wie schwer es ist, einen Graphen durch Löschen von Kanten in 2 Komponenten zu zerlegen. Ist der Kantenzusammenhang groß, so müssen viele Kanten gelöscht werden.

Definition[Bearbeiten]

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

Beispiel[Bearbeiten]

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  \lambda (G)=2 . In diesem Fall stimmt die Kantenzusammenhangszahl also mit dem Minimalgrad des Graphen überein.

Eigenschaften[Bearbeiten]

Verwandte Begriffsbildungen[Bearbeiten]

Der k-Zusammenhang ist ein zum Kantenzusammenhang ähnlicher Begriff, bloß dass nur Trenner mit leerer Kantenmenge und eine beliebigen Knotenmenge betrachtet werden. Der k-Zusammenhang gibt also ein Maß dafür an, wie viele Knoten aus einem Graphen entfernt werden müssen, so dass dieser in verschiedene Komponenten zerfällt. Ein zum Kantenzusammenhang ähnlicher Begriff für gerichtete Graphen ist der Bogenzusammenhang

Literatur[Bearbeiten]