Drsná matematika III -- 9. přednáška Rovinné grafy: Stromy, konvexní mnohoúhelníky v prostoru a Platónská tělesa Masarykova univerzita Fakulta informatiky 11. 11. 2008 Obsah přednášky Literatura Eulerovské grafy a Hamiltonovy kružnice Stromy Rovinné grafy Platónská tělesa Plán přednáky Literatura Eulerovské grafy a Hamiltonovy kružnice Stromy Rovinné grafy Platónská tělesa Kde je dobré číst? 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/ Bill Cherowitzo, Applied Graph Therory, Lecture Notes, http://www- math.cudenver.edu/~wcherowi/courses/m4408/m4408f.html Plán přednáky Literatura Eulerovské grafy a Hamiltonovy kružnice Stromy Rovinné grafy Platónská tělesa Přeložme důvěrně známou intelektuální výzvu z mateřské školky ,,nakresli obrázek jedním tahem do jazyka teorie grafů: najděte sled, který projde všechny hrany a každý vrchol alespoň jednou. Přeložme důvěrně známou intelektuální výzvu z mateřské školky ,,nakresli obrázek jedním tahem do jazyka teorie grafů: najděte sled, který projde všechny hrany a každý vrchol alespoň jednou. Definition Sled, který prochází právě jednou všemi hranami a začíná a končí v jednom vrcholu, se nazývá uzavřený eulerovský sled. Grafům, které takový sled připouští říkáme eulerovské. 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 Leonharta Eulera z roku 1736. 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 Leonharta Eulera z roku 1736. Situace je znázorněna na obrázku. Nalevo neumělý náčrt řeky s ostrovy a mosty, napravo odpovídající (multi)graf. Vrcholy tohoto grafu odpovídají ,,souvislé pevnině , hrany mostům. Pokud by nám vadily násobné hrany mezi vrcholy, stačí rozdělit hrany pomocí nových vrcholů. 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. 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. Theorem Graf G je eulerovský tehdy a jen tehdy, když je souvislý a všechny vrcholy v G mají sudé stupně. 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. Theorem Graf G je eulerovský tehdy a jen tehdy, když je souvislý a všechny vrcholy v G mají sudé stupně. Corollary Graf lze nakreslit jedním tahem právě, když má všechny stupně vrcholů sudé nebo když existují pravě dva vrcholy se stupněm lichým. 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. Lze ukázat, že neexistuje algoristmus, který by v polynomiálním čase rozhodnul, zda je graf hamiltonovský. 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. Lze ukázat, že neexistuje algoristmus, který by v polynomiálním čase rozhodnul, zda je graf hamiltonovský. Problém nalezení hamiltonovské kružnice je podstatou mnoha problémů v logistice, tj. například když řešíme optimální cesty při dodávkách zboží. Plán přednáky Literatura Eulerovské grafy a Hamiltonovy kružnice Stromy Rovinné grafy Platónská tělesa Definition Souvislý graf, ve kterém není žádná kružnice, se nazývá strom. Obecně v grafech nazýváme vrcholy stupně jedna listy (případně také koncové vrcholy). Následující lemma ukazuje, že každý strom lze vybudovat postupně z jediného vrcholu přidáváním listů: Definition Souvislý graf, ve kterém není žádná kružnice, se nazývá strom. Obecně v grafech nazýváme vrcholy stupně jedna listy (případně také koncové vrcholy). 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. Theorem Pro každý graf G = (V , E) jsou následující podmínky ekvivalentní 1. G je strom; 2. pro každé dva vrcholy v, w grafu G existuje právě jedna cesta z v do w; 3. graf G je souvislý, ale vyjmutím libovolné hrany vznikne nesouvislý graf 4. graf G neobsahuje kružnici, každým přidáním hrany do grafu G však již kružnice vznikne 5. G je souvislý graf a mezi velikostí množin jeho vrcholů a hran platí vztah |V | = |E| + 1. Theorem Pro každý graf G = (V , E) jsou následující podmínky ekvivalentní 1. G je strom; 2. pro každé dva vrcholy v, w grafu G existuje právě jedna cesta z v do w; 3. graf G je souvislý, ale vyjmutím libovolné hrany vznikne nesouvislý graf 4. graf G neobsahuje kružnici, každým přidáním hrany do grafu G však již kružnice vznikne 5. G je souvislý graf a mezi velikostí množin jeho vrcholů a hran platí vztah |V | = |E| + 1. Obecně, graf neobsahující kružnice nazýváme les. Můžeme tedy formulovat matematickou větu: ,,Strom je souvislý les. Theorem Pro každý graf G = (V , E) jsou následující podmínky ekvivalentní 1. G je strom; 2. pro každé dva vrcholy v, w grafu G existuje právě jedna cesta z v do w; 3. graf G je souvislý, ale vyjmutím libovolné hrany vznikne nesouvislý graf 4. graf G neobsahuje kružnici, každým přidáním hrany do grafu G však již kružnice vznikne 5. G je souvislý graf a mezi velikostí množin jeho vrcholů a hran platí vztah |V | = |E| + 1. Obecně, graf neobsahující kružnice nazýváme les. Můžeme tedy formulovat matematickou větu: ,,Strom je souvislý les. Ke stromům se vrátíme později v souvislosti s praktickými aplikacemi. Plán přednáky Literatura Eulerovské grafy a Hamiltonovy kružnice Stromy Rovinné grafy Platónská tělesa 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(1) = 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. 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(1) = 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 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í . 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 K3,3, 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í: 0011 0011 0 0 1 1 0 0 1 1000000 000000000 000000 000 000000 111111111 111111 111111111 111111 000000 000000000 000000 000 000000 111111 111111111 111111 111 111111 00 000 00 0 00 111 11 111 11 00 000 00 0 00 111 11 111 11 00 000 00 0 00 111 11 111 110011 Obecně se dá ukázat tzv. Kuratowského věta: Theorem Graf G je rovinný právě tehdy když žádný jeho podgraf není izomorfní dělení grafu K3,3 nebo grafu K5. Obecně se dá ukázat tzv. Kuratowského věta: Theorem Graf G je rovinný právě tehdy když žádný jeho podgraf není izomorfní dělení grafu K3,3 nebo grafu K5. Jedna implikace je zřejmá ­ dělením rovinného grafu vzniká vžy 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. Obecně se dá ukázat tzv. Kuratowského věta: Theorem Graf G je rovinný právě tehdy když žádný jeho podgraf není izomorfní dělení grafu K3,3 nebo grafu K5. Jedna implikace je zřejmá ­ dělením rovinného grafu vzniká vžy 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í rovinatost grafu na n vrcholech v čase O(n), což určitě nejde přímou aplikací Kuratowského věty. Uvažme (konečný) rovinný graf G, včetně jeho realizace v R2 a nechť S je množina všech bodů x R2, které nepatří žádné hraně, ani nejsou vrcholem. Množina R2 \ G se rozpadne na disjunktní souvislé podmnožiny Si , kterým říkáme oblasti rovinného grafu G. Jedna oblast je výjimečná ­ ta jejíž doplněk obsahuje všechny vrcholy grafu. Budeme jí říkat neohraničená oblast S0. Množinu všech oblastí budeme označovat S = {S0, S1, . . . , 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ů K3,3 nebo K5. Protože strom G neobsahuje žádnou kružnici, dostáváme pouze jedinou oblast S0 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 |V | - |E| + |S| = 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 rovinnou realizaci vybereme. Theorem Nechť G = (V , E, S) je souvislý rovinný graf. Pak platí |V | - |E| + |S| = 2. 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 oblastech a pro takovýto graf pak jsou všechny jeho stěny rovnocenné (i oblast S0 je ohraničená). 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 oblastech a pro takovýto graf pak jsou všechny jeho stěny rovnocenné (i oblast S0 je ohraničená). Naopak, každý konvexní mnohostěn P R3 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 S0) pak obdržíme rovinný graf jako výše. Rovinné grafy, které vzniknou z konvesních mnohočlenů 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 (oblast) kromě S0 je vnitřkem nějaké kružnice a S0 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: Theorem Libovolný vrcholově 3­souvislý rovinný graf G vzniká z konvexního mnohostěnu v R3. Plán přednáky Literatura Eulerovské grafy a Hamiltonovy kružnice Stromy Rovinné grafy Platónská tělesa 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: 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 = 2e d - e + 2e k . Úpravou odtud dostáváme pro naše známé d a k vztah 1 d + 1 k = 1 2 + 1 e . Protože e a n musí být přirozená čísla (tj. zejména je 1 e > 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.