Silně souvislá komponenta

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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.

Definice[editovat | editovat zdroj]

Nechť G = (V, E) je orientovaný graf. Podgraf G' grafu G se nazývá silně souvislá komponenta (SSK) grafu G, pokud platí:

  1. G' je silně souvislý.
  2. G' je maximální, tj. neexistuje žádný silně souvislý podgraf G" různý od G', který by obsahoval podgraf G'.

Vlastnosti[editovat | editovat zdroj]

  • 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.
  • Pokud kontrahujeme hrany v jednotlivých SSK, dostaneme kondenzaci grafu. Její výsledek je vždy acyklický graf.
Graf s vyznačenými silně souvislými komponentami