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

\subchapter{Rovinn� grafy}{

	\shortdef{Oblouk}{Mno�ina bod� $\{\gamma(x): x \in [0,1]\}$,
	p�i�em� $\gamma\colon [0,1] \to \real^2$ (rovina)
	je prost� a spojit� zobrazen�.}

	\definition{
		Graf $G=(V,E)$ je {\bf rovinn�}, m�-li {\bf rovinn� nakreslen�}:

		Vrcholy odpov�daj� r�zn�m bod�m v $\real^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�.
	}

	\examples{
	\list{
		\listItem{$K_4$ je rovinn�}
		\listItem{$C_n$ je rovinn�}
		\listItem{Libovoln� strom}
	}
	}


	\shortdef{Je zn�mo}{
		Ka�d� rovinn� graf m� rovinn� nakreslen�,
		v n�m� hrany odpov�daj� �se�k�m.
		(D�kaz t�k�.)
	}


	\definition{{\bf St�ny rovinn�ho nakreslen�:}
		Maxim�ln� souvisl� oblasti mno�iny $\real^2 \setminus X$,
		kde $X$ je mno�ina bod� le��c�ch na oblouc�ch nakreslen�.
		(Souvislost bereme intuitivn�.)

		\example{
			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).
		}

		\shortdef{Vn�j�� st�na}{
			Jedna neomezen� st�na, kter� existuje pro ka�d� rovinn� graf.
		}
		\shortdef{Vnit�n� st�ny}{
			Ostatn� st�ny.
		}
	}


	\definition{{\bf Topologick� kru�nice:}
		Uzav�en� ``oblouk'' (tj. $\gamma(0) = \gamma(1)$).

		\example{
			Obr�zky. (�neci a m��avky. ;-)
		}
	}


	\theorem{}{Jordanova v�ta o kru�nici}{
		Libovoln� topologick� kru�nice rozd�luje rovinu
		na dv� souvisl� oblasti ({\bf vnit�ek} a {\bf vn�j�ek}
		dan� kru�nice).

		(D�kaz t�k�.)
	}


	\theorem{}{Nerovinnost $K_5$}{
		Graf $K_5$ nen� rovinn�.

		\proof{
			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$.

			\list{
				\alistItem{$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.
				}

				\alistItem{$v_4$ le�� vn� $K$:

					M��eme p�ev�st na isomorfn� graf s $v_4$ uvnit�.
				}
			}

			\qed
		}
	}


	\theorem{}{Nerovinnost $K_{3,3}$}{
		Graf $K_{3,3}$ (�pln� bipartitn� graf o $3+3$ vrcholech) nen� rovinn�.

		\proof{
			$V = \{1,2,3,1',2',3'\}$

			Spousta obr�zk�.

			\asciiart{
        o 1
       / \
     / 3   \
2' o - -o- - o 1'
     \     /
       \ /
        o 2
			}

			Kam s $3'$?

			\qed
		}
	}


	\observation{
		$G$ rovinn� $\Leftrightarrow$ ka�d� d�len� $G$ je rovinn�.

		\proof{
			Obr�zkem $K_4$. Libovoln� rozd�l�me hrany, ale t�m se n�m nijak nezm�n� rovinnost.
		}
	}


	\theorem{}{Kuratowski}{
		$G$ je rovinn� $\Leftrightarrow$ $G$ neobsahuje d�len� $K_5$ ani d�len� $K_{3,3}$.

		\proof{
			\proofrightimpl{Z�ejm�.}
			\proofleftimpl{T�k�.}
		}

		\qed
	}

	\scpart{Euler�v vztah}{
		$G$ souvisl� rovinn� graf, $|V|\ge1$, $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�.)

		\proof{
			Indukc� podle $|E|$:

			\list{
			\nlistItem{$|E| = 0$: $s = 1$, $|V| = 1$ (kv�li souvislosti), $1-0+1=2$.
			}
			\nlistItem{$|E| \ge 1$:

				\list{
				\alistItem{$G$ neobsahuje kru�nici: $G$ je strom.

					Tedy $|V|=|E|+1$, $s = 1$, tedy plat�.
				}
				\alistItem{$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.
				}
				}
			}
			}

			\qed
		}
	}

	\declaration{
		$G$ bu� rovinn�, 2-souvisl�. Pak hranice libovoln� st�ny v libovoln�m
		nakreslen� $G$ odpov�d� kru�nici v $G$.

		\example{
			\asciiart{
   o---o-.
  / \     o
 /.o.\  / |
o-----o---o

Ale ne:


   o-----o------o--\
   |\    |      | o \
   | o-o |      | |  \
   |     |      | o   \
   o-----o      o------o
}
		}

		\proof{
			Sta�� uk�zat, �e tvrzen�:
			\list{
			\listItem{plat� pro troj�heln�k}
			\listItem{nep�estane platit podrozd�len�m nebo p�id�n�m hrany}
			}
			Jednodu�e z obr�zku.
		}
	}

	\declaration{
		$G=(V,E)$ rovinn� graf, $|V| \ge 3$. Potom:
		\list{
		\listItem{$|E| \le 3|V| - 6$}
		\listItem{$G$ neobsahuje $\Delta$ $\Rightarrow$ $|E| \le 2|V| - 4$}
		}

		\proof{
		\list{
		\listItem{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 \eqno\textnote{Euler�v vzorec} $$
			$$ |E| = 3|V| - 6 $$
			To plat� pro ka�d� maxim�ln� rovinn� graf (rovinn� triangulace).
		}
		\listItem{

			\scpart{Pozor!}{
				Tento d�kaz {\bf 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| \le 2|V| - 4$. \sqed

				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:

			\list{
			\alistItem{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 {\bf (nevytv���!)}.

				Hv�zda:
				$$ |E| = |V|-1 \le 2|V|-4 $$
			}
			\alistItem{V�sledn� graf je 2-souvisl�.

				Ka�d� st�na je ohrani�ena kru�nic� d�lky $\ge 4$
				Po�et inciden�n�ch dvojic hrana---st�na $= 2|E| \ge 4s$:
				$$ 2s \le |E| $$
				$$ 2|E| = 2|V| + 2s - 4 $$
				$$ |E| \le 2|V| - 4 $$
			}
			}
		}
		}
		}

		\scpart{D�sledky}{
			\list{
			\nlistItem{$K_5$ ani $K_{3,3}$ nejsou rovinn�.

				$$K_5:\ z(i)=\ 10 \not\le 3\cdot5-6$$
				$$K_{3,3}:\ z(i)=\ 9 \not\le 2\cdot6-4$$
			}
			\nlistItem{Ka�d� rovinn� graf m� alespo� jeden vrchol stupn� nejv��e 5.

				Sporem: Kdyby v�echny vrcholy byly stupn� alespo� 6
				$\Rightarrow$ $$2|E| = \sum_{v \in V} \deg v \ge 6|V|$$ (spor s (i)).
			}
			}
		}
	}
}

\bend
