Orientované eulerovské grafy
Úloha číslo: 3631
Dokažte: Orientovaný graf \(G\) má uzavřený eulerovský tah právě tehdy, když \(G\) je silně souvislý a vstupní stupeň každého vrcholu je roven jeho výstupnímu stupni.
(Silná souvislost znamená, že mezi každou dvojicí vrcholů \(u\) a \(v\) vede jak orientovaná cesta z \(u\) do \(v\), tak orientovaná cesta z \(v\) do \(u\).)
Řešení
Důkaz provedeme sporem. Nechť \(G\) je nejmenší protipříklad. Zvolme nejdelší uzavřený orientovaný tah \(T\) v \(G\). Odebráním \(T\) z \(G\) zůstane v platnosti, že vstupní a výstupní stupně jsou ve zbylém grafu u každého vrcholu stejné.
Pokud \(T\) neobsahuje všechny hrany, potom má \(G-T\) neprázdnou komponentu. Z indukce lze tuto komponentu pokrýt uzavřeným orientovaným eulerovským tahem \(T'\).
Protože je \(G\) silně souvislý, platí \(V_T\cap V_{T'}\ne\emptyset\), tedy lze tah \(T'\) včlenit do tahu \(T\), což je spor.
Varianta
Dokažte silnější variantu tohoto tvrzení, kde silná souvislost je nahrazena slabou souvislostí.
(Slabá souvislost znamená, že mezi libovolnými dvěma vrcholy vede cesta, jejíž hrany mohou být orientovány jak po, tak proti směru cesty.)
Řešení
Stačí vzít předchozí důkaz a uvědomit si, že pro \(V_T\cap V_{T'}\ne\emptyset\) stačí, aby \(G\) byl jen slabě souvislý.
Vidíme, že rovnost vstupních a výstupních stupňů ve skutečnosti zesiluje slabou souvislost na silnou.
