Zusammenhang

Einfache Sprache

Ein Graph heißt zusammenhängend, wenn alle seine Knoten untereinander durch Kantenfolgen verbunden sind.

Def. Zusammenhang (Graphentheorie)

Ein Ungerichteter Graph heißt zusammenhängend, wenn es zwischen beliebige Knoten $v,w\in V$ einen ungerichteten Weg in $G$ gibt, der $v$ als Startknoten und $w$ als Endknoten hat. Ein Gerichteter Graph heißt zusammenhängend von einem Knoten $v$ aus, falls zu jedem Knoten $w\in V$ ein gerichteter Weg in $G$ von $v$ nach $w$ gibt. Ein Gerichteter Graph heißt stark zusammenhängend, falls zwischen beliebigen Knoten $v,w\in V$ es einen gerichteter Weg in $G$ von $v$ nach $w$ und von $w$ nach $v$ gibt.

Ein Zusammenhangskomponente bezeichnet einen maximal zusammenhängenden Teilgraph.

Die Verallgemeinerung des Zusammenhangs ist der k-Zusammenhang.