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:
Den Beweis der Korrektheit des Verfahrens liefert die folgende Behauptung:
![]() |
v,w in einer sZHK von G . |
![]() |
|
![]() |
|
![]() |
|
![]() |
|
![]() |
Sei x die Wurzel des Tiefensuchebaums, der v und w enthält. |
![]() |
|
![]() |
|
![]() |
|
Analog: ![]() ![]() |