Eulerovské grafy a hamiltonovské kružnice ooooooooooo Stromy oo Matematika III - 10. přednáška Eulerovské grafy a Hamiltonovské kružnice, stromy, rovinné grafy Michal Bulant Masarykova univerzita Fakulta informatiky 21. 11. 2012 Euleravské grafy a hamiltonovské kružnice ooooooooooo Stromy OO Obsah přednášky Q Eulerovské grafy a hamiltonovské kružnice Q Stromy Eulerovské grafy a hamiltonovské kružnice Stromy OOOOOOOOOOO OO EBS2S • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové záložky v IS MU Eulerovské grafy a fiamiltonovské kružnice ooooooooooo EBS2S Stromy oo • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové záložky v IS MU • Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. • Petr Hliněný, Teorie grafů, studijní materiály, https://is. muni.cz/auth/el/1433/podzim2012/MA010/index.qwarp Eulerovské grafy a hamiltonovské kružnice ooooooooooo IS Stromy oo • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové záložky v IS MU • Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. • Petr Hliněný, Teorie grafů, studijní materiály, https://is. muni.cz/auth/el/1433/podzim2012/MA010/index.qwarp • Donald E. Knuth, The Stanford GraphBase, ACM, New York, 1993 (http://www-cs-facuity.Stanford.edu/-knuth/sgb.html). Eulerovské grafy a hamiltonovské kružnice ooooooooooo IS Stromy oo • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové záložky v IS MU • Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. • Petr Hliněný, Teorie grafů, studijní materiály, https://is. muni.cz/auth/el/1433/podzim2012/MA010/index.qwarp • Donald E. Knuth, The Stanford GraphBase, ACM, New York, 1993 (http://www-cs-facuity.Stanford.edu/-knuth/sgb.html). Eulerovské grafy a hamiltonovské kružnice ooooooooooo Stromy OO Plán přednášky Q Eulerovské grafy a hamiltonovské kružnice Q| Stromy Eulerovské grafy a hamiltonovské kružnice •oooooooooo Stromy OO Grafy jedním tahem Jistě se každý setkal s dětskou hříčkou Nakresli obrázek jedním tahem. V řeči grafů to znamená najděte sled, který projde všechny hrany právě jednou a každý vrchol alespoň jednou. Eulerovské grafy a hamiltonovské kružnice •oooooooooo Stromy OO Grafy jedním tahem Jistě se každý setkal s dětskou hříčkou Nakresli obrázek jedním tahem. V řeči grafů to znamená najděte sled, který projde všechny hrany právě jednou a každý vrchol alespoň jednou. Definice Sled, který prochází právě jednou všemi hranami a začíná a končí v jednom vrcholu, se nazývá uzavřený eulerovský tah. Grafům, které takový sled připouští říkáme eulerovské. Hovoříme rovněž o (neuzavřeném) eulerovském tahu, kde vypouštíme požadavek na stejný výchozí a cílový vrchol. Eulerovské grafy a hamiltonovské kružnice o»ooooooooo Stromy oo Terminologie odkazuje na klasický příběh o sedmi mostech ve městě Královec (Königsberg, tj. Kaliningrad), které se měly projít na procházce každý právě jednou a důkaz nemožnosti takové procházky od Leonharda Eulera z roku 1736. Eulerovské grafy a hamiltonovské kružnice Stromy o»ooooooooo oo Terminologie odkazuje na klasický příběh o sedmi mostech ve městě Královec (Königsberg, tj. Kaliningrad), které se měly projít na procházce každý právě jednou a důkaz nemožnosti takové procházky od Leonharda Eulera z roku 1736. Situace je znázorněna na obrázku. Nalevo dobová mapa, napravo odpovídající (multi)graf. Vrcholy tohoto grafu odpovídají „souvislé pevnině", hrany mostům. Kupodivu je obecné řešení takového problému dosti snadné, jak ukazuje následující věta. Samozřejmě také ukazuje, že se Euler zamýšleným způsobem procházet nemohl. Eulerovské grafy a hamiltonovské kružnice oo»oooooooo Stromy oo Kupodivu je obecné řešení takového problému dosti snadné, jak ukazuje následující věta. Samozřejmě také ukazuje, že se Euler zamýšleným způsobem procházet nemohl. Věta Graf G je eulerovský tehdy a jen tehdy, když je souvislý a všechny vrcholy v G mají sudý stupeň. Důkaz. Podmínka je zřejmě nutná. Eulerovské grafy a hamiltonovské kružnice Stromy oo»oooooooo oo Kupodivu je obecné řešení takového problému dosti snadné, jak ukazuje následující věta. Samozřejmě také ukazuje, že se Euler zamýšleným způsobem procházet nemohl. ' Věta * Graf G je eulerovský tehdy a jen tehdy, když je souvislý a všechny vrcholy v G mají sudý stupeň. Důkaz._1 Podmínka je zřejmě nutná. Dostatečnost podmínky se ukáže sporem uvážením tahu v G maximální možné délky. □ Eulerovské grafy a hamiltonovské kružnice Stromy oo»oooooooo oo Kupodivu je obecné řešení takového problému dosti snadné, jak ukazuje následující věta. Samozřejmě také ukazuje, že se Euler zamýšleným způsobem procházet nemohl. Věta Graf G je eulerovský tehdy a jen tehdy když je souvislý a všechny vrcholy v G mají sudý stupeň. Důkaz. Podmínka je zřejmě nutná. Dostatečnost podmínky se ukáže sporem uvážením tahu v G maximální možné délky. □ Důsledek Graf lze nakreslit jedním tahem právě tehdy když má všechny stupně vrcholů sudé nebo když existují právě dva vrcholy se stupněm lichým. Eulerovské grafy a hamiltonovské kružnice Stromy ooo#ooooooo oo Příklad O Určete nejmenší počet mostů, které je třeba v Královci přistavět, aby byl graf eulerovský. Q Jaká je situace v Kaliningradu nyní (od dob Eulerových doznalo zejména působením válek město mnoho změn)? Byl by dnes schopen Euler svoji procházku realizovat? Eulerovské grafy a hamiltonovské kružnice oooo»oooooo Stromy OO Eulerovské orientované grafy Definice Orientovaný graf (V, E) nazveme eulerovský, jestliže v něm existuje uzavřený orientovaný tah, který obsahuje každou hranu právě jednou a každý vrchol aspoň jednou. Orientované eulerovské grafy lze rovněž velmi dobře charakterizovat. K tomu ovšem potřebujeme některé nové pojmy. Orientovaný graf nazveme vyvážený, jestliže pro každý jeho vrchol v platí deg+(v) = deg_(v). Symetrizacíorientovaného grafu (V, E) nazýváme neorientovaný graf (V,T), kde E = Ux'y}; (x>y)£f nebo (y,x) e £}■ Eulerovské grafy a fiamiltonovské kružnice ooooo»ooooo Stromy oo Věta Orientovaný graf G je eulerovský právě když je vyvážený a jeho symetrizace je souvislý graf (tj. graf G je slabě souvislý). Důkaz. Analogický jako v neorientovaném případě. Eulerovské grafy a hamiltonovské kružnice oooooo^oooo I i Problém čínského Stromy oo Route inspection problem je zobecněním problému nalezení eulerovského tahu. Úkolem je nalézt nejkratší sled v grafu s ohodnocenými hranami, který obsahuje každou hranu v grafu. Tento problém má v současnosti mnoho praktického využití (analýza DNA, směrování robotů, svoz odpadu, ...). Eulerovské grafy a fiamiltonovské kružnice oooooo^oooo I i Problém čínského Stromy oo Route inspection problem je zobecněním problému nalezení eulerovského tahu. Úkolem je nalézt nejkratší sled v grafu s ohodnocenými hranami, který obsahuje každou hranu v grafu. Tento problém má v současnosti mnoho praktického využití (analýza DNA, směrování robotů, svoz odpadu, ...). Zřejmě je v případě, že graf G je eulerovský, nejkratším takovým sledem příslušný eulerovský tah. Eulerovské grafy a fiamiltonovské kružnice oooooo^oooo I i Problém čínského Stromy oo Route inspection problem je zobecněním problému nalezení eulerovského tahu. Úkolem je nalézt nejkratší sled v grafu s ohodnocenými hranami, který obsahuje každou hranu v grafu. Tento problém má v současnosti mnoho praktického využití (analýza DNA, směrování robotů, svoz odpadu, ...). Zřejmě je v případě, že graf G je eulerovský, nejkratším takovým sledem příslušný eulerovský tah. V opačném případě nutně graf obsahuje sudý počet vrcholů lichého stupně. Tento graf je třeba přidáváním hran doplnit na eulerovský (multi)graf (později ukážeme, že v případě stromů to znamená nutnost zdvojení všech hran). Snadno lze ukázat, že to lze udělat v polynomiálním čase jak v orientovaném, tak neorientovaném případě, v případě multigrafů je to však problém NP-úplný. Eulerovské grafy a hamiltonovské kružnice Stromy ooooooo»ooo oo Hamiltonovské grafy Obdobný požadavek na průchod grafem, ovšem tak, abychom prošli právě jednou každým vrcholem (tj. zároveň nejvýše jednou každou hranou), vede na obtížné problémy. Takový průchod grafem je realizován kružnicí, která obsahuje všechny vrcholy grafu G, hovoříme o hamiltonovských kružnicích v grafu G. Graf se nazývá hamiltonovský, jestliže má hamiltonovskou kružnici. Eulerovské grafy a hamiltonovské kružnice Stromy ooooooo»ooo oo Hamiltonovské grafy Obdobný požadavek na průchod grafem, ovšem tak, abychom prošli právě jednou každým vrcholem (tj. zároveň nejvýše jednou každou hranou), vede na obtížné problémy. Takový průchod grafem je realizován kružnicí, která obsahuje všechny vrcholy grafu G, hovoříme o hamiltonovských kružnicích v grafu G. Graf se nazývá hamiltonovský, jestliže má hamiltonovskou kružnici. Zatímco (zdánlivě podobně složitý) problém nalezení eulerovského tahu je triviální, zjistit, zda je daný graf hamiltonovský, je NP-úplný problém. Eulerovské grafy a hamiltonovské kružnice Stromy ooooooo»ooo oo Hamiltonovské grafy Obdobný požadavek na průchod grafem, ovšem tak, abychom prošli právě jednou každým vrcholem (tj. zároveň nejvýše jednou každou hranou), vede na obtížné problémy. Takový průchod grafem je realizován kružnicí, která obsahuje všechny vrcholy grafu G, hovoříme o hamiltonovských kružnicích v grafu G. Graf se nazývá hamiltonovský, jestliže má hamiltonovskou kružnici. Zatímco (zdánlivě podobně složitý) problém nalezení eulerovského tahu je triviální, zjistit, zda je daný graf hamiltonovský, je NP-úplný problém. V praxi je ovšem problém nalezení hamiltonovské kružnice (či jeho modifikace - např. problém obchodního cestujícího) podstatou mnoha problémů v logistice, je proto často žádoucí nalezení i suboptimálního řešení (v případě problému obchodního cestujícího). Eulerovské grafy a hamiltonovské kružnice oooooooo»oo Stromy oo Příklad (Icosian Game - William Rovan Hamilton) Nalezněte hamiltonovskou kružnici v grafu tvořeném vrcholy a hranami pravidelného dodekaedru (dvanáctistěnu) - viz http:// www.puzzlemuseum.com/month/picm02/200201hamilton.jpg Příklad Existuje hamiltonovská kružnice v Petersenově grafu? Eulerovské grafy a hamiltonovské kružnice oooooooo»oo Stromy oo Příklad (Icosian Game - William Rovan Hamilton) Nalezněte hamiltonovskou kružnici v grafu tvořeném vrcholy a hranami pravidelného dodekaedru (dvanáctistěnu) - viz http:// www.puzzlemuseum.com/month/picm02/200201hamilton.jpg Příklad Existuje hamiltonovská kružnice v Petersenově grafu? Řešení Neexistuje (přitom ale po odebrání libovolného vrcholu již graf hamiltonovský bude). Ukáže se to např. tak, že se popíší všechny 3-regulární grafy na 10 vrcholech, které jsou hamiltonovské a v každém se nalezne kružnice kratší než 5. Eulerovské grafy a fiamiltonovské kružnice ooooooooo»o Stromy oo Věta (Dirac (1952)) Má-li v grafu G s n > 3 vrcholy každý vrchol stupeň alespoň n/2, je G hamiltonovský. Věta (Ore (1960)) Má-li v grafu G s n > 4 vrcholy každá dvojice nesousedních vrcholů součet stupňů alespoň n, je G hamiltonovský. Uzávěrem grafu G v této souvislosti rozumíme graf c/(G), který dostaneme z G přidáním všech hran u, v takových, že u, v nejsou sousední a deg(u) + deg(v) > n. Eulerovské grafy a hamiltonovské kružnice Stromy OOOOOOOOOO* oo Uzávěrem grafu G v této souvislosti rozumíme graf c/(G), který dostaneme z G přidáním všech hran u, v takových, že u, v nejsou sousední a deg(u) + deg(v) > n. Věta (BondyChvátal (1972)) Graf G je hamiltonovský, právě když je cl(G) hamiltonovský. Eulerovské grafy a hamiltonovské kružnice OOOOOOOOOO* Stromy oo Uzávěrem grafu G v této souvislosti rozumíme graf c/(G), který dostaneme z G přidáním všech hran u, v takových, že u, v nejsou sousední a deg(u) + deg(v) > n. Věta (Bondy,Chvátal (1972)) Graf G je hamiltonovský, právě když je cl(G) hamiltonovský. Je vidět, že Oreho (a tedy i Diracova) věta je triviálním důsledkem této věty. Eulerovské grafy a hamiltonovské kružnice OOOOOOOOOO* Stromy oo Uzávěrem grafu G v této souvislosti rozumíme graf c/(G), který dostaneme z G přidáním všech hran u, v takových, že u, v nejsou sousední a deg(u) + deg(v) > n. Věta (Bondy,Chvátal (1972)) Graf G je hamiltonovský, právě když je cl(G) hamiltonovský. Je vidět, že Oreho (a tedy i Diracova) věta je triviálním důsledkem této věty. Důkaz. Zřejmě stačí dokázat, že pokud je G hamiltonovský po přidání hrany {u, v} takové, že u, v nejsou sousední a deg(u) + deg(v) > n, pak je hamiltonovský i bez této hrany. Předpokládejme, že G + uv je hamiltonovský a G nikoliv. Pak existuje hamiltonovská cesta v G z u do v. Pro každý vrchol sousedící s u platí, že jeho předchůdce na této cestě nemůže sousedit s v (jinak bychom měli hamiltonovskou kružnici v G). Tedy deg(u) + deg(v) < n — 1. □ ■0 0.O Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooooo OO Plán přednášky Q Eulerovské grafy a hamiltonovské kružnice Q Stromy Souvislý graf neobsahující kružnici, se nazývá strom. Obecně v grafech nazýváme vrcholy stupně jedna listy (případně také koncové vrcholy). Graf neobsahující kružnice nazýváme les. Tato definice nicméně není úplně nejvhodnější pro praktickou kontrolu - uvedeme proto za chvíli hned 5 ekvivalentních definic. Následující lemma ukazuje, že každý strom lze vybudovat postupně z jediného vrcholu přidáváním listů: Eulerovské grafy a hamiltonovské kružnice ooooooooooo Stromy •O Souvislý graf neobsahující kružnici, se nazývá strom. Obecně v grafech nazýváme vrcholy stupně jedna listy (případně také koncové vrcholy). Graf neobsahující kružnice nazýváme les. Tato definice nicméně není úplně nejvhodnější pro praktickou kontrolu - uvedeme proto za chvíli hned 5 ekvivalentních definic. Následující lemma ukazuje, že každý strom lze vybudovat postupně z jediného vrcholu přidáváním listů: Lemma Každý strom s alespoň dvěma vrcholy obsahuje alespoň dva listy. Pro libovolný graf G s listem v jsou následující tvrzení ekvivalentní: • G je strom; • G \{v} je strom. ■0 0.0 Eulerovské grafy a hamiltonovské kružnice ooooooooooo Charakte Stromy O* Věta Pro každý graf G = (V, E) jsou následující podmínky ekvivalentní & G je strom; 0 pro každé dva vrcholy v, w grafu G existuje právě jedna cesta z v do w; O graf G je souvislý, ale vyjmutím libovolné hrany vznikne nesouvislý graf Q graf G neobsahuje kružnici, každým přidáním hrany do grafu G však již kružnice vznikne 0 G je souvislý graf a mezi velikostí množin jeho vrcholů a hran platí vztah (Eulerův vzorec) \ V\ = \ E\ + 1. « Důkaz jednotlivých implikací obvykle vedeme indukcí podle počtu vrcholů s využitím lemmatu o výstavbě stromů.