8 Rovinnost a kreslení grafů V přímé návaznosti na předchozí lekci se zaměříme na druhý důležitý aspekt slavného problému čtyř barev, který byl původně formulován pro barevné rozlišení států na politické mapě: Jak tedy taková obarvovaná politická mapa souvisí s kreslením grafů? Jednoduše - souvislé státy můžeme reprezentovat jako vrcholy grafu a hranami pak zaznamenat „sousednost" mezi státy. Důležité je, že takto vzniklý graf můžeme zřejmě zakreslit v rovině bez křížení hran a nazýváme jej proto rovinným grafem: Stručný přehled lekce • Kreslení grafů, definice rovinného grafu a základní vlastnosti. • Rozpoznávání rovinných grafů (Kuratowského věta). • Barvení map a rov. grafů - problém čtyř barev a nástin jeho řešení. • Kreslení grafů s křížením hran - průsečíkové číslo. 8.1 Rovinné kreslení grafu Definice 8.1. Rovinným nakreslení grafu G myslíme zobrazení, ve kterém jsou vrcholy znázorněny jako různé body v rovině a hrany jako oblouky spojující body svých koncových vrcholů. Přitom hrany se nesmí nikde křížit ani procházet jinými vrcholy než svými koncovými body. Graf je rovinný pokud má rovinné nakreslení. Důležitým příkladem rovinných grafů jsou grafy (třírozměrných Euklidovských) mnohostěnů, třeba graf čtyřstěnu, krychle, osmistěnu, dvanáctistěnu, atd. Platí, že grafy mnohostěnů jsou vždy rovinné a 3-souvislé. Naopak každý rovinný 3-souvislý jednoduchý graf je grafem nějakého mnohostěnu. (Důkaz tohoto tvrzení je obtížný.) Petr Hliněný, Fl MU Bn : MA010: Rovinnost a kreslení Definice: Stěnami rovinného nakreslení grafu nazýváme (topologicky) souvislé oblasti roviny ohraničené tímto nakreslením grafu. Rovinný graf může mít více podstatně různých nakreslení, ale 3-souvislý rovinný graf má ve všech svých rovinných nakresleních „stejné stěny" (Důsledek 8.11). c Definice. Duální (multi)graf rovinného nakreslení grafu G získáme tak, že stěny nahradíme vrcholy duálu a hranami spojíme sousedící dvojice stěn. Duální multigraf k rovinnému grafu je vždy rovinný, což je relativně snadné dokázat topologicky. Na druhou stranu však často bude obsahovat násobné hrany a dokonce i smyčky. Petr Hliněný, Fl MU Bn : MA010: Rovinnost a kreslení 8.2 Eulerův vztah o počtu stěn Nyní si uvedeme zajímavý a vlastně „jediný rozumný kvantitativní" vztah o rovinných nakresleních grafů. Jedná se o slavný Eulerův vztah, který říká: Věta 8.2. Nechť rovinné nakreslení souvislého grafu G má f sten. Pak \V(G)\ + f-\E(G)\ = 2.c Důkaz: Nechť počet vrcholů v G je v a hran h. • Pokud je G strom, tj. nemá kružnice, má ve svém nakreslení jedinou stěnu a dle Věty 4.3 má přesně h = v — 1 hran. Potom platí v + f — h = v + í — (v — í) = 2. • Pokud G obsahuje kružnici C, pak vypustíme jednu její hranu e. Tím se počet hran sníží o 1, ale zároveň se sníží o 1 počet stěn, protože kružnice C původně oddělovala (viz Jordánova věta o kružnici) dvě stěny přilehlé k hraně e od sebe, ale nyní tyto dvě stěny „splynou" v jednu. Počet vrcholů se nezmění. Proto se nezmění hodnota v + / — h = v + (f — 1) — (h — 1) = 2. Tvrzení tak plyne z principu matematické indukce, a D Poznámka: Všimněte si dobře, že Eulerův vztah vůbec nezávisí na tom, jak je graf G nakreslený, je to vlastnost grafu jako takového. ________;tr Hliněný, Fl MU Brn< /IAO 10: Rovinnost a kreslení Tento jednoduše vypadající vztah má mnoho aplikací a důsledků. Důsledek 8.3. Jednoduchý rovinný graf na v > 3 vrcholech má nejvýše 3v — 6 hran. Jednoduchý rovinný graf na v > 3 vrcholech a bez trojúhelníků má nejvýše 2v — 4 hran. Důkaz: Můžeme předpokládat, že graf je souvislý, jinak bychom přidali další hrany. Nechť počet vrcholů vGjew, stěn je / a hran h. Jelikož nemáme smyčky ani násobné hrany, má každá stěna v nakreslení grafu na obvodu aspoň 3 hrany, přitom každou hranu započítáme ve dvou přilehlých stěnách. Pak tedy platí h>\ -3f, neboli %h > f. Dosazením do vztahu Věty 8.2 získáme 2 1 2 = v + f — h < v + — h — h = v — — h h<3(v-2) = 3v-6. Druhá část se dokazuje obdobně, ale nyní víme, že graf nemá ani trojúhelníky, a tudíž má každá stěna v nakreslení grafu na obvodu aspoň 4 hrany. Pak tedy platí h > \ -4/, neboli jh > f. Dosazením do vztahu Věty 8.2 získáme 2 1 2 = v + f — h < v -\—h — h = v-----h J - 4 2 h < 2(v - 2) = 2v - 4 . Tím jsme hotovi. D Petr Hliněný, Fl MU Brnc Fl: MA010: Rovinnost a kreslení Důsledek 8.4. Každý jednoduchý rovinný graf obsahuje vrchol stupně nejvýše 5. Každý jednoduchý rovinný graf bez trojúhelníků obsahuje vrchol stupně nejvýše 3. Důkaz: Pokud by všechny vrcholy měly stupně alespoň 6, celý graf by měl aspoň i -6v = 3v hran, což je ve sporu s Důsledkem 8.3. Některý vrchol musí tudíž mít menší stupeň než 6. Obdobně postupujeme u druhého tvrzení. D Petr Hliněný, Fl MU Brno 6 Fl: MA010: Rovinnost a kreslení 8.3 Rozpoznání rovinných grafů Při praktickém využití rovinných grafů je potřeba umět abstraktně zadaný graf rovinně nakreslit bez křížení hran. Na rozdíl od problému určení barevnosti grafu se naštěstí jedná o efektivně algoritmicky řešitelný problém, d První algoritmus běžící v lineárním čase byl podán Hopcroftem a Tarjanem 1974 a od té doby se objevilo několik jednodušších algoritmů, ale stále nejsou dostatečně přístupné, abychom je mohli ukázat v omezeném čase na přednášce. Věta 8.5. Rozhodnout rovinnost a nalézt příslušné nakreslení daného grafu lze v lineárním čase (vůči počtu vrcholů). Místo obecných algoritmů pro rovinné kreslení grafů se zde podíváme na otázku, jak odůvodnit nerovinnost (malého) grafu. Petr Hliněný, Fl MU Brno 7 Fl: MA010: Rovinnost a kreslení Příklad 8.6. Ukažme, že následující dva grafy, K5 a Ks:s nejsou rovinné. Při zdůvodnění využijeme znalosti předchozího oddílu. Všimněme si, že graf K5 má 5 vrcholů a 10 > 3- 5 — 6 hran. Podobně graf A3,3 má 6 vrcholů a 9 > 2 -6 — 4 hran, přitom neobsahuje žádné trojúhelníky. Proto podle Důsledku 8.3 žádný z nich není rovinný. □ Ü Důsledek 8.7. Grafy K5 a K33 nejsou rovinné, c Definice: Podrozdělením grafu G rozumíme graf, který vznikne z G nahrazením některých hran novými cestami libovolné (kladné) délky. Důležitý abstraktní popis všech rovinných grafů nalezl K.Kuratowski: Věta 8.8. Graf G je rovinný právě když neobsahuje pod rozdělení grafů K5 nebo K33 jako podgrafy Detr Hliněný, Fl MU Bn : MA010: Rovinnost a kreslení Příklad 8.9. Které z následujících dvou grafů jsou rovinné? Najděte rovinné nakreslení (včetně očíslovaných vrcholů), nebo zdůvodněte nerovinnost grafu. Po chvíli zkoumání určitě přijdeme na to, že graf A se dá nakreslit rovinně takto: Graf B na druhou stranu rovinný není podle Věty 8.8, protože je v něm obsaženo podrozdělení grafu A3,3, které je ukázáno na tomto obrázku: Petr Hliněný, Fl MU Bn : MA010: Rovinnost a kreslení Jednoznačnost rovinného nakresleni Fakt: V 2-souvislém rovinném grafu je každá stěna ohraničená kružnicí. Díky tomuto faktu lze snadno nadefinovat, že dvě rovinná nakreslení 2-souvislého grafu jsou ekvivalentní, pokud jejich stěny tvoří stejné soubory kružnic, c Klíčovým výsledkem nyní je: Lema 8.10. Kružnice C v 3-souvislém rovinném grafu G je stěnou jeho nakreslení, právě když podgrafG — V(C) je souvislý graf. a Důkaz: V jednom směru, pokud G' = G — V (C) je souvislý, pak podle Jordánovy věty o kružnici leží celý G' uvnitř jedné oblasti C, tudíž druhá oblast C je stěnou v každém nakreslení G. Naopak pokud C ohraničuje stěnu v některém rovinném nakreslení grafu G, dokážeme, že každé dva vrcholy mimo C lze spojit cestou disjunktní s C. Nechť tedy x, y G V(G) \ V(C) a označme X (či Y) množinu těch vrcholů C dosažitelných z x (z y) po cestách neprocházejících přes C. Jelikož x,y náleží stejné stěně kružnice C, množiny X,Y se na C „nepřekrývají", přesněji je lze od sebe oddělit odebráním některých dvou vrcholů c, d G V (C). Pak však {c, d} je řezem v grafu G oddělujícím x od y a to odporuje předpokladu 3-souvislosti, spor. D Důsledek 8.11. Každá dvě rovinná nakreslení 3-souvislého grafu jsou ekvivalentní. Petr Hliněný, Fl MU Brno 10 Fl: MA010: Rovinnost a kreslení r Zajímavou aplikací Důsledku 8.11 je algoritmus pro rozpoznávání isomorfizmu rovinných grafů, který mimo porovnávání rovinných nakreslení 3-souvislých komponent používá metody rozkladu grafu na "více-souvislé" komponenty a testování isomorfizmu stromů: Věta 8.12. Problém isomorfizmu rovinných grafů je řešitelný v lineárním čase. Závěrem si ještě bez důkazu uvedeme, že rovinné grafy vždy mají pěkné nakreslení v rovině. Věta 8.13. Každý jednoduchý rovinný graf lze nakreslit v rovině (bez křížení hran) tak, že hrany jsou úsečky. 'etr Hliněný, Fl MU Brno 11 Fl: MA010: Rovinnost a kreslení Barvení map a rovinných grafů Vzpomeňme si na již zmiňovaný převod mapy na graf -jedná se vlastně o vytvoření duálního grafu k této mapě. Aby v duálním grafu k mapě nevznikly smyčky, v mapě nesmí žádný stát sousedit sám se sebou, což je přirozený požadavek. V roce 1976 Appel a Haken, a pak znovu v roce 1993 Robertson, Seymour, Sanders a Thomas, dokázali tuto větu, která rozřešila problém čtyř barev a která je jedním z nejslavnějších výsledků diskrétní matematiky vůbec: Věta 8.14. Každý rovinný graf bez smyček lze obarvit 4 barvami, c Důkaz této věty je nesmírně složitý (však byl také hledán po více než 100 let a k jeho úplnému provedení je stále třeba počítač), a proto si uvedeme slabší a mnohem jednodušší tvrzení: Tvrzení 8.15. Každý rovinný graf bez smyček lze obarvit 6 barvami. Každý rovinný graf bez smyček a bez trojúhelníků lze obarvit 4 barvami, c Důkaz: Podle Důsledku 8.4 najdeme v každém podgrafu G vrchol v stupně nejvýše 5, a tudíž je G 5-degenerovaný a obarvíme jej podle Věty 7.6. Druhou část dokážeme obdobně, když nalezneme vrchol stupně < 3. ü Petr Hliněný, Fl MU Brno 12 Fl: MA010: Rovinnost a kreslení r Věta 8.16. Každý rovinný graf bez smyček má výberovou barevnost nejvýše 5. c Důkaz (náznak): Poměrně přímočarou indukcí lze dokázat následující zesílené tvrzení: Nechť rovinný graf G s vnéjší sténou ohraničenou kružnicí C má všechny ostatní steny trojúhelníky. Nechť každý vrchol mimo C má přiřazen seznam 5 barev, vrcholy C mají seznamy 3 barev a jisté dva sousední vrcholy x,y na C mají přímo předepsané (různé) barvy. Pak G lze výberové obarvit. • Nechť z y^ y je druhý soused x na C. Pokud některá hrana f ze z nenáležející C má druhý konec také na C, pak podél / „rozdělíme" G na podgraf G\ obsahující x,y a podgraf G i sdílející hranu / s G\. Indukcí nejprve obarvíme G\, pak G i taktéž splní indukční předpoklad a i jej dobarvíme. • Jinak budeme indukcí barvit podgraf G3 = G — z; přičemž všem sousedům z uvnitř G odebereme ze seznamu (jejich pěti) barev dvě z barev seznamu u vrcholu z různé od barvy x. Následně dobarvíme vrchol z, pro nějž máme tři možnosti a jen jeho dva sousedé na C s ním mohou být v konfliktu. D etr Hliněný, Fl MU Brno 13 Fl: MA010: Rovinnost a kreslení 8.5 Praktické „pružinové" kreslení grafů Závěrem se podívejme na trochu jinou problematiku - jak prakticky nakreslit daný (nerovinný) graf, aby vše „vypadalo hezky". Jeden ze základních heuristických přístupů ke kreslení grafů se dá shrnout následovně: Metoda 8.17. Pružinové kreslení grafu • Vytvoříme „fyzikální" model grafu, kde vrcholy budou kuličkami, které se vzájemně odpuzují, a hrany budou pružinami, které své koncové vrcholy vzájemně přitahují. • Náš model budeme iterovat jako dynamický systém, až do konvergence pozic vrcholů. Zde je potřebné modelovat i „tlumení" pohybů vrcholů, aby nedošlo k rozkmitání systému, c • I když kreslíme graf do roviny, je užitečné začít modelovat systém s dimenzí navíc (aby měly vrcholy „více místa k pohybu") a teprve v průběhu času dodatečnou silou přidanou dimenzi „eliminovat", neboli zkonvergovat pozice vrcholů do zvolené roviny. 'etr Hliněný, Fl MU Brno 14 Fl: MA010: Rovinnost a kreslení