— — Rovinné grafy

Rovinné grafy

Oblouk: Množina bodů {γ(x) : x ∈ [0, 1]}, přičemž γ: [0, 1] → ℝ^{2} (rovina) je prosté a spojité zobrazení.

Definice:

Graf G = (V, E) je rovinný, má-li rovinné nakreslení: Vrcholy odpovídají různým bodům v ℝ^{2}, hrany odpovídají obloukům spojujícím příslušné

dvojice vrcholů tak, že mají-li dva oblouky společný bod, potom je tento bod pro oba oblouky koncový.

Příklady:

(i) K_{4} je rovinný (ii) C_{n} je rovinná (iii) Libovolný strom

Je známo: Každý rovinný graf má rovinné nakreslení, v němž hrany odpovídají úsečkám. (Důkaz těžký.)

Definice:

Stěny rovinného nakreslení: Maximální souvislé oblasti množiny ℝ^{2}\X, kde X je množina bodů ležících na obloucích nakreslení. (Souvislost bereme intuitivně.)

Příklad:

Vezmeme-li K_{4}, pak stěny jsou vlastně všechny oblasti mezi úsečkami i kolem celého grafu (má tedy 4 stěny).

Vnější stěna: Jedna neomezená stěna, která existuje pro každý rovinný graf. Vnitřní stěny: Ostatní stěny.

Definice:

Topologická kružnice: Uzavřený “oblouk” (tj. γ(0) = γ(1)).

Příklad:

Obrázky. (Šneci a měňavky. ;-)

VĚTA (Jordanova věta o kružnici):

Libovolná topologická kružnice rozděluje rovinu na dvě souvislé oblasti (vnitřek a vnějšek dané kružnice).

(Důkaz těžký.)

VĚTA (Nerovinnost K_{5}):

Graf K_{5} není rovinný.

DŮKAZ:

Sporem. Nechť V = {1, 2, 3, 4, 5}. Obrázek: vezměme si vrcholy 1, 2, 3 a hrany mezi nimi. Ty vytvoří topologickou kružnici K.

(a) v_{4} leží uvnitř K: Pak ho umístíme do středu, ale pak kam s vrcholem V_{5}? Žádná stěna nemá na hranici všechny vrcholy 1, 2, 3, 4.

(b) v_{4} leží vně K: Můžeme převést na isomorfní graf s v_{4} uvnitř.

Q.E.D.

VĚTA (Nerovinnost K_{3,3}):

Graf K_{3,3} (úplný bipartitní graf o 3 + 3 vrcholech) není rovinný.

DŮKAZ:

V = {1, 2, 3, 1′, 2′, 3′} Spousta obrázků.

o 1 / “ / 3 “ 2’ o - -o- - o 1’ “ / “ / o 2

Kam s 3′? Q.E.D.

Pozorování:

G rovinný ⇔ každé dělení G je rovinné.

DŮKAZ:

Obrázkem K_{4}. Libovolně rozdělíme hrany, ale tím se nám nijak nezmění rovinnost.

VĚTA (Kuratowski):

G je rovinný ⇔ G neobsahuje dělení K_{5} ani dělení K_{3,3}.

DŮKAZ:

“⇒”

Zřejmá.

“⇐”

Těžká.

Q.E.D.

Eulerův vztah

G souvislý rovinný graf, |V | ≥ 1, s = počet stěn nějakého rovinného nakreslení G. Potom

|V | − |E| + s = 2

(Tudíž počet stěn nezávisí na volbě nakreslení.)

DŮKAZ:

Indukcí podle |E|:

(1) |E| = 0: s = 1, |V | = 1 (kvůli souvislosti), 1 − 0 + 1 = 2.

(2) |E| ≥ 1:

(a) G neobsahuje kružnici: G je strom. Tedy |V | = |E| + 1, s = 1, tedy platí.

(b) G obsahuje kružnici C:

e buď libovolná hrana na C. G−e splňuje Eulerův vztah (indukční předpoklad), má o hranu a stěnu méně, tedy G splňuje Eulerův vztah.

Q.E.D.

Tvrzení:

G buď rovinný, 2-souvislý. Pak hranice libovolné stěny v libovolném nakreslení G odpovídá kružnici v G.

Příklad:

o---o-. / “ o /.o.“ / — o-----o---o

Ale ne:

o-----o------o--“ —“ — — o “

— o-o — — — “

— — — o “ o-----o o------o

DŮKAZ:

Stačí ukázat, že tvrzení:

(i) platí pro trojúhelník (ii) nepřestane platit podrozdělením nebo přidáním hrany Jednoduše z obrázku.

Tvrzení:

G = (V, E) rovinný graf, |V | ≥ 3. Potom:

(i) |E| ≤ 3|V | − 6 (ii) G neobsahuje Δ ⇒ |E| ≤ 2|V | − 4

DŮKAZ:

(i) Přidáváme hrany, dokud nedostaneme nějaký maximální rovinný graf, pro který platí, že po přidání jakékoliv hrany do něj již získáme graf, který není rovinný. Takový graf určitě bude 2-souvislý. Souvislý bude, poněvadž kdyby měl více komponent, určitě bychom mohli přidat

nějakou hranu, kterou komponenty spojíme, a tím by nebyla narušena rovinnost.

2-souvislý bude, jinak můžeme přidat hranu, která podruhé spojí nějaké dvě komponenty.

Každá stěna odpovídá kružnici, dokonce trojúhelníku: (obrázek) — každou kružnici můžeme rozkouskovat na trojúhelníky tak, že stále budeme mít rovinné zobrazení.

Počet incidentních dvojic hrana—stěna = 3s = 2|E|:

3s = 2|E|

3|E| = 3|V | + 3s − 6  (Eulerův vzorec)
|E| = 3|V | − 6

To platí pro každý maximální rovinný graf (rovinná triangulace). (ii)

Pozor!

Tento důkaz nefunguje — proti (a) lze najít triviální protipříklad. Opravy budu konzultovat s doc. Valtrem (asi půjde o moji chybu při přepisování), pokud potřebujete tvrzení umět dokázat teď, zkuste vymyslet důkaz (bez záruky!), jehož idea je:

Využijme (i) — to platí pro maximálně pro triangulovaný graf, odstraňme z něj tedy trojúhelníky. Trojúhelníků je právě tolik co stěn, tedy 2/3|E|. Vyberme z množiny stěn disjunktní dvojice sousedních trojúhelníků a ty spojme — tím, že odstraníme hrany, které je rozdělují. Zbyde nám polovina stěn, žádná z nich nebude trojúhelník (a rozmysleme si, že každý hustší graf už trojúhelník obsahuje). Polovina znamená 1/3|E|, odebrali jsme tedy třetinu stěn. To je dle (i) |V | − 2, tedy pro náš nový graf bez trojúhelníků |E| ≤ 2|V | − 4. Q.E.D.

Připomínám, že toto je pouze idea, a to bez záruky. Také tento důkaz není proveden dvojím počítáním. Hodí se tedy zejména pro nouzové případy, kdy nevíte, kudy kam ;-).

Následuje původní (rozbitý) důkaz:

(a) Výsledný graf není 2-souvislý: pak to musí být hvězda.

Pokud můžeme přidat hranu, byl nesouvislý a spojili jsme dvě komponenty, tím trojúhelník určitě nevytvoříme. Pokud byl souvislý (ale ne 2-souvislý), každá hrana již nutně vytváří trojúhelník (nevytváří!).

Hvězda:

|E| = |V | − 1 ≤ 2|V | − 4

(b) Výsledný graf je 2-souvislý.

Každá stěna je ohraničena kružnicí délky ≥ 4 Počet incidenčních dvojic hrana— stěna = 2|E| ≥ 4s:

2s ≤ |E|
2|E| = 2|V | + 2s − 4
|E| ≤ 2|V | − 4

Důsledky

(1) K_{5} ani K_{3,3} nejsou rovinné.

K_{5} : z(i) = 10 ≰ 3 · 5 − 6

K_{3,3} : z(i) = 9 ≰ 2 · 6 − 4

(2) Každý rovinný graf má alespoň jeden vrchol stupně nejvýše 5. Sporem: Kdyby všechny vrcholy byly stupně alespoň 6 ⇒

2|E| = ∑_{v∈V} degv ≥ 6|V |

(spor s (i)).