Podobová Veronika_
Trčková Daniela____
Vybíralová Michaela
Úkol: Použijte algoritmus pro hledání eulerovského tahu v grafu G.
Je graf G Eulerovský?
Nutná a postačující podmínka pro Eulerovský graf:
Skóre grafu: (3, 3, 4, 4, 4, 4)
Graf má právě dva vrcholy lichého stupně (3), ostatní vrcholy jsou stupně sudého (4).
Jedná se tedy o eulerovský graf. V eulerovském grafu existuje uzavřený či otevřený
eulerovský tah T, který obsahuje všechny hrany grafu G.
Otevřený nebo uzavřený eulerovský tah?
V eulerovském grafu, který má právě dva vrcholy lichého stupně, nalezneme otevřený
eulerovský tah. Počáteční a koncový vrchol bude lichého stupně a ostatní vrcholy, kudy
prochází eulerovský tah, budou stupně sudého.
POZN. Obsahuje-li pouze vrcholy stupně sudého, nalezneme v něm uzavřený eulerovský tah.
Algoritmus pro nalezení otevřeného eulerovského tahu T (pomocí zásobníků)
1. Nejdříve si připravíme zásobníky Z a ET.
2. Začneme u vrcholu A a hledáme nejdelší tah; při volbě následující hrany
uplatňujeme lexikografické pravidlo (hledáme vrcholy, které jsou označeny
písmenem, které je abecedně dřív)
3. Tah vyznačíme modrou barvou a všechny vrcholy, které projdeme, zapíšeme do
zásobníku Z.
TAH: A – B – E – C – A – D – C – F – B
4. Ze zásobníku Z vezmeme poslední vrchol (tj. vrchol B) a převedeme jej do
zásobníku ET.
Nový vrchol v zásobníku Z (tj. vrchol F) ukazuje, do kterého vrcholu máme jít zpětnou
hranou z vrcholu B; tuto hranu (BF) označíme červeně.
5. Jsme ve vrcholu F a máme zde ještě neoznačené hrany, proto znovu, modrou
barvou, z vrcholu F najdeme nejdelší tah, vrcholy opět zapisujeme do zásobníku Z.
TAH: F – D – E – F
6. Ze zásobníku Z vezme poslední vrchol (tj. F) a převedeme jej do zásobníku ET.
Opět získáme nový vrchol zásobníku Z (tj. E), který nám ukazuje, do kterého
vrcholu povedeme hranu. Hranu (FE) označíme červeně.
Tento postup opakujeme do té doby, než všechny hrany nejsou označeny červeně.
Ze zásobníku Z vezme vrchol E a převedeme jej do zásobníku ET. Nový vrchol D zásobníku Z
nám ukazuje, do kterého vrcholu povedeme hranu. Hranu (ED) označíme červeně.
Ze zásobníku Z vezme vrchol D a převedeme jej do zásobníku ET. Nový vrchol F zásobníku Z
nám ukazuje, do kterého vrcholu povedeme hranu. Hranu (DF) označíme červeně.
.
.
.
Eulerovský tah je zaznamenaný v zásobníku ET.
EULEROVSKÝ TAH: A – B – E – C – A – D – C – F – D – E – F – B
Nebo: B – F – E – D – F – C – D – A – C – E – B – A