Wege, Zusammenhang

Eine Folge (x₀, x₁,..., x_n) von Knoten heißt Weg (zwischen x₀ und x_n), falls

• für 0$\le$i < n : x_ix_{i + 1} $\in$ E(G),
• x₀, x₁,..., x_{n - 1} paarweise verschieden sind

(für ungerichtete Graphen)

Die Relation x $\sim_{G}^{}$ y falls es in G einen Weg zwischen x und y gibt, ist eine Äquivalenzrelation auf V(G).

Die Äquivalenzklassen von $\sim_{G}^{}$ heißen Zusammenhangskomponenten.

Ein Graph heißt zusammenhängend, wenn er nur eine Zusammenhangskomponente besitzt.