Recepty z programátorské kuchařky
Rovinné grafy

Na úvod položme otázku: „Stačí čtyři barvy na obarvení libovolné politické mapy, aby žádné dva sousedící státy neměly stejnou barvu?“ Za sousedící státy se nepovažují ty, které sousedí jen v jediném bodě (ba ani v konečně mnoha).

Na první pohled jednoduchá otázka, že? Matematici se s ní však trápili více jak století (od první formulace v roce 1852 do vyřešení v roce 1976) a nikdo nebyl schopen přijít s důkazem ani s protipříkladem, tedy mapou, na níž je potřeba pět barev. Třeba i na tuto mapu jsou potřeba jen čtyři barvy:

Nebudeme dlouho tajit odpověď: čtyři barvy stačí. Důkaz se spoléhá na strojové probírání stovek případů (fragmentů rovinných grafů) a ve své době pro svou domnělou nematematičnost vzbudil velké pozdvižení. Dodnes se snaží mnoho vědců najít jednodušší důkaz, podobně jako u Velké Fermatovy věty.

My si ukážeme, jak každou politickou mapu obarvit šesti barvami, a od toho přejdeme k pěti barvám. Nejdříve si však převedeme politické mapy na rovinné grafy a předvedeme si několik jejich užitečných vlastností.

Cvičení

• U státu se v úvodní otázce tiše předpokládá, že je souvislý, tedy mezi každými dvěma místy v něm lze přejít bez přechodu do jiného státu. Rozmyslete si, jak by vypadala mapa s nesouvislými státy, na niž je potřeba pět barev.

Rovinné grafy

Rovinný graf (někdy též nazývaný planární) je graf, který můžeme nakreslit do roviny bez křížení hran. To znamená, že vrcholům přiřadíme vhodné body a hrany nakreslíme jako křivky spojující příslušné body tak, že se žádné dvě křivky neprotínají mimo své krajní body.

Ne každý graf lze takto nakreslit – sami si rozmyslete, že například graf K₅, což je 5 vrcholů spojených každý s každým, žádné rovinné nakreslení nemá. Na druhou stranu například každý strom určitě rovinný je.

Vezměme si tedy nějaký graf a jeho rovinné nakreslení, například tento:

Hrany nakreslení dělí rovinu na několik oblastí, těm budeme říkat stěny. Náš graf má 6 stěn: jednu čtvercovou, čtyři „trojúhelníkové“ (tedy ohraničené třemi hranami, byť to nejsou vždy úsečky) a jednu 6-úhelníkovou (to je celý zbytek roviny okolo grafu, tzv. vnější stěna).

Například libovolné rovinné nakreslení stromu by mělo pouze jednu stěnu, a to tu vnější. Všimněte si, že pokud v grafu nejsou mosty ani artikulace, je každá stěna ohraničena nějakou kružnicí. (Pozor, to, jak vypadají stěny, závisí na konkrétním nakreslení do roviny!)

Barvení grafů

Jistě byste dokázali vymyslet převod politické mapy se státy na graf. Jen pro úplnost: samotné státy budou vrcholy a hrana povede mezi vrcholy právě tehdy, když odpovídající státy sousedí.

Podobně jako se barví politické mapy, lze barvit i grafy. Samozřejmě ne doslova, barvením se zpravila myslí přiřazování přirozených čísel jednotlivým vrcholům pod podmínkou, že sousední vrcholy nesmí mít stejnou barvu. Důležitou vlastností grafu je pak jeho barevnost, neboli nejmenší počet barev, kterými se dá obarvit. Úvodní problém tedy vlastně říká, že barevnost každého rovinného grafu je nejvýše čtyři.

V praxi má barvení grafů (nejen rovinných) velké využití. Jako příklad si můžeme vzít určování frekvencí vysílačů mobilního signálu, kdy dva na sebe vidící vysílače nemohou dostat stejnou frekvenci. Zároveň chceme jako operátor použít co možná nejméně frekvencí to jde, a tak pro mapu sousedících vysílačů chceme vysílače „obarvit“ frekvencemi tak, aby měly každé dva sousedící vysílače jinou.

Dobré je poznamenat, že tato úloha může být chápána jako úloha na rovinných i nerovinných grafech – ve městské zástavbě docela často najdeme alespoň pětici vysílačů, kde na sebe každé dva vysílače vidí.

Cvičení k zamyšlení

• Rozmyslete si, že graf vytvořený z politické mapy je skutečně rovinný, tzn. že tento graf lze zakreslit do roviny tak, že se nekříží jeho hrany.
• Představte si, že máte algoritmus, který obarví vstupní graf daným počtem barev, pokud to jde. Jak pomocí něj vyřešit sudoku?
• U grafů se studuje i barvení hran (hrany nesmí mít stejnou barvu, pokud sdílejí vrchol). Zkuste si rozmyslet, jak vrcholová i hranová barevnost souvisí s maximálním stupněm grafu (např. najít horní omezení v závislosti na maximálním stupni, u hranové i dolní omezení).

Vlastnosti rovinných grafů

O rovinných grafech platí několik důležitých vět, které se často hodí při vytváření grafových algoritmů.

Je zřejmé, že každý strom je rovinný. Navíc pro každý strom platí, že má o jedna méně hran než vrcholů (tedy e=v-1, kde v je počet vrcholů a e počet hran). Proč tomu tak je? Abychom tvrzení dokázali, použijeme indukci podle počtu vrcholů – ukážeme platnost tvrzení pro strom s jedním vrcholem a potom s použitím indukčního předpokladu (že tvrzení platí pro všechny stromy s méně jak v vrcholy) dokážeme tvrzení i pro strom s v vrcholy.

Pro strom s jedním vrcholem formulka určitě platí. Strom s v>1 vrcholy má jistě list, tak jej odtrhneme (poněkud vandalské, nicméně účinné), čímž získáme strom s menším počtem vrcholů, pro který podle indukčního předpokladu formulka platí, a opětovným přidáním listu platit nepřestane, protože k oběma stranám přičteme jedničku. Dokázáno.

Vztah počtu vrcholů, hran a stěn

Počet stěn souvislého rovinného grafu je pevně určen počtem vrcholů a hran, aniž by záleželo na konkrétním nakreslení do roviny nebo dokonce na tom, mezi kterými vrcholy hrany vedou. Pro každý souvislý rovinný graf nakreslený do roviny totiž platí tzv. Eulerova formule uvádějící do vztahu počet vrcholů v, počet hran e a počet stěn f:

Důkaz: Opět indukcí, tentokráte podle počtu hran. Každý souvislý graf má alespoň v-1 hran, a pokud jich má právě tolik, je to strom. Protože každé rovinné nakreslení stromu má právě jednu stěnu, tak bude v tomto případě Eulerova formule platit.

Pokud máme nakreslení grafu, který je souvislý a není to strom, znamená to, že obsahuje alespoň jednu kružnici. A každá hrana na kružnici jistě odděluje nějaké dvě stěny. Zvolme si tedy nějakou takovou hranu h a z grafu ji odeberme. Tím získáme graf s menším počtem hran (opět nakreslený do roviny), použijeme indukční předpoklad, Eulerova formule pro něj tedy již platí, a vrátíme hranu zpět. Levá strana rovnosti se tím zvětší o 1 (přidali jsme stěnu), pravá také (přidali jsme hranu), tedy rovnost stále platí.

Cvičení k zamyšlení

• Dokažte, že Eulerova formule pro grafy s k komponentami je:
  v+f=e+k+1

Omezení počtu hran

Intuicí snadno odhalíte, že velké rovinné grafy nemohou mít spoustu hran, protože by nešly nakreslit bez křížení. Hran je dokonce lineárně, protože platí následující nerovnost (pro grafy s alespoň třemi vrcholy):

Nejprve jednoduchá aplikace: výše jsme zmínili, že K₅ (úplný graf na 5 vrcholech) není rovinný. Má totiž 10 hran, ale naše formulka mu dovoluje jen 9. Takto se dá o spoustě „hustých“ grafů dokázat, že nejsou rovinné, bohužel však tvrzení neplatí obráceně a existují grafy s 3v-6 vrcholy (nebo méně), které nejsou rovinné.

Pěkným příkladem je vzít si třeba nerovinný K₅ a přidat mu k jednomu vrcholu ocásek. I ocásek o pouze jednom vrcholu způsobí, že hran bude 11, vrcholů 6 a nerovnost tak bude splněna, ale graf je nerovinný.

Důkaz: Jak tuto nerovnost dokázat? Zvolme si libovolné nakreslení grafu do roviny. Nejprve předpokládejme, že je to triangulace, čili že každá stěna je trojúhelník. V takovém grafu patří každá hrana k právě dvěma trojúhelníkovým stěnám, takže e=f·3/2, čili f=e·2/3. Dosazením do Eulerovy formule získáme v+(2/3)e=e+2, tedy e=3v-6.

Není-li náš graf triangulace, může to mít několik důvodů. Není souvislý (pak ale stačí větu dokázat pro jednotlivé komponenty a nerovnosti sečíst), nebo je moc malý (má nejvýše dva vrcholy, ale tak malé grafy neuvažujeme) anebo obsahuje nějakou stěnu ohraničenou více než třemi hranami. Dovnitř takové stěny ovšem můžeme dokreslit další hrany a tím ji rozdělit na trojúhelníčky. Tím tedy dokážeme graf doplnit hranami na triangulaci a pro tu, jak už víme, platí dokonce rovnost. Když přidané hrany opět odebereme, snížíme pouze počet hran a uděláme tak z rovnosti nerovnost.

Cvičení k zamyšlení

• Rovinné grafy bez trojúhelníkové stěny (tedy ty, co neobsahují K₃ jako podgraf) mají dokonce maximálně 2v-4 hran. Důkaz tentokrát ponecháme na vás.
• Lze pro každé v najít rovinný graf s v vrcholy a 3v-6 hranami?

Vrchol nízkého stupně

Dokážeme, že v každém rovinném grafu existuje vrchol stupně maximálně 5 (stupeň vrcholu je počet hran, které do vrcholu vedou). Proč tomu tak musí být? Kdyby všechny vrcholy měly stupeň alespoň 6, byl by součet stupňů alespoň 6v. Jenže součet stupňů je přesně dvojnásobek počtu hran (každá hrana má dva konce), takže e≥ 3v, což je spor s předchozí větou.

Cvičení

• Najděte rovinný graf, který má všechny stupně 5.
• Tvrzení o vrcholu nízkého stupně platí jen pro konečné grafy. Najděte nekonečný rovinných graf, jehož všechny vrcholy mají stupeň 6. Dokážete totéž i pro stupeň 42?

Natíráme 6 barvami

Konečně máme všechny potřebné ingredience (i se zdůvodněním, abyste nám věřili) a můžeme se pustit do barvení. Jelikož máme zaručený vrchol stupně maximálně 5, vezmeme ho, odebereme z grafu a zařadíme na zásobník. Odebráním se určitě neporušila rovinnost grafu, takže vezmeme další vrchol stupně maximálně 5. Takto pokračujeme rekurzivně, dokud nerozebereme celý graf a nenaskládáme všechny vrcholy na zásobník.

Jelikož jsme odebírali vrcholy stupně maximálně 5, má každý vrchol na zásobníku nad sebou nejvýše 5 sousedů v původním grafu. Z toho už je patrný barvící algoritmus: budeme postupně odebírat z vrchu zásobníku a u každého vrcholu máme jistotu, že mezi jeho sousedy chybí jedna barva (některé sousední vrcholy jsou samozřejmě ještě neobarvené, ale obarvených je maximálně 5).

Co se týče implementace, jediným problémem je hledání vrcholů stupně 5 a méně. Řešení však není těžké na vymyšlení, ani na programování: stačí na začátku naskládat všechny vrcholy stupně maximálně 5 do nějaké datové struktury (hodí se třeba fronta) a potom si uvědomit, že při odebírání vrcholu z grafu je potřeba se podívat jen na jeho sousedy, jestli jim neklesl stupeň na 5.

Jak rychle tento algoritmus poběží na grafu s N vrcholy a M hranami? Nejprve si trochu zjednodušíme odhady, protože víme, že počet hran je v rovinných grafech omezený počtem vrcholů – stačí nám tak v odhadech počítat pouze s N.

Na začátku si potřebujeme u každého vrcholu spočítat stupeň a všechny vrcholy stupně maximálně 5 přidat do fronty, což zvládneme v čase O(N). Pak již jen bereme vrcholy z fronty, přidáváme je do zásobníku a přitom aktualizujeme stupně sousedů. Když se nějaký soused dostane také na stupeň 5, tak ho přidáme do fronty.

Každý vrchol přidáme i odebereme z fronty právě jednou, takže přitom strávíme také čas O(N). A nakonec vybírání vrcholů ze zásobníku a jejich barvení také zvládneme v O(N), tedy i celý algoritmus stihneme za čas O(N).

Třešnička na dortu: 5 barev

Algoritmus na obarvení rovinného grafu 5 barvami má stejný průběh jako předchozí představený, tedy se postupně rozebírá graf (mimo jiné se odebírají vrcholy) a potom se barví vrcholy v obráceném pořadí, než se zpracovávaly. Jenže tentokrát nelze přímočaře obarvit vrcholy stupně 5 (s vrcholy s menšími stupni můžeme zacházet stejně).

K vyřešení problému se nám bude hodit operace kontrakce hrany, která jednu danou hranu odstraní a spojí její dva koncové vrcholy u,v do nového vrcholu w. Hrany vedoucí z u a v do jiných vrcholů nyní povedou z w, násobné hrany se smažou (tzn. pokud u a v měly společného souseda, z w do něj povede jen jedna hrana).

Prvně je důležité pozorování, že mezi sousedy vrcholu v stupně 5 v rovinném grafu, existuje alespoň jedna dvojice vrcholů, mezi kterými nevede hrana. (Kdyby tomu tak nebylo, obsahuje tento graf K₅ jako podgraf, a tudíž nemůže být rovinný.) Najdeme tedy dvojici x,y sousedů v, která není spojena hranou, a místo odstranění v provedeme kontrakci hran xv a yv do vrcholu w. Vrchol v přidáme na zásobník (při implementaci se hodí také uložit, jaké hrany se zkontrahovaly) a pokračujeme rekurzivně s kontrahovaným grafem.

Při samotném obarvování, narazíme-li na zkontrahovaný vrchol v, máme už obarvený vrchol w vzniklý kontrakcí (nechť má například barvu 1). Jelikož sousedi w zahrnují sousedy vrcholů x a y, dáme těmto dvěma vrcholům barvu 1 a žádný jejich soused určitě už nedostal stejnou barvu. Vrcholu v pak přidělíme jinou barvu, kterou nemají jeho 3 zbývající sousedi, ani x (tedy ani y). Barev je 5, takže to akorát vyjde.

Tím jsme zakončili povídání o barvicích algoritmech, samotnou implementaci ponecháme čtenáři jako cvičení.

Poznámky

• Kdybychom definici rovinného nakreslení změnili a dovolili hrany kreslit pouze jako úsečky místo libovolných křivek, překvapivě se nic nezmění: každý rovinný graf má rovinné nakreslení, v němž jsou všechny hrany úsečky. Ale není to zrovna jednoduché dokázat.
• Stejně jako do roviny bychom mohli grafy kreslit třeba na povrch koule. Tím se také nic nezmění, zkuste sami vymyslet, jak z rovinného nakreslení udělat „kulové“ a naopak. Ale třeba anuloid (povrch pneumatiky) se už chová jinak, například zmíněný nerovinný graf K₅ se na anuloid dá nakreslit bez křížení hran.
• Jak poznat, jestli je daný graf rovinný, nebo ne? Tak, že nalezneme jeho nakreslení v rovině, ale rychlý algoritmus není vůbec jednoduchý. Více o tomto problému se dočtete například na anglické Wikipedii pod heslem Planarity testing nebo ve skriptíčkách Krajinou grafových algoritmů od Martina Mareše.
• Při pohledu na mapu států lze vidět také jiný rovinný graf. Ten má jako vrcholy body, kde se střetávají hranice tří nebo více států, a hrany v rovinném nakreslení tohoto grafu vedou po hranicích. Vztah druhého rovinného grafu na mapě k prvnímu má svou abstrakci v teorii grafů: duální graf rovinného grafu má vrcholy odpovídající stěnám původního grafu a hrana mezi nimi vede, právě když v původním rovinném grafu spolu stěny sousedí. Sami si ověřte, že oba grafy jsou vůči sobě navzájem duální. Malé cvičení: jak vypadá duální graf duálního grafu nějakého rovinného grafu? (Tedy dvakrát uděláme z grafu duální graf.)
• Více informací o teorii (nejen rovinných) grafů najdete například v knize Jiřího Matouška a Jaroslava Nešetřila Kapitoly z diskrétní matematiky či v knížce Grafy a jejich aplikace od Jiřího Demela.

Pavel Veselý, Martin Mareš a Petr Škoda

Menu