Zusammenhang, Komponenten

Def. Relation $\sim_{G}^{}$ durch

x $\sim_{G}^{}$ y$\iff$$\exists$Weg von $x$ nach $y$ in G.

Satz: $\sim_{G}^{}$ ist Äquivalenzrelation.

(reflexiv, symmetrisch, transitiv)

Def: die Äquivalenzklassen heißen Zusammenhangskomponenten.

Def: wenn $\sim_{G}^{}$ nur eine Äquivalenzklasse erzeugt, dann heißt G zusammenhängend.

Aufgabe: für jeden Graphen G gilt: G ist zusammenhängend oder $\overline{G}$ ist zusammenhängend.