Silně souvislá komponenta

Technology

12 hours ago

Author

Graf s vyznačenými kvazikomponentami

Silně souvislá komponenta (též kvazikomponenta) je takový maximální podgraf orientovaného grafu, v němž pro každou dvojici vrcholů u, v existuje sled.

Definice

Nechť G = (V, E) je orientovaný graf. Podgraf G' grafu G se nazývá silně souvislá komponenta (SSK) grafu G, pokud platí: # G' je silně souvislý. +more # G' je maximální, tj. neexistuje žádný silně souvislý podgraf G" různý od G', který by obsahoval podgraf G'.

Vlastnosti

SSK grafu GT (transponovaný graf ke G) jsou transponované SSK grafu G * SSK lze hledat pomocí algoritmu prohledávání do hloubky * Množiny vrcholů indukující SSK tvoří rozklad množiny vrcholů V celého grafu. To znamená, že každý vrchol se nachází v právě jedné komponentě silné souvislosti. +more * Pokud kontrahujeme hrany v jednotlivých SSK, dostaneme kondenzaci grafu. Její výsledek je vždy acyklický graf.