Zusammenhang (Graphentheorie)

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Starke Zusammenhangskomponente)
Wechseln zu: Navigation, Suche
Ein zusammenhängender Graph: Je zwei Knoten lassen sich durch eine Kantenfolge verbinden. Exemplarisch ist eine Kantenfolge zwischen den Knoten v und w rot hervorgehoben.

Der Zusammenhang ist ein mathematischer Begriff aus der Graphentheorie. Ein Graph heißt zusammenhängend, wenn je zwei Knoten durch eine Kantenfolge des Graphen verbunden werden können.

Definition[Bearbeiten]

Ungerichtete Graphen[Bearbeiten]

Dieser unzusammenhängende Graph hat zwei Komponenten, die Knoten v und w können nicht verbunden werden.

Ein ungerichteter Graph G=(V,E) heißt zusammenhängend, falls es zu je zwei beliebigen Knoten v und w aus V einen ungerichteten Weg in G mit v als Startknoten und w als Endknoten gibt. Einen maximalen zusammenhängenden Teilgraphen von G nennt man eine Komponente oder Zusammenhangskomponente. Falls G nicht zusammenhängend ist zerfällt der Graph in seine Zusammenhangskomponenten.

Gerichtete Graphen[Bearbeiten]

Ein gerichteter Graph G=(V,E) heißt (stark) zusammenhängend von einem Knoten v aus, falls es zu jedem Knoten w aus V einen gerichteten Weg in G mit v als Startknoten und w als Endknoten gibt. G heißt stark zusammenhängend, falls G von jedem Knoten aus stark zusammenhängend ist.

Ein gerichteter Graph heißt (schwach) zusammenhängend, falls der zugehörige ungerichtete Graph (also der Graph, der entsteht, wenn man jede gerichtete Kante durch eine ungerichtete Kante ersetzt) zusammenhängend ist.

Ein induzierter Teilgraph G[U] für eine Teilmenge U\subset V heißt starke Zusammenhangskomponente von G, falls G[U] stark zusammenhängend ist und kein stark zusammenhängender induzierter Teilgraph von G existiert, der G[U] echt enthält.

Wichtige Aussagen und Sätze[Bearbeiten]

Relativ leicht zeigt man folgende Aussagen:

  1. Jeder zusammenhängende ungerichtete Graph mit n Knoten enthält mindestens n-1 Kanten.
  2. Jeder stark zusammenhängende gerichtete Graph mit n Knoten enthält mindestens n Kanten.
  3. Ein ungerichteter Graph ist genau dann zusammenhängend, wenn er einen Spannbaum enthält.
  4. Ein gerichteter Graph ist genau dann stark zusammenhängend, wenn seine Adjazenzmatrix irreduzibel ist. Damit ist auch ein ungerichteter Graph genau dann zusammenhängend, wenn seine Adjazenzmatrix irreduzibel ist.

Wichtige Algorithmen[Bearbeiten]

Mittels Tiefensuche lässt sich leicht ein linearer Algorithmus implementieren, der die Zusammenhangskomponenten eines Graphen berechnet und so einen einfachen Test impliziert, ob der Graph zusammenhängend ist. Der Test, ob ein gerichteter Graph von einem Knoten v aus zusammenhängend ist, funktioniert analog. Von Tarjan (1972) stammt ein linearer Algorithmus zur Bestimmung starker Zusammenhangskomponenten, der ebenfalls auf Tiefensuche basiert und in gerichteten Graphen die starken Zusammenhangskomponenten und leicht modifiziert in ungerichteten Graphen die Blöcke und Artikulationen berechnet.

Verallgemeinerungen[Bearbeiten]

Eine wesentliche Verallgemeinerung des Begriffs stellt der Begriff des k-fachen Knotenzusammenhangs , der Kantenzusammenhang und der Bogenzusammenhang dar.

Literatur[Bearbeiten]

Weblinks[Bearbeiten]