Zusammenhang (Graphentheorie)
Definitionen
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 gibt, mit v als Startknoten und w als Endknoten. Falls G nicht zusammenhängend ist, nennt man G unzusammenhängend.
Ein induzierter Teilgraph K=(VK,EK) von G heißt Zusammenhangskomponente von G, falls K zusammenhängend ist und in G kein Knoten aus VK mit einem Knoten aus der Differenzmenge V-VK benachbart ist.
G heißt k-fach kantenzusammenhängend, wenn man k-1 Kanten aus G entfernen kann (in Multigraphen kann man Kanten entsprechend ihrer Vielfachheit mehrfach entfernen) und der resultierende Graph zusammenhängend ist. Als Kantenenzusammenhangszahl eines Graphen G bezeichnet man das größte k, sodass G k-fach kantenzusammenhängend ist.
G heißt k-fach knotenzusammenhängend, wenn man die Knoten einer beliebigen höchstens k-1-elementigen Teilmenge von V aus G sowie deren inzidenten Kanten entfernen kann und der resultierende Graph zusammenhängend ist. Als Knotenzusammenhangszahl eines Graphen G bezeichnet man das größte k, sodass G k-fach knotenzusammenhängend ist.
Ein gerichteter Graph G=(V,E) heißt zusammenhängend von einem Knoten v aus, falls es zu jedem Knoten w aus V einen gerichteten Weg in G gibt, mit v als Startknoten und w als Endknoten. Falls G nicht von v aus zusammenhängend ist, nennt man G unzusammenhängend von v aus. G heißt stark zusammenhängend, falls G von jedem Knoten v aus V zusammenhängend ist.
Ein induzierter Teilgraph K=(VK,EK) von G heißt starke Zusammenhangskomponente von G, falls K stark zusammenhängend ist und in G kein Knoten aus VK Vorgänger oder Nachfolger von einem Knoten aus der Differenzmenge V-VK ist.
Bemerkung: Es gibt genau dann einen Weg mit v als Startknoten und w als Endknoten, wenn es einen Pfad mit v als Startknoten und w als Endknoten gibt. In obigen Definitionen kann man Weg also auch durch Pfad ersetzen.
Beispiele
kommen noch.