Zusammenhang (Graphentheorie)

aus Wikipedia, der freien Enzyklopädie
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 die Knoten paarweise durch eine Kantenfolge des Graphen verbunden sind.

Definition[Bearbeiten | Quelltext bearbeiten]

Ungerichtete Graphen[Bearbeiten | Quelltext bearbeiten]

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

Ein ungerichteter Graph heißt zusammenhängend, falls es zu je zwei beliebigen Knoten und aus einen ungerichteten Weg in mit als Startknoten und als Endknoten gibt.

Einen maximalen zusammenhängenden Teilgraphen eines beliebigen Graphen nennt man eine Komponente oder Zusammenhangskomponente. Ein nicht zusammenhängender Graph zerfällt in seine Zusammenhangskomponenten.

Gerichtete Graphen[Bearbeiten | Quelltext bearbeiten]

Ein gerichteter Graph heißt (stark) zusammenhängend von einem Knoten aus, falls es zu jedem Knoten aus einen gerichteten Weg in von nach gibt. heißt stark zusammenhängend, falls 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 für eine Teilmenge heißt starke Zusammenhangskomponente von , falls stark zusammenhängend ist und nicht zu einem größeren stark zusammenhängenden Teilgraphen von erweitert werden kann.

Wichtige Aussagen und Sätze[Bearbeiten | Quelltext bearbeiten]

Relativ leicht zeigt man folgende Aussagen:

  1. Jeder zusammenhängende ungerichtete Graph mit Knoten enthält mindestens Kanten.
  2. Jeder stark zusammenhängende gerichtete Graph mit Knoten enthält mindestens 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 | Quelltext 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. Siehe auch Union Find Algorithmus.

Verallgemeinerungen[Bearbeiten | Quelltext bearbeiten]

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

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]