\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