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í

    Uvažme nejdelší orientovanou cestu. Její počáteční vrchol \(z\) 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.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
Úloha na dokazování, ověřování
	Zaslat komentář k úloze