Matematika III - 8. přednáška Grafy a algoritmy - cesty a souvislost Michal Bulant Masarykova univerzita Fakulta informatiky 13. 11. 2007 Q Eulerovské grafy a hamiltonovské kružnice Q Stromy Q Rovinné grafy Platónská tělesa * Barvení map ˇ 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, http://www.fi.muni.cz/~hlineny/Vyuka/GT/ * Donald E. Knuth, The Stanford GraphBase, ACM, New York, 1993 (http://www-es-facuity.stanford.edu/~knuth/sgb.html). 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. 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. Graf G je eulerovský tehdy a jen tehdy když je souvislý a všechny vrcholy v G mají sudý stupeň. 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 Důsledek Graf lze nakreslit jedním tahem právě tehdy když má všechny stupně vrcholů sudé nebo když existují pravě dva vrcholy se stupněm lichým. Příklad Určete nejmenší počet mostů, které je třeba v Královci přistavět, aby byl graf eulerovský. 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é 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. Definice 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,Ě), kde E = Ux , y}; (x , y) e E nebo (y, x) G E}. 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ě. Poznámka Silně souvislý je takový orientovaný graf G, kde libovolné dva vrcholy lze spojit orientovanou cestou (a to v obou směrech). Problém čínského pošťáka (route inspection problem) 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ý. 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). 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). Příklad Existuje hamiltonovská kružnice v Petersenově grafu? 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 (I960)) 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 cl(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. Definice 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). Obecněji, 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. Charakterizace stromů Pro každý graf G = (V, E) jsou následující podmínky ekvivalentní Q G je strom; Q pro každé dva vrcholy v, w grafu G existuje právě jedna cesta z v do w; Q graf G je souvislý ale vyjmutím libovolné hrany vznikne nesouvislý graf O graf G neobsahuje kružnici, každým přidáním hrany do grafu G však již kružnice vznikne Q 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ů. Ke stromům se vrátíme později v souvislosti s praktickými aplikacemi. Velice často se setkáváme s grafy, které jsou nakresleny v rovině. To znamená, že každý vrchol grafu je ztotožněn s nějakým bodem v rovině a hrany mezi vrcholy v a w odpovídají spojitým křivkám c : [0,1] --> R2 spojujícím vrcholy c(0) = v a c(l) = w. Pokud navíc platí, že se jednotlivé dvojice hran protínají nejvýše v koncových vrcholech, pak hovoříme o rovinném grafu G. Otázka, jestli daný graf připouští realizaci (nakreslení) jako rovinný graf, vyvstává velice často v aplikacích. Jednoduchý příklad je následující: Tři dodavatelé vody, elektřiny a plynu mají každý své jedno přípojné místo v blízkosti tří rodinných domků. Chtějí je všichni napojit tak, aby se jejich sítě nekřížily (třeba se jim nechce kopat příliš hluboko...). Je to možné zvládnout? Odpověď zní ,,není". Jde o bipartitní úplný graf K33, kde tři vrcholy představují přípojná místa, další tři pak domky. Hrany jsou linie sítí. Všechny hrany umíme zvládnout, jedna poslední ale už nejde, viz obrázek na kterém neumíme čárkovanou hranu nakreslit bez křížení: Obecně se dá ukázat tzv. Kuratowského věta: Jedna implikace je zřejmá - dělením rovinného grafu vzniká vždy opět rovinný graf a jestliže podgraf nelze v rovině nakreslit bez křížení, totéž musí platit i pro celý graf G. Opačný směr důkazu je naopak velice složitý a nebudeme se jím zde zabývat. Problematice rovinných grafů je věnováno ve výzkumu a aplikacích hodně pozornosti, my se zde omezíme pouze na vybrané ilustrace. Zmiňme alespoň naokraj, že existují algoritmy, které testují rovinnost grafu na n vrcholech v čase 0{rí), což určitě nejde přímou aplikací Kuratowského věty. Uvažme (konečný) rovinný graf G, včetně jeho nakreslení v R2 a nechť S je množina všech bodů x G R2 , které nepatří žádné hraně, ani nejsou vrcholem. Množina R2 \ G se rozpadne na disjunktní souvislé podmnožiny S,, kterým říkáme stěny rovinného grafu G. Jedna stěna je výjimečná - ta jejíž doplněk obsahuje všechny vrcholy grafu. Budeme jí říkat neohraničená stěna So. Množinu všech stěn budeme označovat S = {So, S i , . . . , Sk} a rovinný graf G = (V,E,S). Jako příklad si můžme rozebrat stromy. Každý strom je zjevně rovinný graf, jak je vidět například z možnosti realizovat jej postupným přidáváním listů k jedinému vrcholu. Samozřejmě také můžeme použít Kuratowského větu - když není v G žádná kružnice, nemůže obsahovat jakékoliv dělení grafů K33 nebo K5. Protože strom G neobsahuje žádnou kružnici, dostáváme pouze jedinou stěnu So a to tu neohraničenou. Protože víme, jaký je poměr mezi počty vrcholů a hran pro všechny stromy, dostáváme vztah IVI - l E I + ISI = 2 . Vztah mezi počty hran, stěn a vrcholů lze odvodit pro všechny rovinné grafy. Jde o tzv. Eulerův vztah. Všimněme si, že z něho zejména vyplývá, že počet stěn v rovinném grafu nezávisí na způsobu, jaké jeho rovinné nakreslení vybereme. Indukcí podle počtu hran. Rovinné grafy si můžeme dobře představit jako namalované na povrchu koule místo v rovině. Sféra vznikne z roviny tak, že přidáme jeden bod ,,v nekonečnu". Opět můžeme stejným způsobem hvořit o stěnách a pro takovýto graf pak jsou všechny jeho stěny rovnocenné (i stěna So je ohraničená). Naopak, každý konvexní mnohostěn P C M3 si můžeme představit jako graf nakreslený na povrchu koule. Vypuštěním jednoho bodu uvnitř jedné ze stěn (ta stane neohraničenou stěnou So) pak obdržíme rovinný graf jako výše. Rovinné grafy, které vzniknou z konvexních mnohostěnů, jsou zjevně 2-souvislé, protože každé dva vrcholy v konvexním mnohoúhelníku leží na společné kružnici. Navíc v nich platí, že každá stěna kromě So je vnitřkem nějaké kružnice a So je vnějškem nějaké kružnice. Názorné se zdá i to, že ve skutečnosti budou grafy vznikající z konvexních mnohoúhelníků 3-souvislé. Ve skutečnosti platí dosti náročná Steinitzova věta: Jako ilustraci kombinatorické práce s grafy odvodíme klasifikaci tzv. pravidelních mnohostěnů, tj. mnohostěnů poskládaných ze stejných pravidlných mnohoúhelníků tak, že se jich v každém vrcholu dotýká stejný počet. Již v dobách antického myslitele Platóna se vědělo, že jich je pouze pět: Přeložíme si požadavek pravidelnosti do vlastností příslušného grafu: chceme aby každý vrchol měl stejný stupeň d > 3 a zároveň aby na hranici každé stěny byl stejný počet k > 3 vrcholů. Označme n počet vrcholů, e počet hran a s počet stěn. Máme k dispozici jednak vztah provazující stupně vrcholů s počtem hran: dn = 2e a podobně počítáme počet hran, které ohraničují jednotlivé stěny, a bereme v úvahu, že každá je hranicí dvou stěn, tj. 2e = ks. Eulerův vztah pak říká 2 = n e + s 2e2e Úpravou odtud dostáváme pro naše známé d a k vztah 1 1 -d + ~k 1 1 2 + ě - Protože e a n musí být přirozená čísla (tj. zejména je ^ > 0) a minimum pro d i k je 3, dostáváme přímou diskusí všech možností tento výčet: d k n e s 3 3 4 6 4 3 4 8 12 6 4 3 6 12 8 3 5 20 30 12 5 3 12 30 20 Tabulka zadává všechny možnosti. Ve skutečnosti ale také všechny odpovídající pravidelné mnohostěny existují - již jsme je viděli. Maximální počet hran Nechť (V, E, S) je rovinný graf s aspoň třemi vrcholy. Pak \E\ <3\V\ - 6 . Rovnost přitom nastává pro maximální rovinný graf tj. rovinný graf k němuž nejde při zachování rovinnosti přidat žádnou hranu. Pokud navíc uvažovaný graf neobsahuje trojúhelník (tj. K3 jako podgraf), platí dokonce \E\ < 2\V\ --4. Maximální rovinný graf má všechny stěny ohraničené kružnicí délky 3, z čehož plyne 3|S| = 2|| a odtud již pomocí Eulerova vztahu dostáváme první tvrzení. Podobně v druhé části. D Důsledek * Ks není rovinný; 9 /C3 3 není rovinný; 9 každý rovinný graf obsahuje alespoň jeden vrchol stupně nejvýše 5; * každý rovinný graf bez trojúhelníků obsahuje alespoň jeden vrchol stupně nejvýše 3. Problém čtyř barev Jedním z nejznámějších kombinatorických problémů je otázka: Je možné každou mapu obarvit 4 barvami? Tento problém sice na první pohled vypadá ryze geometricky, ale dá se přeformulovat do kombinatorické podoby. Definice Mapou nazýváme souvislý rovinný multigraf bez mostů. Normální mapou pak mapu, jejíž všechny vrcholy jsou stupně 3. Obarvení mapy je funkce, která každé stěně mapy přiřadí číslo (barvu). Problém čtyř barev byl rozřešen teprve po více než sto letech bádání - mnoho matematiků na prezentovaný důkaz stále pohlíží s despektem, protože je založen na prověření velkého množství případů pomocí počítače. Elementárními kombinatorickými prostředky je možné alespoň dokázat možnost obarvení normálních map pěti barvami -viz literatura.