Zusammenhang (Graphentheorie)
Dies ist ein momentan alternativer Artikel zu Zusammenhang von Graphen!
| Table of contents |
|
2 Mehrfacher Zusammenhang 3 Zusammenhang in Gerichteten Graphen 4 Trennung 5 Eigenschaften Zusammenhängender Graphen 6 Algorithmen |
Definition
Ein Graph heißt zusammenhängend, wenn es zwischen je zwei Knoten immer einen Pfad gibt.
Ist ein Graph nicht zusammenhängend (unzusammenhängend), so zerfällt er in mehrere Zusammenhangskomponenten, das sind nicht-maximierbare, zusammenhängende Teilgraphen.
Die Kantenzusammenhangszahl eines Graphen bezeichnet die
größte Zahl k, so dass der Graph k-fach zusammenhängend
Analog dazu sind k-fach knotenzusammenhängend
(zusammenhängend nach Entfernen von k-1 beliebigen Knoten)
und die Knotenzusammenhangszahl definiert.
A-B-Trenner, k-Zusammenhangskomponente, Block,
Blockstruktur, Artikulation, Brücke
Der Test, ob ein gerichteter Graph von einem Knoten v aus zusammenhängend ist, funktioniert analog.
Von Tarjan (1972) stammt ein linearer Algorithmus, der ebenfalls auf Tiefensuche basiert und in gerichteten Graphen die starken Zusammenhangskomponenten und leicht modifiziert in ungerichteten Graphen die Blöcke und Artikulationen berechnet.
Zur Berechnung von Knoten- und Kantenzusammenhangszahl gibt es polynomielle Algorithmen. Dazu kann man beispielsweise Flussalgorithmen verwenden. Allerdings gibt es auch effizientere Algorithmen.Mehrfacher Zusammenhang
Ein Graph heißt k-fach kantenzusammenhängend, falls er nach Entfernen
von k-1 beliebigen Kanten noch immer zusammenhängend ist.Zusammenhang in Gerichteten Graphen
TODOTrennung
TODO: Erkläre die BegriffeEigenschaften Zusammenhängender Graphen
TODO wichtige Aussagen und SätzeAlgorithmen
Mittels Tiefensuche oder Breitensuche lässt sich ein
linearer Algorithmus implementieren, der die
Zusammenhangskomponenten eines Graphen berechnet
und so auf einfachen Zusammenhang testet.
