Motivace: V jednom (raději) nejmenovaném městě, se starosta rozhodl, že ze všech ulic udělá jednosměrky. Odůvodnil to vznikem většího počtu parkovacích míst. Po jisté době se ale začalo proslýchat, že se z určitých míst nedá dojet do jiných míst ve městě jinak, něž porušením předpisů. Pokud by se to prokázalo, tak by s toho mohl mít starosta průšvih. Rád by to zkontroloval a případně napravil. Protože se rychle blíží volební období, tak už není moc času a nemůžete použít jiný algoritmus, než s lineární časovou složitostí. Znáte vhodný algoritmus, který ověří, že se dá dostat z kteréhokoliv místa ve městě kamkoliv?

Neorientovaný graf $G$ je souvislý, pokud mezi každou dvojicí vrcholů existuje cesta. Jinými slovy, z každého vrcholu $u\in V(G)$ se dostaneme do libovolného jiného vrcholu $v\in V(G)$ po nějaké cestě. Graf $G$ můžeme rozložit na komponenty souvislosti. To jsou největší “kusy” (podgrafy) grafu $G$, které jsou souvislé.

Ale co je to souvislost v orientovaném grafu? Po šipkách můžeme projít jen jedním směrem. Opět bychom chtěli zavést “souvislost” tak, aby se bylo možné po šipkách dostat z libovolného vrcholu $u\in V(G)$ do libovolného vrcholu $v\in V(G)$. Tentokrát se ale může stát, že orientovaná cesta z $u$ do $v$ povede jinudy než cesta z $v$ do $u$.

Definice: Dva vrcholy $u,v\in V(G)$ jsou spolu silně propojeny, pokud existuje orientovaná cesta z $u$ do $v$ a i orientovaná cesta z $v$ do $u$. Orientovaný graf $G$ je silně souvislý, pokud je každá dvojice vrcholů $u,v\in V(G)$ silně propojena.

Relace být silně propojen je relace ekvivalence. Třídám této ekvivalence budeme říkat silně souvislé komponenty. Jinými slovy, silně souvislá komponenta je maximální podgraf grafu $G$, který je silně souvislý.

Příklad:

V grafu na obrázku máme $5$ silně souvislých komponent.

Kontrakcí každé silně souvislé komponenty do jednoho meta-vrcholu dostaneme meta-graf.


Pozorování: Meta-graf vzniklý kontrakcí silně souvislých komponent je acyklický orientovaný graf.
Důkaz: Kdyby obsahoval orientovanou kružnici, tak všechny meta-vrcholy na kružnici tvoří jednu silně souvislou komponentu. To je spor s tím, že jsme všechny silně souvislé komponenty zkontrahovali do meta-vrcholů.

Tato struktura orientovaných grafů nám umožňuje topologicky uspořádat silně souvislé komponenty. Silně souvislé komponentě, která odpovídá zdroji/stoku meta-grafu, budeme říkat zdrojová/stoková silně souvislá komponenta.

Při realizaci DFS jsme používali proceduru ${\tt Projdi(v)}$. Ta projde právě všechny vrcholy, které jsou dostupné z vrcholu $v$. Pokud pustíme ${\tt Projdi(v)}$ na vrchol, který leží v silně souvislé komponentě odpovídající stoku meta-grafu, tak se dostaneme právě do všech vrcholů této silně souvislé komponenty.

Konkrétně na výše uvedeném příkladu: pokud v $G$ pustíme ${\tt Projdi(E)}$ na vrchol $E$, tak projdeme právě vrcholy silně souvislé komponenty obsahující $\{ E, F, G, I, J, K \}$. Nešlo by toho nějak využít? Ano, ale budeme muset vyřešit dva problémy:

(A) Jak najít vrchol, který určitě leží v silně souvislé komponentě, která je stokem?

(B) Jak pokračovat dále po té, co najdeme první silně souvislou komponentu?

Začneme s problémem (A). Vrchol, který je ve stokové silně souvislé komponentě se přímo najít nedá. Co se ale dá snadno najít, je vrchol, který leží ve zdrojové silně souvislé komponentě.

Pozorování: Vrchol, který při DFS průchodu grafu $G$ dostane největší opouštěcí čas $\ARRAY{out}{\cdot}$, leží ve zdrojové silně souvislé komponentě grafu $G$.

Pozorování přímo plyne z následujícího obecnějšího pozorování.

Pozorování: Nechť $\ARRAY{out}{v}$ jsou opouštěcí časy vrcholů při DFS průchodu grafu $G$. Pokud $C_1$ a $C_2$ jsou dvě silně souvislé komponenty takové, že z $C_1$ vede hrana do $C_2$, tak potom největší hodnota $\ARRAY{out}{\cdot}$ v první komponentě je větší než největší hodnota $\ARRAY{out}{\cdot}$ ve druhé komponentě.
Důkaz: Mohou nastat dva případy. V prvním případě DFS navštíví komponentu $C_2$ jako první. Potom v ní ale zůstane, dokud ji celou neprozkoumá (to je vlastnost procedury ${\tt Projdi()}$). Teprve pak se DFS dostane do $C_2$.

Ve druhém případě DFS nejprve navštíví $C_1$. Nechť $v$ je vrchol, který byl v $C_1$ navštíven jako první. DFS opustí vrchol $v$, až když prozkoumá všechny vrcholy, které jsou z $v$ dosažitelné a které nebyly dosud navštíveny. Proto nejprve projde celou komponentu $C_2$ a pak se teprve naposledy vrátí do $v$. 

Pozorování [ref]observation_zdroj_zobecnen[/ref] vlastně říká, že sestupné uspořádání silně souvislých komponent podle jejich největšího čísla $\ARRAY{out}{\cdot}$ je topologické.

Pozorování [ref]observation_zdroj[/ref] nám ukazuje, jak najít vrchol, který leží ve zdrojové silně souvislé komponentě. To je přesně naopak, než potřebujeme! Potřebujeme vrchol ležící ve stokové silně souvislé komponentě. Nevadí, vrchol budeme hledat v grafu $G^R$. To je v grafu, který vznikne z $G$ tak, že obrátíme všechny hrany. Graf $G^R$ má stejné silně souvislé komponenty jako graf $G$. Rozmyslete si proč.

Pustíme DFS na graf $G^R$. Vrchol $v$ s největším $\ARRAY{out}{v}$ bude ležet ve stokové silně souvislé komponentě grafu $G$. Tím jsme vyřešili problém (A).

Zbývá vyřešit problém (B). Jak pokračovat po tom, co určíme stokovou silně souvislou komponentu? Znovu využijeme pozorování [ref]observation_zdroj_zobecnen[/ref]. Po té, co z grafu $G$ vymažeme první nalezenou silně souvislou komponentu, tak vrchol $w$ s největším $\ARRAY{out}{w}$ (ze zbylých vrcholů) patří do stokové silně souvislé komponenty zbytku grafu $G$. Pokud si budeme pamatovat hodnoty $\ARRAY{out}{\cdot}$, které jsme získali DFS průchodem grafu $G^R$, tak můžeme z $G$ snadno odtrhnout druhou silně souvislou komponentu, třetí, čtvrtou a tak dál.

Celý algoritmus vypadá následovně:

  1. Pusť DFS na graf $G^R$ a ulož si posloupnost $\ARRAY{out}{\cdot}$ v klesajícím pořadí.
  2. Pusť DFS na graf $G$, ve kterém procházíme vrcholy v pořadí podle klesajících hodnot $\ARRAY{out}{\cdot}$, a vypisuj nalezené komponenty souvislosti (jako v neorientovaném grafu).

Algoritmu běží v lineárním čase $\OO(m+n)$. V podstatě je to dvakrát čas průchodu do hloubky (DFS). (Jak rychle vytvoříme reprezentaci grafu $G^R$? Vejdeme se do času $\OO(m+n)$?)

Zkusme algoritmus pustit na grafu $G$ z příkladu. Pokud si DFS může vybrat z více vrcholů, tak si vybere ten abecedně menší. Pořadí vrcholů podle klesajících časů $\ARRAY{out}{\cdot}$ v průchodu $G^R$ je $L$, $F$, $G$, $K$, $J$, $I$, $E$, $H$, $D$, $B$, $C$, $A$. Silně souvislé komponenty, které algoritmus nalezne, jsou postupně $\{L\}$, $\{E, F, G, I, J, K \}$, $\{D, H\}$, $\{B, C \}$, $\{A \}$.