Motivace: Pomocí orientovaného grafu snadno znázorníme závislosti. Orientovanou hranou (šipkou) mezi úkoly vyjádříme, že druhý úkol můžeme začít provádět až po skončení prvního úkolu. Například když se chceme ráno obléknout, tak si ponožky musíme obléci dříve než boty. Dostaneme seznam úkolů a závislosti mezi nimi. Zajímalo by nás, v jakém pořadí úkoly vykonávat, abychom neporušili závislosti. Zkuste úlohu vyřešit pro následující orientovaný graf.

Jiným příkladem je uspořádání látky probírané na přednáškách tak, aby student nejprve slyšel všechny základy a potřebné ingredience a teprve pak si poslechl navazující výsledky.

Podobně funguje Makefile — soubor se závislostmi pro unixový program make. Často, když chceme ze vstupních souborů dostat požadované výstupy, musíme spustit více programů nebo utilit. Vstupem jednoho programu může být výstup z jiného programu. To určuje závislosti mezi použitými programy. Abychom dostali správný výstup, musíme programy pouštět ve správném pořadí. Závislosti napíšeme do souboru Makefile. Podle něj Make spustí všechny použité programy ve správném pořadí. Při dalším volání, make nespouští vše znova, ale podívá se, které vstupy i mezivýsledky se změnily. Potom spustí pouze ty programy, které přepočítají výstupy ke změněným vstupům. To je hlavní výhoda Make, která často výrazně zrychlí přepočítávání.

Proč se tomu říká topologické uspořádání? Šipky mezi vrcholy můžeme představit jako relaci ‚$\succeq$‘. Potom hledáme lineární uspořádání ‚$\geq$‘, které je rozšířením ‚$\succeq$‘. To znamená, že když $x \succeq y$, pak i $x \geq y$.

Definice: Topologické uspořádání vrcholů orientovaného grafu je seřazení vrcholů do řady $v_1$, $v_2$, $v_3$, \dots, $v_n$ tak, že každá hrana vede zleva doprava. Jinými slovy je to takové očíslování vrcholů čísly $1$ až $n$ takové, že každá hrana vede z vrcholu s nižším číslem do vrcholu s vyšším číslem.

Úkol: Pro zadaný orientovaný graf nalezněte topologické uspořádání.
Přeskládávání vrcholů do topologického uspořádání se někdy říká topologické třídění.

Definice: Orientovaný cyklus je posloupnost $v_0 \to v_1 \to v_2 \to \cdots \to v_{n-1} \to v_n$ taková, že $v_0 = v_n$ a $v_{i-1}v_i$ je orientovaná hrana pro každé $i\in\{1,\dots, n\}$. Orientovaným grafům, které neobsahují orientovaný cyklus, říkáme orientované acyklické grafy.1
Pozorování: Graf $G$ obsahuje orientovaný cyklus $\Longleftrightarrow$ DFS najde zpětnou hranu.
Důkaz: Jeden směr je jednoduchý, pokud je $uv$ zpětná hrana, tak společně s cestou z $v$ do $u$ v DFS stromě tvoří cyklus. Na druhou stranu pokud graf obsahuje orientovaný cyklus, tak označme pomocí $r$ první vrchol cyklu, který byl nalezen při průchodu DFS. Všechny ostatní vrcholy cyklu jsou potomky $r$, protože do nich z $r$ vede orientovaná cesta. Proto je hrana cyklu, vedoucí do $r$, zpětná.
Lemma: Topologické uspořádání orientovaného acyklického grafu nalezneme pomocí DFS tak, že každý vrchol vypíšeme v momentě, kdy ho opouštíme. Na závěr výslednou posloupnost obrátíme. Jinými slovy uspořádání vrcholů podle klesajících časů $\ARRAY{out}{v}$ je topologické.
Důkaz: K důkazu předchozího tvrzení stačí ukázat, že je ve výsledném pořadí každá hrana zorientována správně. Nechť $ij$ je libovolná orientovaná hrana. Podle klasifikace hran z pozorování [ref]poz_intervaly[/ref] je hrana $ij$ buď

$\bullet$ stromová nebo dopředná a potom $\ARRAY{out}{i}>\ARRAY{out}{j}$, nebo je

$\bullet$ příčná, ale pak také $\ARRAY{out}{i}>\ARRAY{out}{j}$. Hrana $ij$ by ještě mohla být

$\bullet$ zpětná, to ale není podle předchozího pozorování možné, protože by graf obsahoval orientovaný cyklus.

Rozpoznávání acykličnosti a hledání topologického uspořádání můžeme spojit do jednoho průchodu DFS. Budeme hledat topologické uspořádání pomocí průchodu do hloubky. Pokud objevíme zpětnou hranu, tak můžeme skončit a odpovědět, že topologické uspořádání neexistuje. V opačném případě topologické uspořádání najdeme. Časová složitost nalezení topologického uspořádání je $\OO(n+m)$.

Poznamenejme na závěr, že topologické uspořádání je pro práci s acyklickými grafy (DAG, directed acyclic graph) stejně důležité, jako třídění pro práci s polem. Řada pěkných algoritmů v acyklických grafech vyžaduje topologicky uspořádané vrcholy. Aplikace najdte ve cvičeních na konci kapitoly.

Alternativním algoritmem pro nalezení topologického uspořádání může být postupné odtrhávání zdrojů (stoků) grafu a jejich vypisování na výstup. Zdroj je vrchol, do kterého nevede žádná hrana. Hrany z něj pouze vychází (vytékají). Naopak do stoku hrany pouze vedou a žádná hrana z něj nevede ven. Zkuste si rozmyslet, proč tento alternativní algoritmus funguje a jaká může být jeho nejrychlejší implementace.

Který algoritmus byste si vybrali pro řešení úlohy na papíře?