Rovinný graf a steny
Graf je rovinný (planárny), ak sa dá nakresliť do roviny tak, že sa žiadne dve hrany nekrížia — pretínajú sa nanajvýš vo svojich spoločných vrcholoch. Takému konkrétnemu nakresleniu hovoríme rovinné vnorenie.
Pozor na rozdiel: rovinný je graf už vtedy, keď existuje aspoň jedno nakreslenie bez kríženia. Pokojne ho môžeš nakresliť aj „škaredo" s krížením — dôležité je, že sa kríženia dajú odstrániť.
Vrcholy a hrany
Graf G = (V, E): množina vrcholov V a množina hrán E. Počty značíme v = |V|, e = |E|.
Steny (oblasti)
Rovinné vnorenie rozdelí rovinu na steny — súvislé oblasti ohraničené hranami. Ich počet značíme f.
Vonkajšia stena
Práve jedna stena je neohraničená — ten nekonečný priestor „okolo" grafu. Aj tú počítame do f.
Pre malý príklad si predstav trojuholník s jedným vrcholom v strede (graf K₄). Vnútri vzniknú tri menšie trojuholníkové oblasti a okolo všetkého je vonkajšia stena — spolu 4 steny.
Trojuholník s vrcholom v strede — tri vnútorné steny (S₁, S₂, S₃) a vonkajšia stena S₄.
Každá stena má stupeň — počet hrán na jej hranici (most na hranici sa počíta dvakrát). Súčet stupňov všetkých stien sa rovná 2e, podobne ako pri stupňoch vrcholov.
Vyber správnu odpoveď.
Eulerova formula
Pre každý súvislý rovinný graf platí krásny a jednoduchý vzťah medzi počtom vrcholov, hrán a stien:
v − e + f = 2
vrcholy − hrany + steny = 2. Číslo 2 nezávisí od toho, ako graf nakreslíš — je rovnaké pre každé rovinné vnorenie.
Najľahšie si formulu zapamätáš na strome. Strom je súvislý graf bez kružníc, má e = v − 1 hrán a jedinú stenu (vonkajšiu), teda f = 1:
v − e + f = v − (v − 1) + 1 = 2 ✓
Dôsledok pre hrany
Z formuly a z odhadu stupňov stien vyplýva pre súvislý jednoduchý graf s v ≥ 3 horný odhad e ≤ 3v − 6.
Invariant
Ľavá strana v − e + f je topologický invariant roviny (resp. gule) — vždy 2, nech počítaš akokoľvek.
Spočítame v, e, f pre rovinné vnorenie K₄ a dosadíme do formuly. Klikaj.
Vyber správnu odpoveď.
Neplanárne grafy a Kuratowski
Nie každý graf je rovinný. Dva najmenšie „previnilci" sú K₅ (úplný graf na 5 vrcholoch) a K₃,₃ (úplný bipartitný graf 3+3) — tie sa nakresliť bez kríženia nedajú.
K₅
Päť vrcholov, každý spojený s každým — spolu 10 hrán. Keďže 10 > 3·5 − 6 = 9, porušuje odhad e ≤ 3v − 6, a teda nie je rovinný.
K₃,₃
Tri „domy" a tri „studne", každý dom spojený s každou studňou (9 hrán). Tiež nie je rovinný — klasická úloha „tri domy, tri studne".
Graf je rovinný ⇔ neobsahuje podrozdelenie grafu K₅ ani grafu K₃,₃. (Podrozdelenie = na hrany pridáme nové vrcholy stupňa 2.) Inými slovami, K₅ a K₃,₃ sú jediné podstatné prekážky planárnosti.
Pre súvislý jednoduchý graf s v ≥ 3 musí platiť e ≤ 3v − 6. Ak je hrán viac, graf určite nie je rovinný. Pozor: opak neplatí — splnenie odhadu planárnosť ešte nezaručuje (napr. K₃,₃ má e = 9 ≤ 3·6 − 6 = 12, a aj tak nie je rovinný).
Vyber správnu odpoveď.
Farbenie grafov
Farbenie vrcholov grafu priradí každému vrcholu farbu tak, aby žiadne dva susedné vrcholy (spojené hranou) nemali rovnakú farbu. Pýtame sa: koľko farieb najmenej stačí?
Korektné farbenie
Priradenie farieb, pri ktorom má každá hrana dva rôznofarebné konce. Vrcholy bez hrany medzi sebou môžu mať tú istú farbu.
Chromatické číslo χ(G)
Najmenší počet farieb, ktorý stačí na korektné zafarbenie grafu G. Čím „prepojenejší" graf, tým väčšie χ.
Šesť vrcholov v kruhu — striedaním dvoch farieb (plná / prázdna) susedia nikdy nesplynú, takže χ(C₆) = 2.
Niekoľko užitočných hodnôt, ktoré sa oplatí poznať naspamäť:
| Graf | χ(G) | Prečo |
|---|---|---|
| Úplný graf Kₙ | n | každé dva vrcholy susedia |
| Strom (≥ 2 vrcholy) | 2 | striedame dve farby po úrovniach |
| Párna kružnica C₆ | 2 | striedanie dvoch farieb vyjde |
| Nepárna kružnica C₅ | 3 | pri striedaní sa posledný stretne s prvým |
Klikni a over si hodnotu χ(G).
Vyber správnu odpoveď.
Veta o štyroch farbách a bipartitné grafy
Spojme obe línie lekcie dokopy. Rovinnosť totiž farbenie veľmi obmedzuje — a pri dvoch farbách dostaneme úplne presnú charakterizáciu.
Každý rovinný graf sa dá zafarbiť najviac štyrmi farbami: χ(G) ≤ 4. (Práve preto na mape vždy stačia štyri farby, aby susedné štáty mali rôznu farbu.)
Druhý extrém je farbenie iba dvoma farbami. To je presne bipartitnosť: vrcholy vieš rozdeliť na dve skupiny tak, že každá hrana ide medzi skupinami (nikdy vnútri jednej).
G je bipartitný ⇔ χ(G) ≤ 2 ⇔ G neobsahuje nepárnu kružnicu
Práve nepárna kružnica je jediná prekážka, ktorá ti zabráni vystačiť s dvoma farbami.
χ ≤ 4
platí pre každý rovinný graf — slávny výsledok (Appel a Haken, 1976).
χ ≤ 2
⇔ graf je bipartitný ⇔ bez nepárnej kružnice. Napr. C₆, stromy.
Pozor: C₅
nepárna kružnica, takže nie je bipartitná a χ(C₅) = 3.
Vyber správnu odpoveď.
Záverečný kvíz
Desať otázok cez celú tému — od stien a Eulerovej formuly cez K₅ a K₃,₃ až po chromatické číslo a štyri farby.
Otestuj sa cez celú tému.