Petr Hliněný, FI MU Brno 1 FI: MA010: Rovinnost a kreslení
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ě:
1
1 2
3 4
2
3
1
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.2
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.
Petr Hliněný, FI MU Brno 2 FI: MA010: Rovinnost a kreslení
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í. 2
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.
s s
ss
s s
ss
s s
s
s
s s
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ý, FI MU Brno 3 FI: 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.
s
s
s
s
s
s s
s
s
s
s
s
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.11Jednoznačnost rovinného
nakreslenítheorem.8.11). 2
Definice. Duální 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í graf k rovinnému grafu je vždy rovinný, což je snadné dokázat.
s s
s
s
s s
s
s
Petr Hliněný, FI MU Brno 4 FI: MA010: Rovinnost a kreslení
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 .2
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 +1 -(v-1) = 2.
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 Jordanova 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 + (f - 1) - (e - 1) = 2.
Tvrzení tak plyne z principu matematické indukce. 2 2
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.
Petr Hliněný, FI MU Brno 5 FI: MA010: 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.2
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 f 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í e  1
2 3f, neboli 2
3 e  f.
Dosazením do vztahu Věty 8.2Rovinné kreslení grafutheorem.8.2 získáme
2 = v + f - e  v +
2
3
e - e = v -
1
3
e
e  3(v - 2) = 3v - 6 .2
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í e  1
2 4f, neboli
2
4 e  f. Dosazením do vztahu Věty 8.2Rovinné kreslení grafutheorem.8.2 získáme
2 = v + f - e  v +
2
4
e - e = v -
1
2
e
e  2(v - 2) = 2v - 4 .
Tím jsme hotovi. 2
Petr Hliněný, FI MU Brno 6 FI: MA010: Rovinnost a kreslení
Důsledek 8.4. Každý rovinný graf obsahuje vrchol stupně nejvýše 5.
Každý rovinný graf bez trojúhelníků obsahuje vrchol stupně nejvýše 3. 2
Důkaz: Pokud by všechny vrcholy měly stupně alespoň 6, celý graf by měl aspoň
1
2  6v = 3v hran, což je ve sporu s Důsledkem 8.3Rovinné kreslení grafutheorem.8.3.
Některý vrchol musí tudíž mít menší stupeň než 6.
Obdobně postupujeme u druhého tvrzení. 2
Petr Hliněný, FI MU Brno 7 FI: MA010: Rovinnost a kreslení
8.2 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. 2
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ý, FI MU Brno 8 FI: MA010: Rovinnost a kreslení
Příklad 8.6. Ukažme, že následující dva grafy, K5 a K3,3 nejsou rovinné.
K5 s s
s
s
s
K3,3 s s s
s s s
2
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 > 35- 6 hran. Podobně graf K3,3 má 6 vrcholů a 9 > 26- 4 hran, přitom neobsahuje
žádné trojúhelníky. Proto podle Důsledku 8.3Rovinné kreslení grafutheorem.8.3 žádný z nich
není rovinný. 2 2
Důsledek 8.7. Grafy K5 a K3,3 nejsou rovinné. 2
Definice: Podrozdělením grafu G rozumíme graf, který vznikne z G rozdělením některých
hran novými vrcholy stupně 2.
s s
s
s
s
s
s
s
s s s
s s s
s
s s
Důležitý abstraktní popis všech rovinných grafů nalezl K.Kuratowski:
Petr Hliněný, FI MU Brno 9 FI: MA010: Rovinnost a kreslení
Věta 8.8. Graf G je rovinný právě když neobsahuje podrozdělení grafů K5 nebo K3,3
jako podgrafy.
Petr Hliněný, FI MU Brno 10 FI: 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.
A s s
ss
s s
B s s
ss
s s
s
2
Po chvíli zkoumání určitě přijdeme na to, že graf A se dá nakreslit rovinně takto:
s s
ss
s s
a b
cd
x y
 s s
s
s
s s
a b
c
d
x y
Graf B na druhou stranu rovinný není podle Věty 8.8Rozpoznání rovinných grafůtheorem.8.8,
protože je v něm obsaženo podrozdělení grafu K3,3, které je ukázáno na tomto obrázku:
s
ss
s s
s
2
Petr Hliněný, FI MU Brno 11 FI: MA010: Rovinnost a kreslení
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. 2
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ž podgraf G - V (C) je souvislý graf. 2
Důkaz: V jednom směru, pokud G
= G - V (C) je souvislý, pak podle Jordanovy 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 .................. 2 2
Důsledek 8.11. Každá dvě rovinná nakreslení 3-souvislého grafu jsou ekvivalentní.
Petr Hliněný, FI MU Brno 12 FI: MA010: Rovinnost a kreslení
Závěrem si ještě bez důkazu uvedeme, že rovinné grafy vždy mají "pěkné" nakreslení
v rovině.
Věta 8.12. Každý jednoduchý rovinný graf lze nakreslit v rovině (bez křížení hran)
tak, že hrany jsou úsečky.
Petr Hliněný, FI MU Brno 13 FI: MA010: Rovinnost a kreslení
8.3 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.13. Každý rovinný graf bez smyček lze obarvit 4 barvami. 2
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.14. 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. 2
Důkaz: Podle Důsledku 8.4Rovinné kreslení grafutheorem.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.5. Druhou část dokážeme obdobně, když nalezneme vrchol stupně  3. 2
Petr Hliněný, FI MU Brno 14 FI: MA010: Rovinnost a kreslení
Věta 8.15. Každý rovinný graf bez smyček má výběrovou barevnost nejvýše 5. 2
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, na C jsou
seznamy 3 barev a jisté dva sousední vrcholy na C mají přímo předepsané (různé)
barvy. Pak G lze výběrově obarvit.
................. 2
Petr Hliněný, FI MU Brno 15 FI: MA010: Rovinnost a kreslení
8.4 O průsečíkovém čísle grafů
Třebaže již dobře víme (a umíme algoritmicky rozpoznat), které grafy jsou rovinné,
praxe požaduje ,,hezká nakreslení i nerovinných grafů do roviny. Jak tedy na hezká
kreslení nerovinných grafů do roviny? 2
Definice (rozšíření Definice 8.1Rovinné kreslení grafutheorem.8.1):
Nakreslením grafu G do roviny rozumíme zobrazení, ve kterém jsou vrcholům G přiřazeny
různé body roviny a hranám jednoduché křivky spojující koncové vrcholy. Přitom
je požadováno, aby se žádné tři hrany neprotínaly v jednom bodě (jiném než koncový
vrchol), aby žádná hrana neprocházela jiným vrcholem a aby se každá protínající dvojice
hran skutečně ,,křížila (tj. ne jednostranný dotyk).
Příklad 8.16. Podívejme se na následující tři (korektní) nakreslení do roviny. Jsou všechna
,,optimální , tj. je počet jejich křížení nejmenší možný?
s s
ss
s s
ss
s
s
s
s
s
s
s
s
s
s
2
Snadno vidíme, že první graf lze nakreslit i bez křížení a druhý graf jen s jedním křížením.
Naopak třetí graf už s méně kříženími nakreslit nelze. Uměli byste toto dokázat? 2
Petr Hliněný, FI MU Brno 16 FI: MA010: Rovinnost a kreslení
Definice 8.17. Průsečíkové číslo grafu G v rovině
je definováno jako nejmenší možný počet křížení dvojic hran přes všechna korektní
nakreslení G do roviny. Značíme cr(G).
Původ problému průsečíkového čísla spadá do doby druhé světové války, kdy P. Turán
byl na nucených pracech v cihelně. Jejich úkolem bylo tlačit vozíky s cihlami po kolejnicích
a na každé křižovatce s tím měli velké problémy. Proto Turán přemýšlel, jak
navrhnout kolejiště lépe, aby minimalizoval počet křížení kolejnic.
V dnešní době je problém průsečíkového čísla velmi důležitý v praktických oblastech
VLSI designu [Leighton] a ,,lidsky čitelné vizualizace grafů v různých schématech.
Petr Hliněný, FI MU Brno 17 FI: MA010: Rovinnost a kreslení
Příklad 8.18. Určeme průsečíková čísla následujících dvou grafů:
s s
s
s
s
s s
s
s
s
s s
s
s s
s
2
Asi snadno každý nalezne nakreslení prvního grafu (Petersenův) s pouze dvěma kříženími
hran. Jak však dokázat, že jej nelze nakreslit s jedním křížením? Všimněme si, že
každá jeho hrana je ,,ekvivalentní s každou jinou. To znamená, že by ostraněním jedné
zvolené hrany z Petersenova grafu mělo vytvořit rovinný graf, ale to není pravda. 2
Druhý graf K6 lze nakreslit s 3 kříženími ­ začněme s kružnicí délky 5 a posledním
vrcholem spojeným uvnitř. Zbylých 5 hran pak už dokážeme dokreslit s vytvořením tří
křížení. Zkuste si to! Proč není možných méně křížení? Předpokládejme, že dvě křížení
hran postačují, pak bychom vypuštěním dvou dotčených hran získali rovinný graf. Ten
by však měl 6 vrcholů a 13 > 3  6 - 6 hran, spor. 2
Petr Hliněný, FI MU Brno 18 FI: MA010: Rovinnost a kreslení
Fakt: Přesné obecné hodnoty průsečíkových čísel nejsou známy ani pro úplné či úplné
bipartitní grafy. 2
Věta 8.19. Problém určit, zda průsečíkové číslo cr(G)  k pro G a k na vstupu je
NP-úplný. Toto platí dokonce i když G je kubický 3-souvislý graf.
Zamyslete se sami, proč by problém průsečíkového čísla měl vůbec náležet do třídy
NP, není to tak zřejmé. . . 2
V praxi se ukazuje, že určení průsečíkového čísla je přímo zoufale těžký problém, ještě mnohem
beznadějnější než třeba barevnost. Snad jediným existujícím ,,pozitivním (i když zcela
nepraktickým) algoritmickým výsledkem je následovné:
Věta 8.20. (Grohe) Pro fixní k lze otestovat, zda cr(G)  k, v polynomiálním kvadratickém
čase vzhledem k počtu vrcholů grafu.
(2006: Dnes je známo i vylepšení v lineárním čase.) 2
Poznámka: Dnes zatím ani nevíme, jak v polynomiálním čase přesně určit průsečíkové číslo
grafu, který vznikne z rovinného grafu přidáním jedné hrany! (Umíme jen aproximovat s faktorem
daným největším stupněm grafu.)