Existence zdroje a stoku
Úloha číslo: 4315
Nechť \(G\) je acyklický orientovaný graf (pozor, to není totéž, co strom: myslime graf bez orientovaných cyklů). Dokažte, že v \(G\) existují vrcholy \(z\) (zdroj) a \(s\) (stok) takové, že \({\rm deg}^{\rm in}(z)={\rm deg}^{\rm out}(s)=0\).
Nápověda
Uvažte nejdelší cestu.Řešení
Počáteční vrchol \(z\) nejdelší orientované cesty musí být zdroj: kdyby nebyl, existuje hrana \((x,z)\) z nějakého vrcholu \(x\). Pokud \(x\) leží na cestě, v grafu je cyklus; pokud na cestě neleží, je možno cestu prodloužit o hranu \((x,z)\), takže nebyla nejdelší.
Symetrickým argumentem dokážeme, že koncový vrchol cesty je stok.
