MA2BP_PDM1 Diskrétní matematika 1 7. Eulerovské grafy Lukáš Másilko Středisko pro pomoc studentům se specifickými nároky Masarykova univerzita 28. 11. 2017 28. 11. 2017 1 / 36 Program prezentace □ Zavedení Eulerovských grafů Procházení labyrintů Hledání eulerovských tahů □ Použité zdroje 28. 11. 2017 2 / 36 Úvodní příklad Nakreslete jedním tahem květinu zobrazenou na následujícím grafu. ô Úkol spočívající v nakreslení eulerovského tahu 28. 11. 2017 3 / 36 Eulerovský tah a graf Definice 2.3 (MILKOVA): ■ Eulerovský tah v grafu G je uzavřený nebo otevřený tah, který obsahuje všechny hrany grafu G. ■ Eulerovský graf je souvislý graf G, ve kterém existuje eulerovský tah. Historická poznámka: Název se vztahuje ke slavnému švýcarskému matematikovi Leonardovi Eulerovi (1707-1783), který v r. 1736 řešil Problém sedmi mostů města Královce (původně Königsberg, dnes Kaliningrad na Kaliningradském území Ruska mezi Polskem a Litvou, do r. 1945 hlavní město Východního Pruska). Jde o první příspěvek k teorii grafů a rok 1736 je pokládán za počátek teorie grafů. 28. 11. 2017 4 / 36 Problém sedmi mostů města Královce Ve městě Královec jsou v centru města na řece Pregel (dnes Pregolya) dva ostrovy, které v 18. století spojovalo s oběma břehy sedm mostů: c B Obyvatelé města při procházkách často přemýšleli, zda by bylo možné projít se městem tak, aby procházku začali v jednom místě, přešli všechny mosty, přes každý právě jednou, a vrátili se tam, kde začali. 28. 11. 2017 5 / 36 Problém sedmi mostů města Královce Převedeno do teorie grafů: existuje v následujícím grafu uzavřený eulerovský tah? Leonard Euler ukázal, že to není možné, a dokonce formuloval obecnou charakteristiku úloh daného typu. 28. 11. 2017 6 / 36 Nutná a postačující podmínka pro Eulerovský graf Věta 2.2 (MILKOVA): Pro každý graf G = (V, E) platí: Graf G je eulerovský právě tehdy, když G je souvislý a má buď všechny vrcholy sudého stupně nebo právě dva vrcholy lichého stupně. 28. 11. 2017 7 / 36 Nutná a postačující podmínka pro Eulerovský graf Věta 2.2 (MILKOVA): Pro každý graf G = (V, E) platí: Graf G je eulerovský právě tehdy, když G je souvislý a má buď všechny vrcholy sudého stupně nebo právě dva vrcholy lichého stupně. Důkaz (nebude vyžadován u zkoušky): jedná se tvrzení tvaru logické ekvivalence, je tedy třeba ukázat oba implikační směry: H Graf G je eulerovský =4> G je souvislý a má buď všechny vrcholy sudého stupně nebo právě dva vrcholy lichého stupně. B "<^:" Graf G je souvislý a má buď všechny vrcholy sudého stupně nebo právě dva vrcholy lichého stupně =4> G je eulerovský. 28. 11. 2017 7 / 36 Nutná a postačující podmínka pro Eulerovský graf Věta 2.2 (MILKOVA): Pro každý graf G = (V, E) platí: I Graf G je eulerovský právě tehdy, když G je souvislý a má buď všechny vrcholy sudého stupně nebo právě dva vrcholy lichého stupně. I Důkaz (nebude vyžadován u zkoušky): jedná se tvrzení tvaru logické ekvivalence, je tedy třeba ukázat oba implikační směry: H Graf G je eulerovský =4> G je souvislý a má buď všechny vrcholy sudého stupně nebo právě dva vrcholy lichého stupně. B "<^:" Graf G je souvislý a má buď všechny vrcholy sudého stupně nebo právě dva vrcholy lichého stupně =4> G je eulerovský. Směr "=^" si nyní ukážeme. Pro směr "<^" budeme potřebovat několik pomocných tvrzení. 28. 11. 2017 7 / 36 Důkaz Věty 2.2 ve směru Předpokládejme, zeje graf G eulerovský. Z definice 2.1 tedy je souvislý a existuje v něm (uzavřený či otevřený) eulerovský tah T obsahující všechny hrany grafu G. 2 28. 11. 2017 8 / 36 Důkaz Věty 2.2 ve směru Předpokládejme, zeje graf G eulerovský. Z definice 2.1 tedy je souvislý a existuje v něm (uzavřený či otevřený) eulerovský tah T obsahující všechny hrany grafu G. H Je-li T uzavřený, pak každý vrchol G, kterým tah minimálně jednou prochází, je sudého stupně. Pro každý v G V totiž platí degG(v) = 2p, kde p počet výskytů vrcholu v v tahu T. 2 28. 11. 2017 8 / 36 Důkaz Věty 2.2 ve směru Předpokládejme, zeje graf G eulerovský. Z definice 2.1 tedy je souvislý a existuje v něm (uzavřený či otevřený) eulerovský tah T obsahující všechny hrany grafu G. H Je-li T uzavřený, pak každý vrchol G, kterým tah minimálně jednou prochází, je sudého stupně. Pro každý v G V totiž platí degG(v) = 2p, kde p počet výskytů vrcholu v v tahu T. B Je-li T otevřený, pak počáteční a koncový vrchol tahu T mají lichý stupeň. Ostatní vnitrní vrcholy tahu T mají sudý stupeň. 28. 11. 2017 8 / 36 Připomenutí a první pomocné tvrzení Pro připomenutí: ■ Důsledek 1.1 (Milkova): Počet vrcholů lichého stupně v grafu G je sudý. ■ Důsledek 1.2 (Milkova): Hrana grafu je buď most nebo leží na nějaké kružnici grafu. ■ Definice: Graf G = {V, E) nazveme sudým grafem, jsou-li všechny vrcholy v G V sudého stupně. Tvrzení 2.1 (Milkova): Pro každý graf G = (V,E) platí: Jestliže je graf G sudý, pak G neobsahuje most. Důkaz: provedeme sporem, tj. předpokládejme, že existuje sudý graf G — (\/, E), který obsahuje most: hranu e = {v, w}, viz následující slajd. 28. 11. 2017 9 / 36 Důkaz Tvrzení 2.1 Graf G s mostem e = {v, w}\ Z grafu odebereme hranu e a podíváme se na komponentu Qi obsahující vrchol v. 28. 11. 2017 10 / 36 Důkaz Tvrzení 2.1 Komponenta Qi s vrcholem v: Protože graf G byl sudý, jsou všechny vrcholy komponenty Qi sudého stupně s výjimkou vrcholu v, u něhož se po odebrání hrany e změnil stupeň ze sudého na lichý. 28. 11. 2017 10 / 36 Důkaz Tvrzení 2.1 Komponenta Qi s vrcholem v: Protože graf G byl sudý, jsou všechny vrcholy komponenty Qi sudého stupně s výjimkou vrcholu v, u něhož se po odebrání hrany e změnil stupeň ze sudého na lichý. Spor s Důsledkem 1.1 (počet vrcholů lichého stupně grafu musí být sudý) =4> platí Tvrzení 2.1: Sudý graf neobsahuje most. 28. 11. 2017 10 / 36 Druhé pomocné tvrzení Tvrzení 2.2 (Milkova): Pro každý graf G = (\/, E) platí: Jestliže graf G je sudý, pak každá hrana grafu G leží na nějaké kružnici grafu G. Důkaz: 28. 11. 2017 11 / 36 Druhé pomocné tvrzení Tvrzení 2.2 (Milkova): Pro každý graf G — {V^E) platí: Jestliže graf G je sudý, pak každá hrana grafu G leží na nějaké kružnici grafu G. Důkaz: O Dle Důsledku 1.2 je hrana libovolného grafu buď most nebo leží na nějaké kružnici grafu. B Dle Tvrzení 2.1 sudý graf neobsahuje most. 28. 11. 2017 11 / 36 Druhé pomocné tvrzení Tvrzení 2.2 (Milkova): Pro každý graf G — {V^E) platí: Jestliže graf G je sudý, pak každá hrana grafu G leží na nějaké kružnici grafu G. Důkaz: □ Dle Důsledku 1.2 je hrana libovolného grafu buď most nebo leží na nějaké kružnici grafu. B Dle Tvrzení 2.1 sudý graf neobsahuje most. Z toho vyplývá, že každá hrana sudého grafu leží na nějaké kružnici. 28. 11. 2017 11 / 36 Třetí pomocné tvrzení Tvrzení 2.3 (Milkova): Pro každý graf G = (\/, E) platí: Jestliže graf G je sudý, pak graf G lze zapsat jako sjednocení kružnic, které jsou navzájem po dvou hranově disjunktní. Důkaz (nebude vyžadován u zkoušky): 28. 11. 2017 12 / 36 Třetí pomocné tvrzení Tvrzení 2.3 (Milkova): Pro každý graf G = (\/, E) platí: Jestliže graf G je sudý, pak graf G lze zapsat jako sjednocení kružnic, které jsou navzájem po dvou hranově disjunktní. Důkaz (nebude vyžadován u zkoušky): Nechť G = (\/, E) je sudý gráfa e jeho libovolná hrana, viz následující ilustrační obrázek. 28. 11. 2017 12 / 36 Důkaz Tvrzení 2.3 28. 11. 2017 13 / 36 Důkaz Tvrzení 2.3 Když odebereme všechny hrany kružnice C z grafu G, dostaneme opět sudý graf: Proč? Vyjmutím hran kružnice se stupeň libovolného vrcholu kružnice sníží přesně o dva, tj. zůstane sudý. 28. 11. 2017 13 / 36 Důkaz Tvrzení 2.3 Postup opakujeme tak dlouho, dokud získáme graf G' — (V,0): 28. 11. 2017 13 / 36 Důkaz Tvrzení 2.3 Postup opakujeme tak dlouho, dokud získáme graf G' — (V,0): 28. 11. 2017 13 / 36 Důkaz Tvrzení 2.3 Postup opakujeme tak dlouho, dokud získáme graf G' — (V,0): 28. 11. 2017 13 / 36 Důkaz Tvrzení 2.3 Postup opakujeme tak dlouho, dokud získáme graf G' — (V,0): Když postupně sjednotíme kružnice, které jsme před chvílí odebírali (a které byly hranově disjunktní), dostaneme původní graf G. 28. 11. 2017 13 / 36 Dokončení důkazu Věty 2.2 Vraťme se zpátky k Větě 2.2: Věta 2.2 (MILKOVA): Pro každý graf G = {V, E) platí: Graf G je eulerovský právě tehdy, když G je souvislý a má buď všechny vrcholy sudého stupně nebo právě dva vrcholy lichého stupně. Už jsme dokázali směr "=^". 28. 11. 2017 14 / 36 Dokončení důkazu Věty 2.2 Vraťme se zpátky k Větě 2.2: Věta 2.2 (MILKOVA): Pro každý graf G = {V, E) platí: Graf G je eulerovský právě tehdy, když G je souvislý a má buď všechny vrcholy sudého stupně nebo právě dva vrcholy lichého stupně. Už jsme dokázali směr "=^". Chybí dokázat směr "<^:" (*) Graf G je souvislý a má buď všechny vrcholy sudého stupně nebo právě dva vrcholy lichého stupně =4> G je eulerovský. 28. 11. 2017 14 / 36 Dokončení důkazu Věty 2.2 Vraťme se zpátky k Větě 2.2: Věta 2.2 (MILKOVA): Pro každý graf G = {V, E) platí: | Graf G je eulerovský právě tehdy, když G je souvislý a má buď všechny vrcholy sudého stupně nebo právě dva vrcholy lichého stupně. I Už jsme dokázali směr "=^". Chybí dokázat směr "<^:" (*) Graf G je souvislý a má buď všechny vrcholy sudého stupně nebo právě dva vrcholy lichého stupně =4> G je eulerovský. Nejdříve si tvrzení (*) dokážeme pro souvislý graf, v němž jsou všechny vrcholy sudého stupně. Provedeme to matematickou indukcí vzhledem k počtu hran m, m > 1. 28. 11. 2017 14 / 36 Důkaz Věty 2.2 ve směru "<^M Mějme sudý souvislý graf G. 28. 11. 2017 15 / 36 Důkaz Věty 2.2 ve směru "<^M Mějme sudý souvislý graf G. Báze: Nejmenší sudý souvislý graf G má 3 hrany - jedná se o kružnici (trojúhelník) C3 =4> kružnice C3 je uzavřený eulerovský tah. 28. 11. 2017 15 / 36 Důkaz Věty 2.2 ve směru "<^M Mějme sudý souvislý graf G. Báze: Nejmenší sudý souvislý graf G má 3 hrany - jedná se o kružnici (trojúhelník) C3 =4> kružnice C3 je uzavřený eulerovský tah. Indukční predpoklad: Sudý souvislý graf s počtem hran < m obsahuje uzavřený eulerovský tah. 28. 11. 2017 15 / 36 Důkaz Věty 2.2 ve směru "<^M Mějme sudý souvislý graf G. Báze: Nejmenší sudý souvislý graf G má 3 hrany - jedná se o kružnici (trojúhelník) C3 =4> kružnice C3 je uzavřený eulerovský tah. Indukční predpoklad: Sudý souvislý graf s počtem hran < m obsahuje uzavřený eulerovský tah. Indukční krok: Uvažujme sudý souvislý graf, který má m + 1 hran. 28. 11. 2017 15 / 36 Indukční krok důkazu Věty 2.2 ve směru Dle Tvrzení 2.3 je sudý graf sjednocením několika kružnic navzájem hranově disjunktních. Vybereme některou z těchto kružnic a označíme ji C: Po odebrání hran kružnice C bude graf Gř = (V, E - {e G C}) sudý, ne však nutně souvislý. □ gp ► 4 š ► 4 = 1 Q, O 28. 11. 2017 16 / 36 Indukční krok důkazu Věty 2.2 ve směru "<^M Zbylé komponenty grafu G' jsou sudé grafy, které mají určitě < m hran: Tyto komponenty obsahují dle IP uzavřené eulerovské tahy (jsou souvislé a mají < m hran). 28. 11. 2017 16 / 36 Indukční krok důkazu Věty 2.2 ve směru "<^M Komponenty (uzavřené eulerovské tahy) spojíme do grafu G hranami kružnice C a získáme uzavřený eulerovský tah o m + 1 hranách. Platí tedy: (**) Sudý souvislý graf obsahuje uzavřený eulerovský tah. 28. 11. 2017 16 / 36 Indukční krok důkazu Věty 2.2 ve směru "<^M Chtěli jsme dokázat Větu 2.2 ve směru "<^", tj. tvrzení: (*) Graf G je souvislý a má buď všechny vrcholy sudého stupně nebo právě dva vrcholy lichého stupně =4> G je eulerovský. Pro sudé souvislé grafy je již tvrzení (*) je dokázáno. 28. 11. 2017 17 / 36 Indukční krok důkazu Věty 2.2 ve směru "<^M Uvažujme tedy souvislý graf G = (\/, E) s právě dvěma vrcholy x,y e V lichého stupně. Chceme ukázat, že G obsahuje otevřený eulerovský tah. 28. 11. 2017 17 / 36 Indukční krok důkazu Věty 2.2 ve směru "<^M Spojíme vrcholy x,y s novým uzlem v* a vytvoříme sudý graf G' = {VU{v*},EU{{x, v*},{y,v*}}: Nový sudý a souvislý graf G' obsahuje, dle dokázaného tvrzení (**), uzavřený eulerovský tah. 28. 11. 2017 17 / 36 Indukční krok důkazu Věty 2.2 ve směru "<^M Odebráním uzlu v* z grafu G' získáme otevřený eulerovský tah v grafu G. Souvislý graf G s právě dvěma vrcholy lichého stupně je tudíž eulerovský. 28. 11. 2017 17 / 36 Eulerovské vs. Hamiltonovské grafy ■ Věta 2.2 je jednoznačným kritériem pro rozhodnutí, zdaje zadaný graf eulerovský. Takovou nutnou a postačující podmínku jsme pro hamiltonovské grafy neměli. ■ K rozlišení obou typů grafů nám pomůže následující srovnání: Q Eulerovský graf = problém průzkumníka (vydává se na průzkum všech ulic města nebo jeho části, chtěl by každou ulici projít právě jednou). B Hamiltonovský graf = problém cestujícího (vyjíždí na putování po určených městech a chtěl by si trasu naplánovat tak, aby každé navštívil právě jednou). 28. 11. 2017 18 / 36 Příklad 2.4 Určete, zda je následující graf eulerovský. Príklad 2.4 Určete, zda je následující graf eulerovský. Řešení: zapíšeme si skóre grafu: (2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 6). Jedná se o souvislý a sudý graf, obsahuje tedy uzavřený eulerovský tah. Graf je eulerovský. 28. 11. 2017 19 / 36 Odklízení sněhu z chodníků Představte si, že jste na brigádě a Vaším úkolem je odklízení sněhu z chodníků v ulicích jisté části města Brna, jejíž plánek máte k dispozici. Víte, že se jedná o ulice, které mají chodníky po obou stranách. Jak si naplánujete úklid, aby průchod ulicemi byl efektivní (tj. abychom každou stranu ulice prošli právě jednou)? 28. 11. 2017 20 / 36 Procházení labyrintů Ukázka bludiště v zahradě Hampton Court Paláce (jihozápadní Londýn) -viz plánek: První pokusy o nalezení algoritmu pro procházení labyrintu byly učiněny v letech 1873 až 1895 (Wiener, Trémaux, Tarry). 28. 11. 2017 21 / 36 Jak labyrinty převést do grafu? Křižovatky a konce chodeb označíme písmeny Jak labyrinty převést do grafu? Písmena budou vrcholy grafu. Dva uzly x,y propojíme hranou, pokud mezi nimi existuje chodba: © © © 28. 11. 2017 22 / 36 Edmons-Johnsonův algoritmus ■ Tarryho a Trémauxův algoritmus pro procházení labyrintu inspirovaly v r. 1973 Edmonse a Johnsona k formulaci vlastní metody procházení labyrintem. ■ Edmons-Johnsonův algoritmus slouží k nalezení průchodu labyrintem, přičemž každou chodbu (hranu) procházíme v obou směrech (tam i zpět). ■ Hlavní zásady algoritmu: O Každou hranou (chodbou) můžeme projít v jednom směru nejvýše jednou. B Po hraně, po které jsme do vrcholu přišli poprvé, se můžeme vracet pouze tehdy, nemáme-li jinou možnost. Q Z hran, které máme k odchodu z vrcholu k dispozici, upřednostňujeme tu hranu, kterou jsme dosud nikdy nešli. 28. 11. 2017 23 / 36 Edmons-Johnsonův algoritmus - principy O Označení chodby, kterou procházíme poprvé: ■ na jejím začátku vkládáme dvě značky •• ■ na jejím konci vkládáme Q jednu značku •, vede-li chodba k již navštívené křižovatce, B tři značky • • •, vede-li chodba k dosud nenavštívené křižovatce. Q Označení chodby, kterou procházíme podruhé (tj. jdeme v opačném směru): ■ na svém začátku má jednu značku •, ■ k této značce na začátku chodby přidáme druhou značku •. B Výběr chodby k procházení, jsme-li na křižovatce: ■ primárně vybíráme chodbu, která nemá značení; ■ pokud žádná taková neexistuje, vybereme chodbu s jednou značkou • na svém začátku; ■ není-li k dispozici chodba bez značení či s jednou značkou •, vybereme chodbu se třemi značkami • • •. 28. 11. 2017 24 / 36 Příklad 6.1 Mějme plánek města, v jehož ulicích (s chodníky na obou stranách) máme odklidit sníh. Pomocí Edmons-Johnsonova algoritmu najděte posloupnost orientovaných hran označujících průchod ulicemi při odklízení sněhu tam i zpět. Příklad 6.1 - několik zásad ■ Poprvé navštívenou chodbu budeme značit uspořádanou dvojicí (x,y), kde x je začátek chodby, y konec chodby. ■ Při druhém průchodu chodbou v opačném směru zapíšeme (y,x), čímž naznačíme, že už je sníh odklizen z obou chodníků ulice. ■ Máme-li více možností, jakou chodbou se vydat, respektujeme lexikografické (abecední) pravidlo. 28. 11. 2017 26 / 36 Příklad 6.1 - řešení Začínáme ve vrcholu a, s nímž sousedí vrcholy b,i. Lexikograficky je blíž b, vydáme se chodbou do b, přičemž na její začátek vložíme ••, na její konec • • jelikož křižovatku b jsme ještě nenavštívili. Navštívené chodby: 0 Aktuální chodba: (a, b) Příklad 6.1 - řešení V křižovatce b vybíráme chodbu, kterou půjdeme. Máme ještě k dispozici neoznačené chodby, takže vybereme "lexikograficky" hranu (b,d). Navštívené chodby: (a, b) Aktuální chodba: (b, d) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení Označíme chodbu (b, d), přičemž na její začátek vložíme ••, na její konec • • •, jelikož křižovatku d jsme ještě nenavštívili. Navštívené chodby: (a, b) Aktuální chodba: (b, d) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení V křižovatce d vybíráme chodbu, kterou půjdeme. Máme ještě k dispozici neoznačené chodby, takže vybereme "lexikograficky" hranu (c/, f). Navštívené chodby: (a, b); (b, d) Aktuální chodba: (c/? f) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení Ve dvou krocích projdeme hranami (c/, f)\ (f, e), jejich začátek označíme ••, konec • • •. Další hrana v pořadí je (e, b). Navštívené chodby: (a, b); (b, d) Aktuální chodba: (e, b) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení Označíme chodbu (e, b), přičemž na její začátek vložíme ••, na její konec pouze jelikož křižovatku d jsme již navštívili. Navštívené chodby: (a, b); (b, d)\ (c/, ŕ); (ŕ, e) Aktuální chodba: (e, b) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení V křižovatce b vybíráme chodbu, kterou půjdeme. Nemáme už k dispozici neoznačené chodby, vybereme tedy zpětnou hranu (b,e) s •. Navštívené chodby: (a, b); (b, d)\ (d, f)\ (ŕ, e); (e, b) Aktuální chodba: (b, e) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení Označíme chodbu (b,e), přičemž na její začátek doplníme • navíc, její konec necháme beze změny. Navštívené chodby: (a, b); (b, d); (d, f); (ŕ, e); (e, b) Aktuální chodba: (b, e) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení Ve dvou krocích projdeme zpětnými hranami (e,f); (f,d) a jejich značení ponecháme beze změny. Navštívené chodby: (a, b)\ (b, d)\(cř, f)\ (ŕ, e); (e, b); (b, e); (e, f); (f, d) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení V křižovatce d vybíráme chodbu, kterou půjdeme. Máme ještě k dispozici neoznačené chodby, takže vybereme "lexikograficky" hranu (d,g). Navštívené chodby: (a, b)\(b, d)\(d, f)\ (ŕ, e); (e, b)\ (b, e); (e, f); (f, d) Aktuální chodba: (d,g) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení Označíme chodbu (d,g), přičemž na její začátek vložíme ••, na její konec • • jelikož křižovatku g jsme ještě nenavštívili. Navštívené chodby: (a, b)\ (b, d)\(d, f)\ (ŕ, e); (e, b); (b, e); (e, f); (f, d) Aktuálni chodba: (c/, g) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení Označíme chodbu (g,j), přičemž na její začátek vložíme ••, na její konec • • •, jelikož křižovatku j jsme ještě nenavštívili. Navštívené chodby: (a, b); (b, d)\ (d, f); (f, e); (e, b); (b, e); (e, f); (f, d); (d,g); Aktuální chodba: (gj) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení V křižovatce j vybíráme chodbu, kterou půjdeme. Máme ještě k dispozici neoznačené chodby, takže vybereme "lexikograficky" hranu (j\d). Navštívené chodby: (a, b); (b, d); (d, f); (ŕ, e); (e, b); (b, e); (e, f); (f, d); (d, g)] (g J) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení Označíme chodbu (/, d), přičemž na její začátek vložíme ••, na její konec pouze jelikož křižovatku d jsme již navštívili. Navštívené chodby: (a, b); (b, d); (d, f); (ŕ, e); (e, b); (b, e); (e, f); (f, d); (d, g)] (g J) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení V křižovatce d vybíráme chodbu, kterou půjdeme. Máme ještě k dispozici neoznačenou chodbu (d,h). Navštívené chodby: (a, b); (b, d); {d7 f); (f, e); (e, b); (b, e); (e, f); (f, d); (d', g); {g, j)\(j', d) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení V několika krocích zpracujeme chodby (c/, h); (b, c); (c, /), na jejichž konci jsou neznámé vrcholy - dostaneme se až ke křižovatce /, u níž "lexikograficky" vybereme hranu (/, a). Navštívené chodby: (a, b); (b, d); (d, f); (ŕ, e); (e, b); (b, e); (e, f); (f, d) {d, g); (g, j); U, d); (d, h); (h, c); (c, i) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení Hranu (/, a) projdeme v jednom směru... Navštívené chodby: (a, b); (b, d); (d, f); (ŕ, e); (e, b); (b, e); (e, f); (f, d); {d, g); {g J); (y, d); (d, h); (/?, c); (c, /); (/, a) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení ...i ve zpětném směru. V křižovatce / vybíráme chodbu, kterou půjdeme. Máme ještě k dispozici neoznačenou chodbu (ij). Navštívené chodby: (a, b); (b, d); (d, f); (ŕ, e); (e, b); (b, e); (e, f); (f, d); {d, g); {g J); (y, d); (d, h); (/?, c); (c, /); (/, a); (a, i) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení Označíme chodbu (ij). V křižovatce j vybíráme chodbu, kterou půjdeme. Nemáme už k dispozici neoznačené chodby, vybereme tedy zpětnou hranu Navštívené chodby: (a, b); (b, d); (d, f); (ŕ, e); (e, b); (b, e); (e, f); (f, d); {d, g); {g J); (y, d); (d, h); (/?, c); (c, /); (/, a); (a, i); (i J) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení Označíme chodbu (j,i), na začátku přidáme •, protože pomocí ní přijdeme ke známé křižovatce /'. Navštívené chodby: (a, b); (b, d); (d, f); (f, e); (e, b); (b, e); (e, f); (f, d); (d,g); (g,j); (/', d); {d, h); (h, c); (c, /'); (/', a); (a, i); (j, i) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení V několika krocích zpracujeme chodby (i,c); (c, h); (h,d) a dostaneme se až ke křižovatce d, u níž vybereme hranu (d,j) s •. Navštívené chodby: (a, b); (b, d); (d, f); (f, e); (e, b); (b, e); (e, f); (f, d); (d, g); (g,j); (j, d)\ (d, /?); (h, c); (c, /'); (/', a); (a, i); (ij); (j, i); (i, c); (c, h); (h,d) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení Označíme chodbu (d, j), na začátku přidáme protože pomocí ní přijdeme ke známé křižovatce j. Navštívené chodby: (a, b); (b, d); (d, f); (ŕ, e); (e, b); (b, e); (e, f); (f, d); {d, g)\ {gj')] (y, d); (d, h); (/?, c); (c, /); (/, a); (a, i); (/J); (j, i); (i, c); (c, h) (h, d); (d J) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení Ve dvou krocích projdeme zpětnými hranami (j,g); (g,d) a jejich značení ponecháme beze změny. Navštívené chodby: (a, b)\ (b, d); (d, f); (f, e); (e, b); (b, e); (e, f); (f, d); (d, g)\(gj): (j, d)\(d, h); (h, c); (c, /); (/, a); (a, i); (ij); (j, i); (i, c); (c, h); (h,d);(d,j);(j,g);(g,d) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení Na křižovatce d už máme jedinou možnost, "zpětnou" chodbu (d,b) s • • • na začátku. Pouze jí projdeme ke křižovatce b. Navštívené chodby: (a, b); (b, d)\ (d, f)\ (ŕ, e); (e, b); (b, e); (e, f); (f, d); (d, g); (g J); (/, d)\{d, b); (b, c); (c, /); (/, a); (a, i); (i J); (j, i); (i, c); (c, h); (h, d); (dj); Q, g); (g, d); (d, b) 28. 11. 2017 27 / 36 Příklad 6.1 - řešení Dokončíme naší "pouť" průchodem chodby (b,a). Navštívené chodby: (a, b); (£», d); (d, f); (f, e); (e, b); (b, e); (e, f); (f, d); (d, g): (gj)\(i, d); {d, h); (h, c); (c, /'); (/', a); (a, i); (/', j); (j, i); (i, c); (c, h); (h,d);(d,j);(j,g);(g,d);(d,b);(b,a) 28. 11. 2017 27 / 36 Hledání zvonků se jménem Novák či Nováková Úloha Zvonky: Představme si, že máme k dispozici plánek určité městské části Brna (viz níže) a s jeho pomocí chceme projít všemi ulicemi a zjistit, přečtením jmen u zvonků každého domu, kolik se v městské části nachází domů, ve kterých bydlí Novákovi. 28. 11. 2017 28 / 36 Hledání pamětních desek na domech Úloha Pamětní desky: Mějme opět plánek stejné městské části Brna (viz níže) a s jeho pomocí chceme projít všemi ulicemi a zjistit, kolik se tam nachází domů s pamětní deskou informující o tom, že tam žil známý člověk. 28. 11. 2017 29 / 36 Jak obě úlohy řešit? □ Úlohu Zvonky řešíme pomocí algoritmů pro průchod labyrintem, protože ulice potřebujeme projít v obou směrech, abychom přečetli zvonky u každého domu. B Při řešení úlohy Pamětní desky stačí každou ulicí projít právě jednou - hledáme tedy v daném plánku eulerovský tah. 28. 11. 2017 30 / 36 Hledání eulerovského tahu ■ Když vhodně aplikujeme Edmons-Johnsonův algoritmus na eulerovský graf, můžeme pomocí něj najít eulerovský tah. ■ Zpětný průchod hranami při Edmons-Johnsonově algoritmu určuje eulerovský tah. ■ Je třeba využít datovou strukturu zásobník fungující na principu LIFO (Last In First Out). 28. 11. 2017 31 / 36 Princip algoritmu pro nalezení eulerovského tahu H Začneme v nějakém vrcholu x a modrou pastelkou kreslíme nějaký tah, dokud to jde. ■ Buď skončíme znovu ve vrcholu x a našli jsme uzavřený tah. ■ Nebo skončíme v jiném vrcholu y a našli jsme otevřený tah. ■ V obou případech zbylý "neobarvený" graf je sudý ^> existuje v něm uzavřený eulerovský tah. B Vracíme se zpět proti směru tahu a hrany označujeme červenou pastelkou, přičemž hledáme vrchol, ze kterého lze začít další tah, tj. uzel, který je incidentnís nějakou neobarvenou hranou. B Jakmile neobarvenou hranu najdeme, vybereme jí a pokračujeme krokem 1. □ Pokračujeme tak dlouho, dokud máme neobarvené hrany. 28. 11. 2017 32 / 36 Použití zásobníků ■ K uchovaní přesné informace o průběhu tahu nakresleného modrou pastelkou používáme zásobník Z, kam vkládáme každý vrchol, kterým modrý tah prochází. ■ Ke zpětné rekonstrukci zpětného průchodu nakresleného červeného pastelkou používáme zásobník ET, kam vkládáme každý vrchol, kterým zpětný červený průchod prochází. ■ Na začátku algoritmu je zásobník ET prázdný, zásobník Z obsahuje Q libovolně vybraný vrchol v, je-li eulerovský graf sudý. B jeden z vrcholů lichého stupně, obsahuje-li eulerovský graf právě dva uzly lichého stupně. ■ Provádíme-li zpětný průchod, kopírujeme uzel z vrcholu zásobníku Z na vrchol zásobníku ET. ■ Algoritmus končí v okamžiku, kdy je zásobník Z prázdný. V té chvíli je eulerovský tah "zaznamenán" na zásobníku ET. 28. 11. 2017 33 / 36 Nalezněte eulerovský tah v následujícím grafu. Při volbě následující hrany tahu uplatňujte lexikografické pravidlo Příklad 6.2 - řešení Nejdříve si připravíme zásobníky Z a ET. Začínáme ve vrcholu a a hledáme co nejdelší tah. Z: ET: 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Modrou barvou vyznačíme tah, přičemž veškeré vrcholy, které projdeme, vkládáme do zásobníku Z. Skončíme ve vrcholu a. b Z: c I a 12. ET: 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Ze zásobníku Z vezmeme vrchol a a vložíme jej do zásobníku ET. Nový vrchol zásobníku Z ukazuje, kam máme jít zpětnou hranou, kterou označíme červene, Z: f c Z a Í2. ET: □ i3 - 1 -O Q, O 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Modrou barvou vyznačíme tah z vrcholu /, přičemž veškeré vrcholy, které projdeme, vkládáme do zásobníku Z. Skončíme opět ve vrcholu /. Z: 4 c T a 3" Ď. ET: 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Ze zásobníku Z vezmeme vrchol / a vložíme jej do zásobníku ET. Nový vrchol zásobníku Z ukazuje, kam máme jít zpětnou hranou, kterou označíme červeně. 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Ze zásobníku Z vezmeme vrchol h a vložíme jej do zásobníku ET. Nový vrchol zásobníku Z ukazuje, kam máme jít zpětnou hranou, kterou označíme červeně. 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Ze zásobníku Z vezmeme vrchol j a vložíme jej do zásobníku ET. Nový vrchol zásobníku Z ukazuje, kam máme jít zpětnou hranou, kterou označíme červeně. 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Ze zásobníku Z vezmeme vrchol / a vložíme jej do zásobníku ET. Nový vrchol zásobníku Z ukazuje, kam máme jít zpětnou hranou, kterou označíme červeně. 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Ze zásobníku Z vezmeme vrchol f a vložíme jej do zásobníku ET. Nový vrchol zásobníku Z ukazuje, kam máme jít zpětnou hranou, kterou označíme červeně. 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Ze zásobníku Z vezmeme vrchol d a vložíme jej do zásobníku ET. Nový vrchol zásobníku Z ukazuje, kam máme jít zpětnou hranou, kterou označíme červene, Z: c Z a ET: Z / JU / □ 1 ► 1 -O o, O 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Modrou barvou vyznačíme tah z vrcholu c, přičemž veškeré vrcholy, které projdeme, vkládáme do zásobníku Z. Skončíme opět ve vrcholu c. Z: c 7 a 3" ET: / 7? X / 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Ze zásobníku Z vezmeme vrchol c a vložíme jej do zásobníku ET. Nový vrchol zásobníku Z ukazuje, kam máme jít zpětnou hranou, kterou označíme červeně. 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Ze zásobníku Z vezmeme vrchol g a vložíme jej do zásobníku ET. Nový vrchol zásobníku Z ukazuje, kam máme jít zpětnou hranou, kterou označíme červeně. 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Ze zásobníku Z vezmeme vrchol e a vložíme jej do zásobníku ET. Nový vrchol zásobníku Z ukazuje, kam máme jít zpětnou hranou, kterou označíme červeně. 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Ze zásobníku Z vezmeme vrchol c a vložíme jej do zásobníku ET. Nový vrchol zásobníku Z ukazuje, kam máme jít zpětnou hranou, kterou označíme červeně. 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Ze zásobníku Z vezmeme vrchol f a vložíme jej do zásobníku ET. Nový vrchol zásobníku Z ukazuje, kam máme jít zpětnou hranou, kterou označíme červene, Z: a Z ET: L í I JU / □ 13" 1 ► 1 -O Q, O 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Ze zásobníku Z vezmeme vrchol a a vložíme jej do zásobníku ET. Nový vrchol zásobníku Z ukazuje, kam máme jít zpětnou hranou, kterou označíme červene. Z: ET: i. ľ. í I / 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Ze zásobníku Z vezmeme vrchol d a vložíme jej do zásobníku ET. Nový vrchol zásobníku Z ukazuje, kam máme jít zpětnou hranou, kterou označíme červene. Z: Ď. ET: SL L ľ. í I JU / □ [S1 ► < -E ► < = 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Ze zásobníku Z vezmeme vrchol b a vložíme jej do zásobníku ET. Nový vrchol zásobníku Z ukazuje, kam máme jít zpětnou hranou, kterou označíme červene. Z: ET: SL L ľ. í I JU / 28. 11. 2017 35 / 36 Příklad 6.2 - řešení Ze zásobníku Z vezmeme vrchol a a vložíme jej do zásobníku ET. Zásobník Zje prázdný =4> algoritmus je u konce. Pomocí zásobníku ET zpětně zrekonstruujeme eulerovský tah. 28. 11. 2017 35 / 36 Použité zdroje ✓ _ MILKOVA, Eva. Teorie grafů a grafové algoritmy. 1. vyd. Hradec Králové: Nakladatelství Gaudeamus, 2013. 123 s. ISBN 978-80-7435-267-6. 28. 11. 2017 36 / 36