Motivace: Městem Královec protéká řeka Préva, na které leží sedm mostů. Stará mapa Královce je na vedlejším obrázku. Šlechtici 18. století už nevěděli coby a tak chtěli během večerní projížďky projet město v kočáře tak, aby přes každý most projeli právě jednou. Nevěděli jak na to a slibovali velkou odměnu tomu, kdo jim ukáže, jak to udělat. Nakonec přišel pan Euler, úlohu vyřešil a odpověděl, že to nejde. Odměnu samozřejmě nedostal.

Jinou motivací pro hledání Eulerovského tahu jsou jednotažky. Dostaneme obrázek a chceme ho nakreslit jedním tahem aniž bychom zvedli tužku z papíru. Známou jednotažkou je například domeček a nebo následující obrázek.

Sled je posloupnost $v_0$, $e_0$, $v_1$, $e_1$,\dots $v_n$ taková, že $e_i=\{v_i, v_{i+1}\}$ (neboli každé $2$ po sobě jdoucí hrany mají společný vrchol). Pokud se v posloupnosti neopakují hrany, tak ji nazveme tah a pokud se neopakují ani vrcholy, tak ji nazveme cesta. Uzavřený tah je tah, který začíná i končí ve stejném vrcholu. Uzavřený tah nazveme cyklus. Uzavřený Eulerovský tah je tah, který projde všechny hrany grafu a vrátí se do výchozího vrcholu. Graf, který obsahuje alespoň jeden uzavřený Eulerovský tah se nazývá Eulerovský.

Věta: Souvislý graf $G$ je Eulerovský $\Longleftrightarrow$ všechny jeho vrcholy mají sudý stupeň.

Jak najít Eulerovský tah? Na začátku pro jednoduchost předpokládejme, že má každý vrchol sudý stupeň. Pro nalezení uzavřeného Eulerovského tahu použijeme proceduru Euler($v$). Procedura vypíše vrcholy v pořadí, jak po sobě následují v uzavřeném Eulerovském tahu (vrchol, kterým tah projde $k$-krát, se na výstupu objeví také $k$-krát). Procedura Euler() funguje hodně podobně jako DFS. Tentokrát můžeme vrcholem projít několikrát, ale každou hranou stále jen jednou.

Euler($v$):
	while $\exists$ neprošlá hrana $vw$  do
		 označ hranu $vw$
		 Euler($w$)
		 vypiš($v$)

Začneme ve vrcholu $v$ a projdeme po libovolné hraně. Každou hranu, po které procházíme, označíme. Vždy když přijdeme do vrcholu různého od $v$, tak z něj můžeme odejít po neoznačené hraně. To platí proto, že všechny vrcholy mají sudý stupeň a každý průchod přes vrchol označí právě dvě hrany (po jedné jsme přišli a po druhé odešli). Jedinou výjimkou je výchozí vrchol $v$, protože má navíc označenu hranu, na které jsme tah začali. Po příchodu do výchozího vrcholu se napojíme na začátek tahu a dostaneme cyklus.

Pokud tento cyklus z grafu vyhodíme, dostaneme komponenty souvislosti, které jsou zase Eulerovské (z každého vrcholu jsme vyhodili sudý počet hran). Ve skutečnosti hrany nevyhazujeme, jen je označujeme za prošlé. V neoznačených hranách najdeme stejným způsobem další cyklus. Opakováním postupu nacházíme cykly tak dlouho, dokud jsou v grafu neoznačené hrany.

Slepením nalezených cyklů dohromady dostaneme uzavřený Eulerovský tah. Lepení probíhá podobně, jako když si na výletě s naplánovanou trasou vyrazíte na neplánovaný vyhlídkový okruh. Na chvíli necháte průchodu po naplánované trase, případně odložíte batohy, a vyrazíte na vyhlídkový okruh. Když se vrátíte k batohům, tak pokračujete dále po naplánované trase. Toto lepení za nás v proceduře Euler($v$) provede rekurze.

Jak přesně ta rekurze funguje? Nejprve udělá plán a projde první cyklus (vrcholy naplánovaného tahu jsou uloženy na zásobníku rekurze a hrany cyklu jsou označeny za prošlé). Potom se rekurze začne vracet a vypisovat tah. Když se vrátí do vrcholu, odkud vedou neoznačené hrany, zavolá kamarádku rekurzi, aby zajistila vypsání „výletního“ okruhu. Až se kamarádka rekurze vrátí, vypíše se vrchol a pokračuje se v návratu z rekurze.

Kdybychom dopředu nevěděli, jestli má každý vrchol grafu sudý stupeň, tak to můžeme během algoritmu snadno zjistit. Pokud během algoritmu přijdeme do vrcholu $w$ (jiného než výchozího vrchol) a už z něj nemůžeme pokračovat dále (všechny hrany vedoucí z vrcholu už jsou označené), tak odpovíme, že $w$ má lichý stupeň a tím pádem víme, že uzavřený Eulerovský tah neexistuje.

Poznámka: K tomu, abychom nakreslili jednotažku jedním tahem, aniž bychom zvedli tužku z papíru, nepotřebujeme uzavřený Eulerovský tah. Stačí otevřený Eulerovský tah. Otevřený Eulerovský tah je tah, který projde všechny hrany grafu. Neklademe si žádnou podmínku na to, aby tah skončil ve výchozím vrcholu. Může skončit jinde než začal. Platí věta, která říká, že v souvislém grafu existuje otevřený Eulerovský tah právě tehdy, když všechny vrcholy, až na dva, mají sudý stupeň. Eulerovský tah v jednom lichém vrcholu začne a ve druhém skončí.

Jak by vypadal algoritmus pro nalezení otevřeného Eulerovského tahu?

Pošťákův problém


Motivace: (Problém kropicího vozu) V jednom městě se vzorně starají o své občany. Každý den kropí a zametají všechny ulice, které ve městě mají. Protože je to vzorné město, tak se radní starají i o úsporný rozpočet města. Proto chtějí najít pro řidiče zametacího vozu takovou trasu, aby pokropil a zametl všechny ulice města, ale najezdil co nejméně kilometrů.

Nalezení optimální trasy by městu opravdu pomohlo, protože by ušetřili i při svozu odpadu, rozvozu informačních letáků či volebních lístů. Optimální trasu by ocenila i místní pošta.

Problém se v literatuře označuje jako pošťákův problém, protože se problém poprvé studoval v souvisloti s roznášením pošty.1

Úkol: (Pošťákův problém) Dostanete souvislý graf $G=(V,E)$. Nalezněte nejkratší sled, který obsahuje všechny hrany.

Připomeňme, že sled je posloupnost $v_0$, $e_0$, $v_1$, $e_1$,$\dots$ $v_n$ taková, že $e_i=\{v_i, v_{i+1}\}$ (neboli každé $2$ po sobě jdoucí hrany mají společný vrchol). Sled, který je optimálním řešením úlohy nazveme pošťákův sled.

Pokud by v grafu $G$ existoval uzavřený Eulerovský tah, tak je optimálním řešením úlohy. Eulerovský tah projde všechny hrany a každou hranu právě jednou. V takovém případě je řešení jednoduché.

Pokud v grafu neexistuje uzavřený Eulerovský tah, tak budeme muset projít některé hrany vícekrát. Souvislé grafy, které neobsahují uzavřený Eulerovský tah obsahují vrcholy lichého stupně. Nechť $T\subseteq V$ je množina vrcholů lichého stupně. $|T|$ je sudé, protože součet stupňů všech vrcholů je sudé číslo (každá hrana přispěje do tohoto součtu dvojkou).

Lemma: Nechť $S$ je sled, který je optimálním řešením úlohy. Každá hrana grafu je v $S$ použita nejvýše dvakrát.

Pokud by byla některá hrana $uv$ sledu $S$ použita aspoň třikrát, tak můžeme sled $S$ zkrátit. Na následujícím obrázku je naznačeno zkrácení sledu v případě, kdy po hraně $uv$ vedou 2 průchodu sledu $S$ jdoucí proti sobě (hrana $uv$ zůstane obsažena ve sledu $S$ díky třetímu průchodu). Ještě si rozmyslete možnost, že by sled procházel hranu $uv$ třikrát ve stejném směru.

Lemma: Nechť $H\subseteq G$ je podgraf, který obsahuje právě ty hrany, které optimální sled $S$ projde dvakrát. Vrcholy lichého stupně $H$ jsou právě vrcholy $T$. Pograf $H$ neobsahuje cykly.

V multigrafu, který obsahuje každou hranu tolikkrát, kolikkrát ji projde sled $S$, má každý vrchol sudý stupeň (sled je uzavřený a proto pokaždé když vstoupí do vrcholu, tak z něj i odejde). Po vyhození hran $E(G)$ z multigrafu nám zůstane právě graf $H$. Lichý vrchol $v\in H$ mohl vzniknout pouze tak, že jsme vyhodili lichý počet hran vedoucích z $v$. To ukazuje, že liché vrcholy $H$ jednoznačně odpovídají lichým vrcholům v $G$.

Pokud $H$ obsahuje cyklus, tak ho z $H$ vyhodíme a dostaneme graf $H’$. V multigrafu, který vznikne součtem $G$ a $H’$, už má každý vrchol sudý stupeň. Proto v něm existuje uzavřený Eulerovský tah, který je také řešením úlohy, a prochází méně hran než sled $S$. To je spor s tím, že $S$ je optimální sled.

Důsledkem předchozího lemmatu už konečně dostaneme charakterizaci grafu $H$.

Lemma: $H$ se skládá z $|T|/2$ hranově disjunktních cest, jejichž konce leží v $T$.
Teď už máme skoro všechna pozorování potřebná k tomu, abychom úlohu vyřešili. Poslední ingrediencí je algoritmus na maximální párování. Párování $M$ v grafu $G$ je množina vrcholově disjunktních hran (žádné dvě hrany z $M$ nemohou sdílet vrchol).

Algoritmus na maximální párování si zde nevysvětlíme, protože jeho popis by vydal na samostatnou kapitolu. Časová složitost algoritmu je polynomiální. Popis algoritmu na maximální párování v bipartitním grafu najdete u aplikací toků v sítích v sekci [ref]section_aplikace_toku_v_sitich[/ref]. Popis algoritmu pro obecné grafy čtenář nalezne například v [CCPSCombOpt].

Algoritmus řešící Pošťákův problém:

  1. Nalezneme vrcholy $T$, které mají lichý stupeň v $G$. Chceme najít $|T|/2$ cest, které spárují vrcholy $T$ a budou obsahovat co nejméně hran. Provedeme to následovně. Vytvoříme pomocný graf $G’$ na vrcholech $T$. Každé dva vrcholy $u,v\in T$ spojíme hranou $uv$, kterou odhodnotíme délkou nejkratší cesty mezi $u$ a $v$. V grafu $G’$ nalezneme maximální párování minimální ceny. Nalezené párování odpovídá hledaným cestám. Ty tvoří optimální graf $H$.
  2. V multigrafu $G+H$ najdeme uzavřený Eulerovský tah. Ten odpovídá sledu, který je řešením úlohy.

Poznámka: V reálných úlohách chceme skutečně najezdit co nejméně. Každá silnice má svojí délku $d(e)$. Chceme najít nejkratší sled, který projde všechny hrany. Délka sledu je součet délek hran, které prochází.

Algoritmus řešící Pošťákův problém v ohodnocených grafech vypadá skoro stejně jako pro neohodnocené grafy, jenom místo maximální párování hledáme maximální párování minimální ceny (cena párování $M$ je součet cen všech hran patřících do $M$). Maximální párování minimální ceny se dá najít v polynomiálním čase a proto umíme ve stejném čase vyřešit i Pošťákův problém v ohodnocených grafech. Více informací čtenář najde například v [CCPSCombOpt].

Poznámka: Pošťákův problém je orientovaných grafech o něco jednoduší, protože ho můžeme vyřešit pomocí toků v sítích. Viz cvičení [ref]priklad_orientovany_euleruv_tah[/ref] na konci sekce [ref]cviceni_aplikace_toku_v_sitich[/ref].