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\).)

  • 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í

    Důkaz provedeme sporem podobně jako pro neorientovaný případ.

    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ě/slabě) souvislý, platí \(V_T\cap V_{T'}\ne\emptyset\), tedy lze tah \(T'\) včlenit do tahu \(T\), což je spor.

    Vidíme, že rovnost vstupních a výstupních stupňů ve skutečnosti zesiluje slabou souvislost na silnou.

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