2.3 Sled, cesta a kružnice v grafu
Definice 2.17 (Sled)
Sled délky $k$ v grafu $G$ je sekvence $v_0, e_1, v_1, ..., e_k, v_k$ taková, že $e_i = \{v_{i-1}, v_i\}$ a $e_i \in E(G)$ pro všechna $i = 1, ..., k$
Definice 2.18 (Cesta)
Cesta v grafu $G$ je sled, ve kterém se neopakují vrcholy (a tedy ani hrany).
Má-li cesta $P$ v grafu $G$ koncové vrcholy $s = v_0$ a $t = v_k$, mluvíme o cestě z $s$ do $t$, nebo o $s\textbf{-}t\textbf{-cestě}$.
Délka $s\text{-}t\text{-cesty } d(s,t)$ je počet hran v této cestě (v grafu $G$)
Poznámka 2.2
Připouštíme i cestu s nulovou délkou, tedy $s = t$.
Definice 2.19 (Cesta $P_n$)
Cesta s $n \ge 1$ vrcholy (s $n-1$ hranami) je graf
Definice 2.20 (Kružnice $C_n$)
Kružnice s $n \ge 3$ vrcholy (s $n$ hranami, délky $n$) je graf
Poznámka 2.3
Všimněte si, že definice cesty a kružnice jsou prakticky identické. V kružnici jen přidáváme poslední hranu z $n$-tého vrcholu do prvního vrcholu.
2.3.1 Definice pro orientovaný graf
Definice 2.21 (Orientovaná kružnice / Cyklus)
Nechť $n \geq 1$. Orientovaná kružnice délky $n$ (s $n$ vrcholy) je orientovaný graf
Pozorování 2.4
Orientovaná kružnice může být i délky 1. To je kružnice na jednom vrcholu s jednou smyčkou.
Definice 2.22 (Orientovaný acyklický graf (DAG) / DAG (Directed Acyclic Graph))
Orientovaný graf $G$ nazveme acyklický, pokud neobsahuje jako podgraf orientovanou kružnici.
2.3.2 Definice pro TopSort
Definice 2.23 (Zdroj)
Zdroj je takový vrchol orientovaného grafu, do kterého nevede žádná hrana.
Definice 2.24 (Stok)
Stok je takový vrchol orientovaného grafu, ze kterého nevede žádná hrana.
Věta 2.1 (O existenci stoku)
Nechť $G = (V, E)$ je orientovaný acyklický graf. Potom $G$ obsahuje aspoň jeden zdroj a aspoň jeden stok.
Dokážeme sporem, proto budeme dokazovat tvrzení: „$G = (V,E)$ je orientovaný acyklický graf a zároveň v něm neexistuje žádný zdroj“
Zvolíme libovolný vrchol $v_1 \in V$.
$v_1$ podle našeho předpokladu nemůže být zdrojem, proto do něj musí vést alespoň 1 orientovaná hrana z nějakého vrcholu $v_2$
$v_2$ také nemůže být zdrojem a proto také do něj musí vést alespoň 1 orientovaná hrana z $v_3$, atd.
Nejpozději po $n$ opakování tohoto postupu narazíme na vrchol $x$ který také nemůže být zdrojem, tedy do něj můsí vést alespoň 1 orientovaná hrana z nějakého vrcholu $y$ na který jsme už narazili dříve.
To ale znamená, že v grafu $G$ je nějaký cyklus, což je ve sporu s předpokladem.
Analogicky dokážeme pro stok.
$\square$
Sporem pro existenci zdroje (pro stok analogické).
Předpokládejme, že v $G$ neexistuje zdroj.
Zvolme libovolný vrchol $v_1 \in V$. Do něj, dle předchozího předpokladu, vede alespoň jedna orientovaná hrana z nějakého vrcholu $v_2$.
Do $v_2$ také musí vést orientovaná hrana z nějakého vrcholu $v_3$, a tak dále.
Nejpozději po $n$ krocích se však musí nějaký vrchol zopakovat.
To ale znamená existenci cyklu v $G$, čímž dostáváme spor.
$\square$