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ý býl původne formulovan pro barevne rozliSení statů na politicke mape:
Jak tedy taková obarvovaná politická mapa souvisí s kreslením grafu? Jednoduše - souvislé státy mužeme reprezentovat jako vrcholy grafu a hranami pak zaznamenat „sousednost" mezi staty. Dulezite je, ze takto vznikly graf muzeme zrejme zakreslit v rovine bez krízení hran a nazýváme jej proto rovinným grafem.
Stručný přehled lekce
• Kreslen í grafů, definice rovinného grafu a zakladn í vlastnosti.
• Rozpoznavan í rovinných grafů (Kuratowskeho veta).
• Barven í map a rov. grafů - problem Ctýr barev a nastin jeho resen í .
• Kreslen í grafů s kríZen ím hran - průseCíkove Císlo.
_Petr Hliněný,  FI MU Brno_1_FI: MA010: Rovinnost a kreslení
8.1   Rovinné kreslení grafu Dennice 8.1. Rovinným nakreslení grafu G
myslíme zobrazení, ve kterém jsou vrcholy znázorněny jako rUzne body v rovine a hrany jako oblouky spojující body svých koncových vrcholU. Pritom hrany se nesmí nikde krízit ani prochazet jinymi vrcholy nez svymi koncovymi body.
Graf je rovinný pokud ma rovinne nakreslení. c
Důležitým příkladem rovinných grafů jsou grafy (třírozměrných Euklidovských) mnohostěnů, třeba graf Ctyrstěnu, krychle, osmistěnu, dvaníctistěnu, atd.
Platí, že grafy mnohostenů jsou vždy rovinne a 3-souvisle. Naopak každý rovinný 3-souvislý jednoduchý graf je grafem nejakeho mnohostenu. (Dukaz tohoto tvrzení je obtízny.)
V
Petr Hliněný,  FI MU Brno
FI: MA010: Rovinnost a kreslení
Definice: Stěnami rovinného nakreslen í grafu nazýváme (topologicky) souvislé oblasti roviny ohraniCené 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 vsech svých rovinných nakresleních „stejne stený" (Důsledek 8.11). c
Definice. Duální (multi)gral rovinneho nakreslen í grafu G získame tak, Ze steny nahrad íme vrcholy dualu a hranami spoj íme soused íc í dvojice sten.
Důalní můltigraf k rovinnemů grafů je vždý rovinný, což je relativne snadne dokažat topologický. Na drůhoů stranů vsak casto bůde obsahovat nasobne hraný a dokonce i smýcký.
Petr Hliněný,  FI MU Brno 3 FI: MA010: Rovinnost a kreslení
8.2   Eulerův vztah o počtu stěn
Nyní si uvedeme zajímavý a vlastne „jediný rozumný kvantitativní" vztah o rovinných nakresleních grafU. Jedna se o slavný EulerUv vztah, který říka:
Věta 8.2. Necht rovinné nakreslení souvislého grafu G mé f stěn. Pak
• Pokud je G strom, tj. nema kruznice, ma ve svem nakreslení jedinou stenu a dle
Vetý 4.3 ma přesne h = v — 1 hran. Potom platí v + f — h = v +1 — (v — 1) = 2.
• Pokud G obsahuje kruznici C, pak výpustíme jednu její hranu e. Tím se pocet hran snízí o 1, ale zaroven se snízí o 1 pocet sten, protoze kruznice C puvodne oddělovala (viz Jordanova veta o kruznici) dve stený přilehle k hrane e od sebe, ale nýní týto dve stený „splýnou" v jednu. Pocet vrcholu se nezmení. Proto se nezmen í hodnota v + f — h = v + (f — 1) — (h — 1) = 2.
Tvrzen í tak plýne z principu matematicke indukce. □ □
Poznámka: Všimněte si dobre, ze Euleruv vztah vůbec nezávisí na tom, jak je graf G nakreslený, je to vlastnost grafů jako takoveho.
Petr Hliněný,  FI MU Brno_4_FI: MA010: Rovinnost a kreslení
|V(G)| + f — |E(G)| = 2 .□
Důkaz: Necht pocet vrcholu v G je v a hran h.
Tento jednoduše vypadající vztah má mnoho aplikácia důsledků.
Důsledek 8.3. Jednoduchý rovinný graf na v > 3 vrcholech ma nejvýše 3v — 6 hran. Jednoduchý rovinný graf na v > 3 vrcholech a bez trojúhelníku ma nejvýše 2v — 4 hra^<.
Důkaz: MůZeme předpokladat, Ze graf je souvislý, jinak bychom pridali další hrany. Necht pocet vrcholů v G je v, sten je f a hran h. JelikoZ nemáme smycky ani násobne hrany, ma kaZda stena v nakreslení grafu na obvodu aspon 3 hrany, přitom kaZdou hranu započítáme ve dvou přilehlých stěnách. Pak tedy platí h > \ ■ 3/, neboli %h > f. DosaZením do vZtahu Vety 8.2 Získame
Druha cast se dokaZuje obdobne, ale nyní víme, Ze graf nema ani trojuhelníky, a tudíZ 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 = v + f -h<v +-h-h h < 3(v — 2) = 3v — 6
= v
6.
2=v+f-h<v+-h-h= h < 2(v — 2) = 2v — 4
=v
h
2
Tím jsme hotovi.
□
Petr Hliněný,  FI MU Brno
FI: MA010: Rovinnost a kreslení
Důsledek 8.4. Každý jednoduchý rovinný graf obsahuje vrchol stupně nejvýše 5. Každý jednoduchý rovinný graf bež trojúhelníku obsahuje vrchol stupně nejvýše 3.
Důkaz: Pokud by všechny vrcholy mely stupně alespoň 6, celý graf by mel 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.
Obdobne postupujeme u druheho tvrzení. □
Petr Hliněný,  FI MU Brno
FI: MA010: Rovinnost a kreslení
8.3   Rozpoznání rovinných grafů
Při praktickém využití rovinných grafu je potřeba umet abstraktne zadaný graf rovinně nakreslit bez křížení hran. Na rozdíl od problemu urcení barevnosti grafu se naStestí jedna o efektivne algoritmicky řesitelný problem. c
První algoritmus bežící v linearním Case byl podan Hopcroftem a Tarjanem 1974 a od te doby se objevilo nekolik jednodussích algoritmu, ale stale nejsou dostatecne prístupne, abychom je mohli ukazat v omezenem case na přednísce.
Věta 8.5. Rozhodnout rovinnost a nalézt příslušné nakreslení daného grafu lze v lineárním čase (vUči počtu vrcholU).
Místo obecnych algoritmu pro rovinne kreslení grafu se zde podívame na otázku, jak oduvodnit nerovinnost (maleho) grafu.
V
Petr Hliněný,  FI MU Brno
FI: MA010: Rovinnost a kreslení
Příklad 8.6. Ukažme, že následující dva grafy, Ks a K3,3 nejsou rovinné.
	w	
K3,3 ,	A	A
K6
Pri zdůvodnění využijeme znalosti předchozího oddílu. Všimněme si, že graf Ks má 5 vrcholů a 10 > 3 • 5 — 6 hran. Podobne graf K3,3 má 6 vrcholů a 9 > 2 • 6 — 4 hran, přitom neobsahuje žádne trojúhelníky. Proto podle Důsledku 8.3 žadný z nich není rovinný. □ □
Důsledek 8.7. Grafy K5 a K33 nejsou rovinné. □
Definice: Podrozdélením grafu G rozumíme graf, který vznikne z G nahrazením některých hran novými cestami libovolne (kladne) delký.
DUlezitý abstraktní popis vSech rovinných grafU nalezl K.Kuratowski:
Veta 8.8. Graf G je rovinný právě když neobsahuje podrozdélenígrafU K5 nebo K33 jako podgrafy.
Petr Hlín
ny.
FI MU Brno
FI: MA010: Rovínnost a kreslení
•
Příklad 8.9. Ktere z následujících dvou grafu jsou rovinné? Najděte rovinné nakreslení (včetně očíslovaných vrcholu), nebo zdůvodněte nerovinnost grafu.
Po chvíli zkoumání určitě přijdeme na to, ze graf A se da nakreslit rovinně takto:
Graf B na druhou stranu rovinný nen í podle Vety 8.8, protoZe je v nem obsaZeno podrozdelen í grafu K33, ktere je ukazano na tomto obrazku:
Jednoznačnost rovinného nakreslení
Fakt: V 2-souvislem rovinnem grafu je kaZda stena ohraniCena kruZnic í.
D íky tomuto faktu lze snadno nadefinovat, Ze dve rovinna nakreslen í 2-souvisleho grafu jsou ekvivalentní, pokud jejich steny tvorí stejne soubory kruZnic. c
Kl ícovym vysledkem nyn í je:
Lema 8.10. Kružnice C v 3-souvislěm rovinném grafu G jě stěnou jěho nakreslení, pravě když podgraf G — V(C) jě souvislý graf. c
Důkaz: V jednom smeru, pokud G' = G — V(C) je souvisly, pak podle Jordanovy vety o kruZnici leZ í cely G' uvnitř jedne oblasti C, tud íZ druha oblast C je stenou v kaZdem nakreslen í G. c
Naopak pokud C ohranicuje stenu v nekterem rovinnem nakreslen í grafu G, dokaZeme, Ze kaZde dva vrcholy mimo C lZe spojit cestou disjunktn í s C. Necht tedy x, y G
V (G) \ V (C) a oZnacme X (ci Y) mnoZinu tech vrcholu C dosaZitelnych z x (z y) po
cestach neprochazej íc ích přes C. JelikoZ x, y naleZí stejne stene kruZnice C, mnoZiny X, Y se na C „nepřekryvaj í ", přesneji je lze od sebe oddelit odebran ím nekterych dvou vrcholu c,d G V (C). Pak vsak {c,d} je řezem v grafu G oddeluj íc ím x od y a to
Důsledek 8.11. Každá dvě rovinná nakrěslění3-souvislěho grafu jsou ěkvivalěntní.
odporuje předpokladu 3-souvislosti, spor.
□
V
Petr Hliněný,  FI MU Brr
FI: MA010: Rovinnost a kreslení
Zajímavou aplikací Důsledku 8.11 je algoritmus pro rozpoznávání isomorfizmu rovinných grafu, který mimo porovnavaní rovinných nakreslení 3-souvislých komponent pouZíva metodý rozkladu grafu na "více-souvisle" komponenty a testovaní isomorfizmu stromu:
Veta 8.12. Problém isomorfizmu rovinných grafu je řešitelný v lineárním čase.
Zaverem si jeste bez dukazu uvedeme, ze rovinne grafý vzdý mají pekne nakreslení v rovine.
Veta 8.13. Každý jednoduchý rovinný graf lze nakreslit v rovine (bez kříZení hran) tak, Ze hraný jsou Usečký.
Petr Hliněný,  FI MU Brr
FI: MA010: Rovinnost a kreslení
8.4   Barvení map a rovinných grafů
Vzpomenme si na jiz zminovaný prevod mapy na graf - jedna se vlastne o vytvoren í dualn ího grafu k teto mape. Aby v dualn ím grafu k mape nevznikly smyčky, v mape nesm í zadný stat sousedit sam se sebou, coz je prirozeny pozadavek.
V roce 1976 Appel a Haken, a pak žnovu v roce 1993 Robertson, Seymour, Sanders a Thomas, dokažali tuto vetu, ktera rožřesila problem ctyř barev a ktera je jedním ž nejslavnejsích vysledku diskretní matematiky vubec:
Veta 8.14. Každý rovinný graf bež smýCek lže obarvit 4 barvami. c
Dukaž teto vety je nesmírne složity (vsak byl take hledan po více než 100 let a k jeho uplnemu provedení je stale treba pocítac), a proto si uvedeme slabsí a mnohem jednodussí tvržení:
Tvrzení 8.15. Každý rovinný graf bež smýCek lže obarvit 6 barvami. Každý rovinný graf bež smýCek a bež trojuhelníku lže obarvit 4 barvami. c
Důkaz: Podle Dusledku 8.4 najdeme v každem podgrafu G vrchol v stupne nejvyse 5, a tudíž je G 5-degenerovany a obarvíme jej podle Vety 7.6. Druhou část dokažeme obdobne, když naležneme vrchol stupne < 3. □
Petr Hliněný,  FI MU Brno 12 FI: MA010: Rovinnost a kreslení
Věta 8.16. Každý rovinní/ graf bez smyček ma výběrovou barevnost nejvýše 5. c
Necht rovinný graf G s vnejsí stenou ohraničenou kružnici C ma všechny ostatní steny trojúhelníky. Necht: každí/ vrchol mimo C má přiřazen seznam 5 barev, vrcholy C mají seznamy 3 barev a jiste dva sousední vrcholy x,y na C mají přímo předepsane (ruzní) barvy. Pak G lze vyberove obarvit.
• Necht z = y je druhy soused x na C. Pokud nektera hrana f ze z nenalezej íc í C ma druhy konec take na C, pak podel f „rozdel íme" G na podgraf Gi obsahuj íc í x,y a podgraf G2 sd ílej íc í hranu f s G1. Indukc í nejprve obarvíme G1, pak G2 taktez spln í indukcn í předpoklad a i jej dobarvíme.
• Jinak budeme indukcí barvit podgraf G3 = G — z; přicemz vsem sousedum z uvnitřr G odebereme ze seznamu (jejich přeti) barev dvře z barev seznamu u vrcholu z mzne od barvy x. Nasledne dobarvíme vrchol z, pro nejz mame tri moznosti a jen jeho dva sousede na C s n ím mohou byt v konfliktu.
lze dokazat nasleduj íc í zes ílene tvrzen í:
□
V
Petr Hliněný,  FI MU Brr
FI: MA010: Rovinnost a kreslení
8.5   Prakticke „pružinove" kreslen í grafU
Zíverem se podívejme na trochu jinou problematiku - jak prakticky nakreslit dany (nerovinny) graf, aby vse „vypadalo hezky".
Jeden ze základních heuristickych prístupu ke kreslení grafu se da shrnout následovne:
Metoda 8.17. Pružinove kreslen í grafu
• Vytvoríme „fyzikalní" model grafu, kde vrcholy budou kulickami, ktere se vzajemne odpuzují, a hrany budou pruzinami, ktere sve koncove vrcholy vzajemne
• Nas model budeme iterovat jako dynamicky system, az do konvergence pozic vrcholu. Zde je potrebne modelovat i „tlumení" pohybu vrcholu, aby nedoslo k rozkmitaní systemu. c
• I kdyz kreslíme graf do roviny, je uzitecne začít modelovat system s dimenzí navíc (aby mely vrcholy „více místa k pohybu") a teprve v pmbehu casu dodatecnou silou přidanou dimenzi „eliminovat", neboli zkonvergovat pozice vrcholu do zvolene roviny.
přitahují. c
V
Petr Hliněný,  FI MU Brr
FI: MA010: Rovinnost a kreslení