Silně souvislá komponenta

Graf s vyznačenými kvazikomponentami

Silně souvislá komponenta 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í:

  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'.
Jiné Jazyky