Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy ooooooooooo Matematika III - 9. přednáška Hamiltonovské kružnice, stromy, rovinné grafy Michal Bulant Masarykova univerzita Fakulta informatiky 24. 11. 2010 Eulerovské grafy a hamiltonovské kružnice Obsah přednášky Stromy ooooooooo Rovinné grafy ooooooooooo Q Eulerovské grafy a hamiltonovské kružnice Q Stromy • Izomorfismy stromů Q Rovinné grafy 9 Platónská tělesa • Barvení map Eulerovské grafy a hamiltonovské kružnice Stromy Rovinné grafy ooooooooo ooooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové záložky v IS MU Eulerovské grafy a hamiltonovské kružnice Doporučené zdroje Stromy ooooooooo Rovinné grafy ooooooooooo • 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.f i. muni.cz/~hlineny/Vyuka/GT/ Eulerovské grafy a hamiltonovské kružnice Doporučené zdroje Stromy ooooooooo Rovinné grafy ooooooooooo • 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.f i. muni.cz/~hlineny/Vyuka/GT/ • 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 Doporučené zdroje Stromy ooooooooo Rovinné grafy ooooooooooo • 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.f i. muni.cz/~hlineny/Vyuka/GT/ • 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 Plán přednášky Stromy ooooooooo Rovinné grafy ooooooooooo Eulerovské grafy a hamiltonovské kružnice a Izomorfismy stromů 0 Rovinné grafy • Platónská tělesa 9 Barvení map Eulerovské grafy a hamiltonovské kružnice Stromy Rovinné grafy ooooooooo ooooooooooo Eulerovské grafy - opakování Věta Graf G je eulerovský tehdy a jen tehdy, když je souvislý a všechny vrcholy v G mají sudý stupeň. Eulerovské grafy a hamiltonovské kružnice Stromy Rovinné grafy ooooooooo ooooooooooo Eulerovské grafy - opakování Věta Graf G je eulerovský tehdy a jen tehdy když je souvislý a všechny vrcholy v G mají sudý stupeň. 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. 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ý). Eulerovské grafy a hamiltonovské kružnice Stromy Rovinné grafy ooooooooo ooooooooooo 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, ...). Eulerovské grafy a hamiltonovské kružnice Stromy Rovinné grafy ooooooooo ooooooooooo 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. Eulerovské grafy a hamiltonovské kružnice Stromy Rovinné grafy ooooooooo ooooooooooo 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ý. Eulerovské grafy a hamiltonovské kružnice Stromy Rovinné grafy ooooooooo ooooooooooo 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 Rovinné grafy ooooooooo ooooooooooo 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 Rovinné grafy ooooooooo ooooooooooo 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 Stromy ooooooooo Rovinné grafy ooooooooooo 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 Stromy ooooooooo Rovinné grafy ooooooooooo 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? 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ý. Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy ooooooooooo 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(i/) > n. Eulerovské grafy a hamiltono ■vské kružnice Stromy Rovinné grafy ooooooooo ooooooooooo 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(i/) > n. Věta (Bondy,Chvátal (1972)) Graf G je hamiltonovský, právě když je c/(G) hamiltonovský. Eulerovské grafy a hamiltono ■vské kružnice Stromy Rovinné grafy ooooooooo ooooooooooo 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(i/) > n. Věta (Bondy,Chvátal (1972)) Graf G je hamiltonovský, právě když je c/(G) hamiltonovský. Je vidět, že Oreho (a tedy i Diracova) věta je jednoduchým důsledkem této věty. Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy ooooooooooo 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(i/) > n. Věta (Bondy,Chvátal (1972)) Graf G je hamiltonovský, právě když je c/(G) hamiltonovský. Je vidět, že Oreho (a tedy i Diracova) věta je jednoduchý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(i/) > 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. □ Eulerovské grafy a hamiltonovské kružnice Plán přednášky Stromy ooooooooo Rovinné grafy ooooooooooo Q Eulerovské grafy a har Q Stromy • Izomorfismy stromů • Platónská tělesa » Barvení map Eulerovské grafy a hamiltonovské kružnice Stromy Rovinné grafy ooooooooo ooooooooooo Stromy 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). 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ů: 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). 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í: 9 G je strom; • G \v je strom. Eulerovské grafy a hamiltonovské kružnice Stromy Rovinné grafy ooooooooo ooooooooooo Charakterizace stromů Věta Pro každý graf G = (V, E) jsou následující podmínky ekvivalentní O G je strom; O 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 Q 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ů. ■O O. o- Eulerovské grafy a hamiltonovské kružnice Stromy •oooooooo Rovinné grafy ooooooooooo Stromy jako datové struktury Stromy se často používají jako (acyklické) datové struktury, v praxi stromy procházíme v určitém pořadí vrcholů - narozdíl od grafů k jednoznačnému určení nějakého uspořádání vrcholů stačí vybrat jeden vrchol - kořen (root) vr. Ve stromu není žádná kružnice, proto volba jednoho vrcholu vr zadává orientaci všech hran. Eulerovské grafy a hamiltonovské kružnice Stromy Rovinné grafy •oooooooo ooooooooooo Stromy jako datové struktury Stromy se často používají jako (acyklické) datové struktury, v praxi stromy procházíme v určitém pořadí vrcholů - narozdíl od grafů k jednoznačnému určení nějakého uspořádání vrcholů stačí vybrat jeden vrchol - kořen (root) vr. Ve stromu není žádná kružnice, proto volba jednoho vrcholu vr zadává orientaci všech hran. Po výběru kořenu se začíná graf více podobat skutečnému stromu v přírodě. Stromy s jedním vybraným kořenem nazýváme kořenové stromy. Eulerovské grafy a hamiltonovské kružnice Stromy Rovinné grafy •oooooooo ooooooooooo Stromy jako datové struktury Stromy se často používají jako (acyklické) datové struktury, v praxi stromy procházíme v určitém pořadí vrcholů - narozdíl od grafů k jednoznačnému určení nějakého uspořádání vrcholů stačí vybrat jeden vrchol - kořen (root) vr. Ve stromu není žádná kružnice, proto volba jednoho vrcholu vr zadává orientaci všech hran. Po výběru kořenu se začíná graf více podobat skutečnému stromu v přírodě. Stromy s jedním vybraným kořenem nazýváme kořenové stromy. Definice V kořenovém stromu T = (V, E) je vrchol w je následník vrcholu v a naopak i/je předchůdce vrcholu w právě tehdy, když existuje cesta z kořene stromu do w která prochází v a v ^ w. Přímý následník a přímý předchůdce vrcholu jsou pak následníci a předchůdci přímo spojení hranou. Mluvíme také o synech a otcích (patrně v narážce na genealogické stromy). Eulerovské grafy a hamiltonovské kružnice Stromy o«ooooooo Rovinné grafy OOOOOOOOOOO* Definice Binární stromy jsou speciálním případem kořenového stromu, kdy každý otec má nejvýše dva následníky (někdy se ale pod stejným označením binární strom předpokládá, že všechny vrcholy kromě listů mají právě dva následníky). Eulerovské grafy a hamiltonovské kružnice Stromy o«ooooooo Rovinné grafy ooooooooooo Definice Binární stromy jsou speciálním případem kořenového stromu, kdy každý otec má nejvýše dva následníky (někdy se ale pod stejným označením binární strom předpokládá, že všechny vrcholy kromě listů mají právě dva následníky). Často jsou vrcholy stromu spojeny s klíči v nějaké úplně uspořádané množině (např. reálná čísla) a slouží k hledání vrcholu s daným klíčem. Je realizováno jako hledání cesty od kořene stromu a v každém vrcholu se podle velikosti rozhodujeme, do kterého ze synů budeme pokračovat (resp. zastavíme hledání, pokud jsme již ve hledaném vrcholu). Abychom mohli tuto cestu jednoznačně krok po kroku určovat, požadujeme aby jeden syn společně se všemi jeho následníky měli menší klíce než druhý syn a všichni jeho následníci. Eulerovské grafy a hamiltonc vské kružnice Stromy Rovinné grafy OO0OOOOOO ooooooooooo Pro efektivní vyhledávání užíváme vyvážené binární stromy, ve kterých se délky cest z kořene do listů liší maximálně o jedničku. Eulerovské grafy a hamiltonovské kružnice Stromy OO0OOOOOO Rovinné grafy ooooooooooo Pro efektivní vyhledávání užíváme vyvážené binární stromy, ve kterých se délky cest z kořene do listů liší maximálně o jedničku. Nejdále od vyváženého stromu na n vrcholech je tedy cesta Pn (která formálně může být považována za binární strom), zatímco dokonale vyvážený strom, kde kromě listů má každý otec právě dva syny je možné sestrojit pouze pro hodnoty n = 2k — 1, k = 1,2,.... Eulerovské grafy a hamiltonovské kružnice Stromy OO0OOOOOO Rovinné grafy ooooooooooo* Pro efektivní vyhledávání užíváme vyvážené binární stromy, ve kterých se délky cest z kořene do listů liší maximálně o jedničku. Nejdále od vyváženého stromu na n vrcholech je tedy cesta Pn (která formálně může být považována za binární strom), zatímco dokonale vyvážený strom, kde kromě listů má každý otec právě dva syny je možné sestrojit pouze pro hodnoty n = 2k — 1, k = 1,2,.... Ve vyvážených stromech dohledání vrcholu podle klíče bude vždy vyžadovat pouze O(log2 n) kroků. Hovoříme v této souvislosti také často o binárních vyhledávacích stromech. Eulerovské grafy a hamiltonovské kružnice Stromy OO0OOOOOO Rovinné grafy ooooooooooo Pro efektivní vyhledávání užíváme vyvážené binární stromy, ve kterých se délky cest z kořene do listů liší maximálně o jedničku. Nejdále od vyváženého stromu na n vrcholech je tedy cesta Pn (která formálně může být považována za binární strom), zatímco dokonale vyvážený strom, kde kromě listů má každý otec právě dva syny je možné sestrojit pouze pro hodnoty n = 2k — 1, k = 1,2,.... Ve vyvážených stromech dohledání vrcholu podle klíče bude vždy vyžadovat pouze O(log2 n) kroků. Hovoříme v této souvislosti také často o binárních vyhledávacích stromech. Jako cvičení si rozvažte, jak lze účinně vykonávat základní operace s grafy (přidávání a odebírání vrcholů se zadanými klíči, včetně vyvážení) nad binárními vyhledávacími stromy. Eulerovské grafy a hamiltonovské kružnice Stromy ooo«ooooo Rovinné grafy ooooooooooo Izomorfismus stromů Již dříve jsme si říkali, že rozhodnout o izomorfismu dvou obecných grafů je velmi obtížný problém. U stromů je naštěstí, jak si ukážeme, situace podstatně jednodušší. Eulerovské grafy a hamiltonovské kružnice Stromy Rovinné grafy ooo«ooooo ooooooooooo Izomorfismus stromů Již dříve jsme si říkali, že rozhodnout o izomorfismu dvou obecných grafů je velmi obtížný problém. U stromů je naštěstí, jak si ukážeme, situace podstatně jednodušší. Pro popis všech možných izomorfismu (kořenových) stromů je užitečné kromě vztahů otec-syn ještě užitečné mít syny uspořádány v pořadí (třeba v představě odleva doprava nebo podle postupného růstu atd.). Eulerovské grafy a hamiltonovské kružnice Stromy Rovinné grafy ooo«ooooo ooooooooooo Izomorfismus stromů Již dříve jsme si říkali, že rozhodnout o izomorfismu dvou obecných grafů je velmi obtížný problém. U stromů je naštěstí, jak si ukážeme, situace podstatně jednodušší. Pro popis všech možných izomorfismu (kořenových) stromů je užitečné kromě vztahů otec-syn ještě užitečné mít syny uspořádány v pořadí (třeba v představě odleva doprava nebo podle postupného růstu atd.). Definice Pěstěný strom T = {V,E, vr, v) je kořenový strom společně s částečným uspořádáním v na hranách takovým, že srovnatelné jsou vždy právě hrany směřující od jednoho otce k synům. Izomorfismem kořenových stromů T = (V,E, vr) a T' = (V, E', v'r) rozumíme takový izomorfismus grafů ip : T —> T', který převádí vr na v'r. Pro pěstěné stromy navíc požadujeme aby zobrazení hran zachovávalo částečná uspořádání v a v'. Eulerovské grafy a hamiltonovské kružnice Stromy Rovinné grafy oooo»oooo ooooooooooo Kódy stromů Pro pěstěné stromy T = {V,E, vr, v) zavedeme jejich (jak uvidíme) jednoznačný popis pomocí slov z nul a jedniček. Obrazně si můžeme představit, že strom kreslíme a každý přírůstek naznačíme dvěma tahy, které si označíme 0 (dolů) a 1 (nahoru). Začneme od listů (příp. mimo kořene), kterým všem přiřadíme slovo 01. Celý strom pak budeme popisovat zřetězováním částí slov tak, že má-li otec v syny uspořádány jako posloupnost v\,... ,V£, a jsou-li již jednotliví synové označeni slovy 1/Vi,... Wf>, pak pro otce použijeme slovo OWi... W(l. Hovoříme o kódu pěstěného stromu. Eulerovské grafy a hamiltonovské kružnice Stromy Rovinné grafy oooo»oooo ooooooooooo Kódy stromů Pro pěstěné stromy T = {V,E, vr, v) zavedeme jejich (jak uvidíme) jednoznačný popis pomocí slov z nul a jedniček. Obrazně si můžeme představit, že strom kreslíme a každý přírůstek naznačíme dvěma tahy, které si označíme 0 (dolů) a 1 (nahoru). Začneme od listů (příp. mimo kořene), kterým všem přiřadíme slovo 01. Celý strom pak budeme popisovat zřetězováním částí slov tak, že má-li otec v syny uspořádány jako posloupnost v\,... ,V£, a jsou-li již jednotliví synové označeni slovy 1/Vi,... Wf>, pak pro otce použijeme slovo OWi... W(l. Hovoříme o kódu pěstěného stromu. Skutečně, kreslením cest dolů a nahoru získáme skutečně původní strom s jednou hranou směřující shora do kořene navíc. Eulerovské grafy a hamiltonovské kružnice Stromy ooooo«ooo Rovinné grafy ooooooooooo Věta Dva pěstěné stromy jsou izomorfní právě, když mají stejný kód. Důkaz. Z konstrukce je zřejmé, že izomorfní stromy budou mít stejný kód, zbývá tedy pouze dokázat, že neizomorfní stromy vedou na různé kódy, jinými slovy, že z daného kódy jednoznačně zrekonstruujeme výchozí pěstovaný strom. Dokážeme to indukcí podle délky kódu (tj. počtu nul a jedniček) tak, že využijeme jednoznačné kódy pro všechny podstromy vzniklé odjemutím kořene. 19 0,0- Eulerovské grafy a hamiltonovské kružnice Stromy ooooo«ooo Rovinné grafy ooooooooooo Věta Dva pěstěné stromy jsou izomorfní právě, když mají stejný kód. Důkaz. Z konstrukce je zřejmé, že izomorfní stromy budou mít stejný kód, zbývá tedy pouze dokázat, že neizomorfní stromy vedou na různé kódy, jinými slovy, že z daného kódy jednoznačně zrekonstruujeme výchozí pěstovaný strom. Dokážeme to indukcí podle délky kódu (tj. počtu nul a jedniček) tak, že využijeme jednoznačné kódy pro všechny podstromy vzniklé odjemutím kořene. Pro nejkratší kód 01 je situace snadná. 19 0,0- Eulerovské grafy a hamiltonovské kružnice Stromy ooooo«ooo Rovinné grafy ooooooooooo Dva pěstěné stromy jsou izomorfní právě, když mají stejný kód. Důkaz. Z konstrukce je zřejmé, že izomorfní stromy budou mít stejný kód, zbývá tedy pouze dokázat, že neizomorfní stromy vedou na různé kódy, jinými slovy, že z daného kódy jednoznačně zrekonstruujeme výchozí pěstovaný strom. Dokážeme to indukcí podle délky kódu (tj. počtu nul a jedniček) tak, že využijeme jednoznačné kódy pro všechny podstromy vzniklé odjemutím kořene. Pro nejkratší kód 01 je situace snadná. V indukčním kroku je dán kód délky 2(n + 1) tvaru 041, přičemž A = AXA2 ... At je zřetězením několika kódů pěstovaných stromů. Část A\ je tvořena nejkratším prexifex A, který má stejný počet 0 a 1, dále A2, atd. Podle indukčního předpokladu každé A, jednoznačně odpovídá pěstěnému stromu, z čehož zřejmě dostáváme jediný pěstěný strom odpovídající kódu 041. □ 00. o- Eulerovské grafy a hamiltonc vské kružnice Stromy Rovinné grafy oooooo«oo OOOOOOOOOOO Nyní převedeme testování izomorfismu kořenových stromů, resp. stromů na testování pěstěných stromů. Eulerovské grafy a hamiltonovské kružnice Stromy oooooo«oo Rovinné grafy ooooooooooo Nyní převedeme testování izomorfismu kořenových stromů, resp. stromů na testování pěstěných stromů. U kořenových stromů lze využít kódy, pokud se podaří určit pořadí jejich synů jednoznačně až na izomorfismus. Na pořadí synů ovšem nezáleží právě tehdy, když jsou podgrafy určené jejich následníky izomorfní. Eulerovské grafy a hamiltonovské kružnice Stromy oooooo«oo Rovinné grafy ooooooooooo* Nyní převedeme testování izomorfismu kořenových stromů, resp. stromů na testování pěstěných stromů. U kořenových stromů lze využít kódy, pokud se podaří určit pořadí jejich synů jednoznačně až na izomorfismus. Na pořadí synů ovšem nezáleží právě tehdy, když jsou podgrafy určené jejich následníky izomorfní. Využijeme proto obdobu (rekurzivní) konstrukce kódu pro pěstěné stromy - budeme postupovat obdobně s využitím lexikografického (slovníkového) uspořádní synů podle jejich kódů. Kořenový strom budeme tedy popisovat zřetězováním částí slov tak, že má-li otec v syny již označeny kódy W\,... W£, pak pro otce použijeme slovo OWi... Wel kde pořadí Wi,...,W£je zvoleno tak aby Wi < W2 < ■ ■ ■ < W£. Eulerovské grafy a hamiltonc vské kružnice Stromy Rovinné grafy ooooooo«o ooooooooooo Pokud není určen kořen ve stromě, můžeme jej určit tak, aby byl „přibližně uprostřed stromu". Eulerovské grafy a hamiltonovské kružnice Stromy ooooooo«o Rovinné grafy ooooooooooo Pokud není určen kořen ve stromě, můžeme jej určit tak, aby byl „přibližně uprostřed stromu". Každému vrcholu stromu T přiřadíme hodnotou exc(v) tzv. výstřednosti (excentricity), kterou definujeme pro každý vrchol v jako maximální vzdálenost z v do jiného vrcholu w v T. Tvrzení Bud C( 7") množina vrcholů stromu T, jejichž výstřednost nabývá minimální hodnoty (C(T) se nazývá střed/centrum grafu, minimální hodnota pak poloměr grafu). Pak C(7~) má jeden vrchol nebo dva vrcholy spojené hranou v T. Eulerovské grafy a hamiltonovské kružnice Stromy ooooooo«o Rovinné grafy ooooooooooo Pokud není určen kořen ve stromě, můžeme jej určit tak, aby byl „přibližně uprostřed stromu". Každému vrcholu stromu T přiřadíme hodnotou exc(v) tzv. výstřednosti (excentricity), kterou definujeme pro každý vrchol v jako maximální vzdálenost z v do jiného vrcholu w v T. Tvrzení Bud C( T) množina vrcholů stromu T, jejichž výstřednost nabývá minimální hodnoty (C(T) se nazývá střed/centrum grafu, minimální hodnota pak poloměr grafu). Pak C(T) má jeden vrchol nebo dva vrcholy spojené hranou v T. Důkaz. Snadno indukcí s využitím triviálního faktu, že nejvzdálenějším vrcholem od každého vrcholu i/je nutně list. Centrum T tedy splývá s centrem stromu T', který vznikne z T vypuštěním listů a příslušných hran. □ t Eulerovské grafy a hamiltonovské kružnice Stromy 00000000« Rovinné grafy ooooooooooo* Libovolnému stromu přiřadíme jednoznačný kód, až na izomorfismus takto: Pokud je v centru T jediný vrchol, použijeme jej jako kořen; v opačném případě vytvoříme stejným způsobem kód pro dva stromy vzniklé z T odebráním hrany (bez vrcholů) spojující vrcholy xi,x2 v C(T) a kód vznikne zřetězením kódů obou kořenových stromů (T\, xi), (T2, x2) v pořadí podle lexikografického uspořádání těchto kódů. Eulerovské grafy a hamiltonovské kružnice Stromy 00000000« Rovinné grafy ooooooooooo* Libovolnému stromu přiřadíme jednoznačný kód, až na izomorfismus takto: Pokud je v centru T jediný vrchol, použijeme jej jako kořen; v opačném případě vytvoříme stejným způsobem kód pro dva stromy vzniklé z T odebráním hrany (bez vrcholů) spojující vrcholy xi,x2 v C(T) a kód vznikne zřetězením kódů obou kořenových stromů (T\, xi), (T2, x2) v pořadí podle lexikografického uspořádání těchto kódů. Věta Dva stromy T a T1 jsou izomorfní právě, když mají společný kód. Eulerovské grafy a hamiltonovské kružnice Stromy 00000000« Rovinné grafy ooooooooooo* Libovolnému stromu přiřadíme jednoznačný kód, až na izomorfismus takto: Pokud je v centru T jediný vrchol, použijeme jej jako kořen; v opačném případě vytvoříme stejným způsobem kód pro dva stromy vzniklé z T odebráním hrany (bez vrcholů) spojující vrcholy xi,x2 v C(T) a kód vznikne zřetězením kódů obou kořenových stromů (T\, xi), (T2, x2) v pořadí podle lexikografického uspořádání těchto kódů. Věta Dva stromy T a T' jsou izomorfní právě, když mají společný kód. Poznámka Z uvedených úvah lze snadno nahlédnout, že algoritmus na testování izomorfismu stromů lze implementovat v lineárním čase vzhledem k počtu vrcholů. Eulerovské grafy a hamiltonovské kružnice Plán přednášky Stromy ooooooooo Rovinné grafy ooooooooooo* ■b ei j Iptovskp Érrsfv a ha m i Itonovskp kn jžn ií~p • Izomorfismy stromů Rovinné grafy o Platónská tělesa • Barvení map Eulerovské grafy a hamiltonovské kružnice Rovinné grafy Stromy ooooooooo Rovinné grafy •oooooooooo 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. Eulerovské grafy a hamiltonovské kružnice Rovinné grafy Stromy ooooooooo Rovinné grafy •oooooooooo 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. Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy o»ooooooooo 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í". Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy o»ooooooooo 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í: Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy oo«oooooooo Obecně se dá ukázat tzv. Kuratowského věta: Věta Graf G je rovinný právě tehdy když žádný jeho podgraf není izomorfní dělení grafu K33 nebo grafu K5. Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy oo«oooooooo Obecně se dá ukázat tzv. Kuratowského věta: Věta Graf G je rovinný právě tehdy když žádný jeho podgraf není izomorfní dělení grafu K33 nebo grafu K5. 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. Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy oo«oooooooo Obecně se dá ukázat tzv. Kuratowského věta: Věta Graf G je rovinný právě tehdy když žádný jeho podgraf není izomorfní dělení grafu K33 nebo grafu K5. 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. Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy ooo»ooooooo Uvažme (konečný) rovinný graf G, včetně jeho nakreslení v R2 a nechť R2 \ G je množina všech bodů x e 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, Si,..., Sk} a rovinný graf G = (V, E, S). Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy oooo«oooooo Jako příklad si můžeme 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 rozdíl mezi počty vrcholů a hran pro všechny stromy, dostáváme vztah \V\ -\E\ + \S\ = 2. Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy ooooo«ooooo 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. Věta Necht G = (V, E,S) je souvislý rovinný graf. Pak platí \V\-\E\ + \S\=2. Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy ooooo«ooooo 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. ' Věta * Necht G = (V, E,S) je souvislý rovinný graf. Pak platí \V\ -\E\ + \S\ = 2. Důkaz. Indukcí podle počtu hran. ^1 Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy oooooo»oooo 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 hovoř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á). Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy oooooo»oooo 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 hovoř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. Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy 0000000«0( Rovinné grafy, které vzniknou z konvexních mnohostěnů, jsou zjevně 2-souvislé, protože každé dva vrcholy v konvexním mnohostěnu 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 mnohostěnů 3-souvislé. Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy 0000000«0( Rovinné grafy, které vzniknou z konvexních mnohostěnů, jsou zjevně 2-souvislé, protože každé dva vrcholy v konvexním mnohostěnu 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 mnohostěnů 3-souvislé. Ve skutečnosti platí dosti náročná Steinitzova věta: Věta Libovolný vrcholově 3souvislý rovinný graf G vzniká z konvexního mnohostěnu vM3. Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy oooooooo»oo< Jako ilustraci kombinatorické práce s grafy odvodíme klasifikaci tzv. pravidelních mnohostěnů, tj. mnohostěnů poskládaných ze stejných pravidelný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: Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy oooooooo»oo< Jako ilustraci kombinatorické práce s grafy odvodíme klasifikaci tzv. pravidelních mnohostěnů, tj. mnohostěnů poskládaných ze stejných pravidelný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: Eulerovské grafy a hamiltonc vské kružnice Stromy Rovinné grafy ooooooooo ooooooooo«o 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 Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy ooooooooo«o< 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á 2e 2e 2 = n- e + s= — - e + —. d k Úpravou odtud dostáváme pro naše známé d a k vztah 1 1 _ 1 1 ~ď + ~k ~ 2 + e' Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy 0000000000»« 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. Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy OOOOOOOOOOOt Maximální počet hran Věta Nechi (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. Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy OOOOOOOOOOOt Maximální počet hran Věta Nechi (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. Důkaz. Maximální rovinný graf má všechny stěny ohraničené kružnicí délky 3, z čehož plyne 3|S| = 2\E\ a odtud již pomocí Eulerova vztahu dostáváme první tvrzení. Podobně v druhé části. □ Eulerovské grafy a hamiltonovské kružnice Stromy Rovinné grafy ooooooooo ooooooooooo* Důsledek • Ks není rovinný; Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy OOOOOOOOOOOi Důsledek • K5 není rovinný; • K33 není rovinný; Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy OOOOOOOOOOOi Důsledek • K5 není rovinný; 9 K33 není rovinný; 9 každý rovinný graf obsahuje alespoň jeden vrchol stupně nejvýše 5; Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy OOOOOOOOOOOi Důsledek • K5 není rovinný; 9 K33 není rovinný; 9 každý rovinný graf obsahuje alespoň jeden vrchol stupně nejvýše 5; 9 každý rovinný graf bez trojúhelníků obsahuje alespoň jeden vrchol stupně nejvýše 3. Eulerovské grafy a hamiltonovské kružnice Stromy Rovinné grafy ooooooooo ooooooooooo 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). Eulerovské grafy a hamiltonovské kružnice Stromy ooooooooo Rovinné grafy ooooooooooo* 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. Každou normální mapu je možné obarvit pomocí čtyř barev.