Definujte slabou souvislost a silnou souvislost orientovného grafu

→ pojmy souvislost a souvislá komponenta neorientovaných grafů nejdou jednoduše použít pro orientované grafy

Slabé a silné souvislosti rozdělujeme u orientovaného grafu

Symetrizace

• symetrizace orientovaného grafu G = (V,E) je neorientovaný graf sym(G) = (V,E’)

→ kde {u, v} ∈ E′ právě tehdy, když (u, v) ∈ E nebo (v, u) ∈ E

ℹ️ symetrizace tedy odstraní z grafu informace o orientaci hran ℹ️

Slabá souvislost

• Orientovaný graf G = (V,E) nazveme slabě souvislý, pokud je souvislá jeho symetrizace sym(G)

→ testovat slabou souvislost tedy znamená testovat souvislost neorientovaného grafu