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 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í.
• Trochu o praktickém kreslení grafů.
most a kresleni
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ý.)
most a kresleni
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). :
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.
most a kresleni
^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 stěn. Pak
\V(G)\+f-\E(G)\ = 2.n
Důkaz: Nechť počet vrcholů v G je f a hran h.
• Pokud je G strom, tj. nemá kružnice, má ve svém nakreslení jedinou stěnu (viz Jordánova věta o kružnici) a dle Věty 5.3 má přesně h — v — í hran. Potom platí
v + f- h = v + l-(v-l) = 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 + f — h — v + (/ — 1) — (h — 1) — 2.
Tvrzení tak plyne z principu matematické indukce. C
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.
Eulerův vztah má mnoho aplikací a důsledků.
Důsledek 8.3. Jednoduchý rovinný graf na v > 3 vrcholech má nejvýše 3t> — 6 hran. Jednoduchý rovinný graf na v > 3 vrcholech a bez trojúhelníků má nejvýše 2t> — 4 hran.
Důkaz: Můžeme předpokládat, že graf je souvislý, jinak bychom přidali další hrany. Nechť počet vrcholů v G je v, 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 > \ ■ 3/, neboli |/i > /. Dosazením do vztahu Věty 8.2 získáme
2 1
2=v+f-h<v+-h-h=v--h
J       ~      3 3
h < 30 - 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 |/i > /. 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. C
Poznámka: Kdy nastáva rovnost v Důsledku 8.3? Snadno analýzou důkazu zjistíme, že jednoduchý rovinný graf má 3u — 6 hran, právě když všechny jeho stěny včetně vnější jsou trojúhelníky. Obdobně pro druhou část tvrzení se všemi stěnami velikosti 4.
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ň \ -6f — 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í. C
most a kresleni
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. □
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.
most a kresleni
Příklad 8.6. Ukažme, že následující dva grafy, K$ a Kz,3 nejsou rovinné.
Při zdůvodnění využijeme znalosti předchozího oddílu. Všimněme si, že graf K$ má 5 vrcholů a 10 > 3 ■ 5 — 6 hran. Podobně graf Kz,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 K$ a        nejsou rovinné. □
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 podrozdělenígrafů K$ nebo jako podgrafy.
Příklad 8.9.
očíslovaných
Které z následujících dvou grafů jsou rovinné? Najděte rovinné nakreslení (včetně vrcholů), nebo zdůvodněte nerovinnost grafu.
Graf B na druhou stranu rovinný není podle Věty 8.8, protože je v něm obsaženo podrozdělení grafu 7^3,3, které je ukázáno na tomto obrázku:
Jednoznačnost rovinného nakreslení
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. □
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. □
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. C
Důsledek 8.11. Každá dvě rovinná nakreslení 3-souvislého grafu jsou ekvivalentní.
most a kresleni
Použití pro isomorfismus
Zajímavou aplikací Důsledku 8.11 je algoritmus pro rozpoznávání isomorfismu 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í isomorfismu stromů:
Věta 8.12. Problém isomorfismu 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.
most a kresleni
8.4   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. □
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.
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.7. Druhou část dokážeme obdobně, když nalezneme vrchol stupně < 3. Ľ
Věta 8.16. Každý rovinný graf bez smyček má výběrovou barevnost nejvýše 5. □
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í stěny 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ýběrově obarvit.
• Nechť z ^ 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 G2 sdílející hranu / s G\. Indukcí nejprve obarvíme G\, pak G2 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.
C
most a kresleni
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. □
• 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.
most a kresleni