\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
