\input /home/pasky/school/fastex/lib.tex

\subchapter{Barvení map a grafů}{

	Politická mapa (obrázek).

	Tři barvy obecně nestačí.

	\scpart{Předpoklady}{
	\list{
		\nlistItem{Každý stát je souvislý.}
		\nlistItem{Státy sousedící pouze v jednotlivých bodech nebudeme považovat za sousední.}
	}
	}

	\scpart{Problém čtyř barev}{
		Stačí čtyři barvy na obarvení libovolné politické mapy?

		Ano, ale důkaz je extrémně těžký.
	}

	\definition{
		$G=(V,E)$ lze {\bf (řádně) obarvit} $k$ barvami, pokud
		existuje zobrazení $b\colon V \to \{1,2,\ldots,k\}$
		takové, že $\{x,y\} \in E \Rightarrow b(x) \ne b(y)$.
	}

	\definition{
		{\bf Barevnost grafu $G$ } $= \chi(G) = \min\{k: \textbox{$G$ lze obarvit $k$ barvami}\}$.

		\examples{
		\list{
			\listItem{$\chi(C_{2k}) = 2$}
			\listItem{$\chi(C_{2k+1}) = 3$}
			\listItem{$\chi(K_{n}) = n$}
			\listItem{$\chi(K_{m,n}) = 2$ ($m,n\ge1$)}
			\listItem{$\chi(T) = 2$ ($T$ strom na $\ge2$ vrcholech)}
		}
		}
	}

	\scpart{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 sousedních států, jistě to lze udělat
		tak, že graf, který dostaneme, je rovinný.

		Řekneme, že mapa je $k$-obarvitelná $\Leftrightarrow$
		rovinný graf je $k$-obarvitelný.
	}

	\scpart{Problém čtyř barev II.}{
		Jiná formulace:

		$\chi(G) \le 4$ pro každý rovinný graf $G$?
	}

	\theorem{}{o pěti barvách}{
		$\chi(G)\le5$ pro každý rovinný graf $G=(V,E)$.

		\proof{
			Indukcí podle $|V|$:

			\list{
			\nlistItem{$|V|\le5$: zřejmé.}
			\nlistItem{$|G|$ rovinný, $|V|\ge6$ a předpokládáme,
				že věta platí pro rovinné grafy s menším
				počtem vrcholů.

				$G$ má vrchol $x$, $\deg x \le 5$ (\ref{Eulerův vztah}).
				\list{
				\alistItem{$\deg x \le 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.
				}
				\alistItem{$\deg x = 5$: Nechť sousedé jsou označeni
					$u_1$, \dots, $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\} \notin E$.

\asciiart{
    * 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í):

\asciiart{
    * 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)\qquad v \ne 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)$.
				}
				}

			}
			}

			\qed

			\shortdef{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ý.}
		}

		\scpart{Alternativní důkaz:}{
			Indukcí podle $|V|$:

			\list{
				\nlistItem{$|V| \le 5$: zřejmé.}
				\nlistItem{$|V| \ge 6$:
					Nechť $v$ je vrchol nejmenšího stupně.
					Dle \href{Eulerova formule}{Eulerovy formule}
						$\Rightarrow$ $\deg v \le 5$.

					$G-v$ lze obarvit pěti barvami
					(dle ind. předpokladu).

\asciiart{
    * a     * c
      \   /
      v * -- * b
      /   \
    * e    * d
}

					Vrchol $v$ vyhodíme:

\asciiart{
    * a     * c

             * b

    * e    * d
}

					Bez újmy na obecnosti:
					$a$, $b$, $c$, $d$, $e$ mají různou barvu.
					$$ \eqalign{f(a) &= \textbox{modrá}\cr
					            f(b) &= \textbox{červená}\cr
					            f(c) &= \textbox{žlutá}\cr
					            f(d) &= \textbox{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\pathin{} d$.

					Přebarvíme barvy v žluto--zelené komponentě obsahující $d$
					(prohodíme žlutou a zelenou). 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$\>$

			\qed
		}
	}
}

\bend