— — Barvení map a grafů

Barvení map a grafů

Politická mapa (obrázek). Tři barvy obecně nestačí.

Předpoklady

(1) Každý stát je souvislý.

(2) Státy sousedící pouze v jednotlivých bodech nebudeme považovat za sousední.

Problém čtyř barev

Stačí čtyři barvy na obarvení libovolné politické mapy? Ano, ale důkaz je extrémně těžký.

Definice:

G = (V, E) lze (řádně) obarvit k barvami, pokud existuje zobrazení b: V → {1, 2, …, k} takové, že {x, y} ∈ E ⇒ b(x) ≠ b(y).

Definice:

Barevnost grafu G = χ(G) = min{k : G lze obarvit k barvami }.

Příklady:

(i) χ(C_{2k}) = 2 (ii) χ(C_{2k+1} ) = 3 (iii) χ(K_{n}) = n (iv) χ(K_{m,n}) = 2 (m, n ≥ 1)

(v) χ(T) = 2 (T strom na ≥ 2 vrcholech)

Vztah mezi barvením map a rovinných grafů

(náznak) V každém státě vybereme za vrchol hlavní město, pospojujeme hranami hlavní města soused-

ních států, jistě to lze udělat tak, že graf, který dostaneme, je rovinný. Řekneme, že mapa je k-obarvitelná ⇔ rovinný graf je k-obarvitelný.

Problém čtyř barev II.

Jiná formulace: χ(G) ≤ 4 pro každý rovinný graf G?

VĚTA (o pěti barvách):

χ(G) ≤ 5 pro každý rovinný graf G = (V, E).

DŮKAZ:

Indukcí podle |V |:

(1) |V | ≤ 5: zřejmé.

(2) |G| rovinný, |V | ≥ 6 a předpokládáme, že věta platí pro rovinné grafy s menším počtem vrcholů. G má vrchol x, degx ≤ 5 (Eulerův vztah).

(a) degx ≤ 4: Obarvíme G − x pěti barvami podle indukčního předpokladu, poté dobarvíme x barvou, která se nevyskytuje na jeho sousedech.

(b) degx = 5: Nechť sousedé jsou označeni u_{1}, …, u_{5}. G je rovinný, tudíž neobsahuje podgraf K_{5} — to ale znamená, že nemůžou být všichni sousedé vzájemně pospojováni hranami. Bez újmy na obecnosti nechť např. {u_{4}, u_{5}} ∉ E.

* u2 * u5 “ / x * -- * u3 / “

* u4 * u1

V grafu G − x ztotožníme u_{4} a u_{5} (tím nám nevznikne žádné křížení):

* u2 —˙ ˙ // u * * u3 //

˜˜ — * u1

Podle indukčního předpokladu existuje obarvení b_{0} pěti barvami. Obarvení G − x pak můžeme definovat jako:

b(v) := b_{0}(v) v ≠ u_{4}, u_{5}
b(u_{4}) = b(u_{5}) := b_{0}(u)

Dobavíme vrchol x barvou různou od b(u_{1}), b(u_{2}), b(u_{3}), b(u_{4}) = b(u_{5}).

Q.E.D. Pozor: Důkaz neprobíhá tak, že vezmu rovinný graf a přidám vrchol. Naopak vezmu

libovolný graf, o kterém pouze vím, že libovolný menší graf je rovinný.

Alternativní důkaz:

Indukcí podle |V |:

(1) |V | ≤ 5: zřejmé.

(2) |V | ≥ 6: Nechť v je vrchol nejmenšího stupně. Dle Eulerova formule ⇒ degv ≤ 5. G − v lze obarvit pěti barvami (dle ind. předpokladu).

* a * c “ / v * -- * b / “

* e * d

Vrchol v vyhodíme:

* a * c

* b

* e * d

Bez újmy na obecnosti: a, b, c, d, e mají různou barvu.

f(a) = modrá
f(b) = červená
f(c) = žlutá
f(d) = zelená

Neexistuje žluto–zelená cesta z c do d nebo neexistuje modro–červená cesta z a do b.

Pokud by existovaly, musely by se křížit — buď mimo vrchol (to nesmějí) nebo ve vrcholu (ale jak ho pak obarvit?).

Bez újmy na obecnosti nechť neexistuje cesta c ∼ d. Přebarvíme barvy v žluto–zelené komponentě obsahující d (prohodíme žlutou a ze-

lenou). I toto obarvení je korektní, neboť komponenta je maximální a její sousedé mají všichni jiné barvy.

Teď má ale c a d stejnou barvu, takže v můžeme obarvit barvou nevyskytující se na sousedech.

⟨písnička⟩ Q.E.D.