Obsah ⇫

• eulerovský tah
• eulerovský graf
• sudý graf
• algoritmus nalezení eulerovského tahu

Teorie ⇫

Ve městě Kőnigsbergu (česky nazývaném Královec, dnešním Kaliningradu) jsou v centru města na řece Pregel (dnes Pregolya) dva ostrovy, které v 18. století spojovalo s oběma břehy sedm mostů (viz obrázek níže). Obyvatelé města při nedělní procházce často přemýšleli, zda by bylo možné projít se městem tak, že by procházku začali v jednom místě, přešli všechny mosty, přes každý právě jednou a skončili by tam, kde začali. Protože se jim však stále nedařilo najít způsob, jakým by to provedli, začali se mnozí z nich domnívat, že takovou procházku ani uskutečnit nejde. Tento názor byl matematicky potvrzen roku 1736, kdy byl uvedený problém předložen k vyřešení vynikajícímu švýcarskému matematikovi, Leonhardu Eulerovi. Leonhard Euler nejen tento konkrétní problém vyřešil, ale podal obecnou charakteristiku úloh daného typu.

Sedm mostů v Kőnigsbergu

Pozn.: Uvedený problém je považován za první příspěvek k teorii grafů a rok 1736 je pokládán za počátek teorie grafů.

Pozn.: Eulerovský tah nám umožňuje projít celým grafem, každou hranou právě jednou.

Pozn.: Eulerovský graf lze nakreslit jedním tahem.

Eulerovský graf je charakterizován následující větou:

Věta:

Graf je eulerovský, právě když je souvislý a má buď všechny vrcholy sudého stupně nebo právě dva vrcholy stupně lichého.

Jak nalézt eulerovský tah

Zamysleme se, co můžeme tvrdit o eulerovském grafu, tj. souvislém grafu, jehož všechny vrcholy jsou stupně sudého nebo právě dva vrcholy stupně lichého:

1. V případě všech vrcholů stupně sudého najdeme v grafu nějaký uzavřený tah, obsahuje-li graf právě dva vrcholy stupně lichého, tak v něm najdeme nějaký otevřený tah začínající v jednom z lichých vrcholů a končící v druhém z nich.
2. Jestliže nalezený tah obarvíme, tak ve zbylé neobarvené části grafu (ta již nemusí být souvislá) jsou všechny vrcholy stupně sudého (zamyslete se proč!), tudíž v této části můžeme nalézt nějaký další uzavřený tah. Obarvíme ho jinou barvou. Takto můžeme analogicky postupovat tak dlouho, dokud neobarvíme všechny hrany grafu. Na eulerovský graf lze tudíž pohlížet jako na sjednocení tahů, a to buď všech uzavřených tahů nebo všech uzavřených s výjimkou jediného prvního otevřeného tahu.
3. Vzhledem k souvislosti eulerovského grafu  musí mít každý tah alespoň jeden vrchol společný s alespoň jedním jiným tahem.

Pro počítačové zpracování je zásadní otázka, jak efektivně napojit jednotlivé tahy na sebe. Odpověď nalezneme v Edmonds-Johnsonovu algoritmu procházení labyrintem. Aplikujeme-li tento přístup na eulerovské grafy, je zřejmé, že „zpětný průchod“ hranami (pořadí hran při „zpětném průchodu“) určuje tah, který prochází všemi hranami daného grafu, tj. eulerovský tah.

Na základě výše napsaného můžeme celý proces (algoritmus) hledání jednotlivých tahů a jejich napojování do výsledného eulerovského tahu popsat následovně:

• Uvažujme eulerovský graf.
• Představme si, že modrou pastelkou začneme ve vrcholu x kreslit nějaký tah, dokud to jde. Je zřejmé, že vytvoříme buď uzavřený tah končící ve vrcholu x nebo otevřený tah končící ve vrcholu y, přičemž neobarvené hrany tvoří sudý graf.
• Nyní se po vytvořeném tahu vracejme zpět do prvního vrcholu x1, který je incidentní s nějakou ještě neobarvenou hranou, a tuto zpáteční cestu zaznamenávejme červenou pastelkou. Pak pokračujme v neobarvené části v kreslení dalšího modrého tahu z x1 tak dlouho, dokud je to možné. Je zřejmé, že skončíme ve vrcholu x1 (tvoříme uzavřený tah). A opět se vracejme zpět do prvního vrcholu, který je incidentní s nějakou ještě neobarvenou hranou, a tuto zpáteční cestu zaznamenávejme červenou pastelkou.
• Opakujme popsaný proces tak dlouho, dokud v grafu existují neobarvené hrany.
• Zpáteční cesta zaznamenávaná červenou pastelkou tvoří výsledný eulerovský tah, neboť jednotlivé úseky kreslené červenou pastelkou (zpětný průchod po modře vytvořených tazích) na sebe vždy navazují.

Z hlediska počítačového zpracování je výhodné použít pro zaznamenávání popsaného procesu datovou struktura zásobník. Postupně vkládané vrcholy do zásobníku Z určují jednotlivé tahy (kreslení modrou pastelkou) a postupně ze zásobníku Z odebírané vrcholy ukládané do dalšího zásobníku TAH určují výsledný eulerovský tah („zpětný průchod“ hranami kreslený červenou pastelkou).

Algoritmus nalezení eulerovského tahu

Nechť je dán eulerovský graf G=(V,E) s n vrcholy a m hranami. Nechť vrchol v je vrchol množiny V, přičemž jsou-li všechny vrcholy grafu G sudého stupně, pak v je libovolný vrchol, má-li graf G právě dva vrcholy stupně lichého, je v jeden z nich. Úkolem je nalézt a vypsat eulerovský tah grafu G.

Pozn.: Výsledný eulerovský tah uložený v zásobníku TAH můžeme číst jak od začátku, tak od konce.

Řešený příklad ⇫

1. Je možné nakreslit graf K3,3, kterému chybí jedna hrana, jedním tahem?

Krok 1

chybí-li grafu jedna hrana, je jeho skóre (2,2,3,3,3,3)

Krok 2

ze skóre vidíme, že takovýto graf neobsahuje pouze dva vrcholy lichého stupně

Krok 3

můžeme prohlásit, že bipartitní graf K3,3, kterému chybí jedna hrana nejde nakreslit jedním tahem.

2. Najděte Eulerovský tah pro graf zadaný maticí sousedností:

	a	b	c	d	e	f	g	h
a		1	1
b	1							1
c	1			1	1	1
d			1					1
e			1				1
f			1				1
g					1	1
h		1		1

Krok 1

Krok 2

Krok 3

Krok 4

Krok 5

Teď už nemáme kam z vrcholu a jít, vrchol vyjmeme ze Zásobníku a vložíme do ET (eulerovský tah). LIFO: a,b,h,d,c. ET: a.

Krok 6

Krok 7

Krok 8

Krok 9

Krok 10

Úlohy k řešení ⇫

1. Rozhodněte, který z těchto grafů je eulerovský, který není a proč.

2. Kolik nejméně hran je třeba přidat do grafu K3,3 − e, aby jej bylo možno nakreslit jedním otevřeným tahem?

3. Rozhodněte, zda posloupnost (1,1,2,2,2,3,3,4) může být skóre eulerovského grafu. Své rozhodnutí zdůvodněte.

4. Ve městě, které se rozkládá na třech ostrovech A,B,C a dvou březích D,E jedné řeky, bylo vybudováno osm mostů následovně: A je spojené s B dvěma mosty, C je spojené s D dvěma mosty, A je spojené s E jedním mostem, A je spojené s C jedním mostem, B je spojené s C jedním mostem a jeden most spojuje břehy E a D. Každý z pěti spolužáků bydlících v právě jedné části města (A,B,C,D,E) mělo na návštěvě hosty. Spolužáci se rozhodli, že hosty provedou městem a přitom projdou každým mostem a svoji vycházku ukončí v cukrárně na ostrově B. Zjistěte, zda se některému ze spolužáků podařilo projít se svými hosty město tak, že prošli každým mostem právě jednou a vycházku ukončí na ostrově B.

5. V následujících grafech najděte eulerovské tahy, použijte algoritmus:

6. V následujícím grafu zadaném maticí najděte eulerovský tah, použijte algoritmus:

	a	b	c	d	e	f	g	h
a		1				1	1
b	1		1	1				1
c		1		1	1
d		1	1			1		1
e			1				1
f	1			1
g	1				1
h		1		1

Zdroje textů

1. DIMA - diskrétní matematika, http://oliva.uhk.cz
2. Hliněný, Petr. Diskrétní Matematika (456-533 DIM), 2006
3. Kovář, Petr. DISKRÉTNÍ MATEMATIKA a ÚVOD DO TEORIE GRAFŮ ( příklady k procvičení ), 2012