Silně souvislá komponenta
Z Wikipedie, otevřené encyklopedie
Silně souvislá komponenta je takový maximální podgraf orientovaného grafu, v němž pro všechny dvojice vrcholů u, v existuje cesta z u do v a zároveň z v do u.
[editovat] 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ý.
- G' je maximální, tj. neexistuje žádný silně souvislý podgraf G" různý od G', který by obsahoval podgraf G'.
[editovat] Vlastnosti
- SSK grafu GT (transponovaný graf ke G) jsou transponované SSK grafu G
- SSK lze hledat pomocí algoritmu DFS

