6.2 Strenge Zusammenhangskomponenten

Eine strenge Zusammenhangskomponente (sZHK) ist ein maximaler Teilgraph, in dem je zwei Knoten durch gerichtete Wege verbunden sind.

Ein Algorithmus zur Bestimmung der sZHK in G = (V,E) sieht folgendermaßen aus:

1.: Führe eine Tiefensuche in G durch, wobei die Id eines Knotens vor dem Ende seiner Rekursion vergeben wird (nicht - wie ursprünglich - am Anfang).
2.: Bilde G' durch Umkehrung aller Kanten des Graphen G .
3.: Führe nun eine Tiefensuche in G' durch, wobei man jeweils mit den höchsten Ids aus Phase 1.) beginnt.
4.: Die Tiefensuchebäume aus Phase 3.) sind dann die sZHK vom Graphen G .

Den Beweis der Korrektheit des Verfahrens liefert die folgende Behauptung:

v,w in einer sZHK von G $\iff$ v,w in einem Tiefensuchebaum von G' .

$\Rightarrow$ :	v,w in einer sZHK von G .
	$\Rightarrow$ Es existiert ein Weg von v nach w und ein Weg von w nach v in G .
	$\Rightarrow$ Es existiert ein Weg von v nach w und ein Weg von w nach v in G' .
	$\Rightarrow$ Bei Besuch von v wird auch w erreicht und umgekehrt.
	$\Rightarrow$ v und w liegen in einem Tiefensuchebaum von G' .
$\Leftarrow$ :	Sei x die Wurzel des Tiefensuchebaums, der v und w enthält.
	$\Rightarrow$ Es existiert ein Weg von v nach x und ein Weg von w nach x in G . Wegen des Weges von v nach x kann v erst nach x besucht worden sein.
	$\Rightarrow$ v wurde während der Bearbeitung von x besucht.
	$\Rightarrow$ Es existiert ein Weg von x nach v in G .
	Analog: $\exists$ Weg von x nach w in G $\iff$ v und w sind in einer sZHK.