\documentclass[10pt,a4paper]{article}

\usepackage[utf8]{inputenc}
\usepackage[czech]{babel}
\usepackage[IL2]{fontenc}
\usepackage[margin=2cm]{geometry}

\usepackage[unicode]{hyperref}

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}

%\newtheoremstyle{plain}{\medskipamount}{\smallskipamount}{\itshape}{}{\bfseries}{.}{0.4em}{}
%\newtheoremstyle{definition}{\medskipamount}{\smallskipamount}{}{}{\bfseries}{.}{0.4em}{}

\newtheorem{veta}{Věta}[section]
\newtheorem{lemma}[veta]{Lemma}
\newtheorem{tvrzeni}[veta]{Tvrzení}
\newtheorem{dusledek}[veta]{Důsledek}
\theoremstyle{definition}
\newtheorem*{definice}{Definice}
\newtheorem*{priklad}{Příklad}
\newtheorem*{fakt}{Fakt}

\setlength{\parindent}{0pt}
\setlength{\parskip}{3pt plus 1pt}

\def\eye{$\ooalign{\raise0.2ex\hbox{$\frown$}\cr$\kern0.25em\bullet$\cr\lower0.2ex\hbox{$\smile$}}$\;}
\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\R{\mathbb{R}}
\def\OVF{\mathop{\rm OVF}}
\def\EVF{\mathop{\rm EVF}}
\def\ex{\mathop{\rm ex}}
\def\faktor#1#2{{^{{#1}}\!/_{{#2}}}}

\usepackage{enumitem}

\setlist{itemsep=0pt,topsep=3pt plus 2pt minus 1pt}
\setlist[itemize]{label=$\bullet$}

\def\rightimpl{\item[\uv{$\Rightarrow$}]}
\def\leftimpl{\item[\uv{$\Leftarrow$}]}
\def\O{\mathcal{O}}

\def\cc{\mathop{\mathrm{cc}}}
\def\odd{\mathop{\mathrm{odd}}}

\begin{document}

\section{Párování v grafech}

\textbf{Značení.} $G = (V, E), |V(G)| = n, |E(G)| = m$

\begin{definice}
\emph{Párování} je množina hran $M$ taková, že každý vrchol je incidentní s
nejvýše jednou hranou v $M$.
\end{definice}

Největší párování je párování největší možné velikosti. Jeho velikost je
nejvýše $n/2$.

\begin{definice}
\emph{Perfektní párování} (1-faktor) je párování, kde každý vrchol je
incidentní s právě jednou hranou.
\end{definice}

Graf nemusí mít perfektní párování. Příkladem jsou grafy s lichým počtem
vrcholů.

\begin{definice}
\emph{Volný vrchol} je vrchol, který nevidí žádnou hranu párování.

\emph{Střídavá cesta} je cesta, kde jsou všechny vnitřní vrcholy incidentní s
párovací hranou a navíc tato hrana je leží na cestě.

\emph{Volná střídavá cesta} je taková střídavá cesta, jejíž koncové vrcholy
jsou volné.
\end{definice}

\begin{lemma}[o volné střídavé cestě]
Párování $M$ je největší iff neexistuje volná střídavá cesta.
\end{lemma}

\begin{proof}\leavevmode
\begin{itemize}
\rightimpl Pokud máme volnou střídavou cestu, umíme párování zvětšit jejím
  invertováním.

\leftimpl Nechť $M$ je párování, které není největší. Tedy existuje párovní
   $M'$, kde $|M'| > |M|$. Definujeme $\tilde M = M' \cup M$.

   Komponenty souvislosti grafu $(V,\tilde M)$ jsou buď izolované body nebo
   cesty nebo kružnice. Komponenta, která má více hran z $M'$, bude cesta liché
   délky s hranami z $M'$ na koncích. V této cestě jsou koncové vrcholy volné
   vzhledem k $M$, našli jsme volnou střídavou cestu.\qedhere
\end{itemize}
\end{proof}

\paragraph{Algoritmus.} Edmondsův kytičkový algoritmus

Algoritmus dostane na vstupu párování $M$ a zlepší jej nebo jej prohlásí za
největší.

Návrh algoritmu:
\begin{itemize}
\item Začneme ve volném vrcholu pro každý z nich.
\item Spustíme BFS, kde v každé druhé vrstvě používáme pouze hrany z $M$.
\end{itemize}

Tímto dostaneme tzv. Edmondsův les.

\begin{definice}
\emph{Kytička} je tvořená stonkem -- střídavá cesta sudé délky z volného
vrcholu do květu, což je lichý cyklus, který je střídavý až na vrchol společný
se stonkem.
\end{definice}

\eye Do květu kytičky vede nejvýše jedna hrana z $M$.

\begin{lemma}[o kontrakci květu]
$G$ obsahuje volnou střídavou cestu iff graf $G'$ získaný z $G$ kontrakcí květu
obsahuje volnou střídavou cestu.
\end{lemma}

Umíme efektivně najít střídavou cestu v původním grafu z toho kontrahovaného.

\begin{itemize}
\item V Edmondsově lese hledáme, zda existují hrany mezi sudými i lichými 
hladinami:
\begin{itemize}
  \item v rámci jednoho stromu $\rightarrow$ máme kytičku $\rightarrow$
    zkontrahujeme a spustíme algoritmus na vzniklém grafu.
  \item mezi dvěma stromy $\rightarrow$ máme volnou střídavou cestu
    $\rightarrow$ zlepšíme párování a restartujeme algoritmus.
\end{itemize}
\item Pokud hrany mezi sudými hladinami neexistují, v grafu neexistuje volná
  střídavá cesta, tudíž párování je největší.
\end{itemize}

\textbf{Složitost:} Procedura, která najde kytičku nebo volnou střídavou cestu nebo
největší párování, trvá $\O(n + m)$.

$\O(n)$ restartujeme pro původní graf se zlepšeným párováním

$\O(n)$ se zarekurzíme po zkontrahování kytičky

Celkem tedy $\O(n^2 (n+m)) = \O(n^2 m)$. Tato rovnost platí, protože můžeme na
začátku odstranit všechny izolované vrcholy.

\subsection{Perfektní párování v obecných grafech}

\begin{veta}[Hallova]\label{veta:hallova}
Bipartitní graf s partitami $A, B$ takovými, že $|A| = |B|$, má perfektní
párování iff $\forall S \subseteq A : |N(S)| \geq |S|$.
\end{veta}

\begin{itemize}
\item $\cc(G) = {}$ množina souvislých komponent grafu $G$
\item $\odd(G) = {}$ množina souvislých komponent liché velikosti

\item Nutná podmínka pro existenci perfektního párování:
  $\forall S \subseteq V(G) : |S| \geq |\odd(G \setminus S)|$
\end{itemize}

\begin{definice}
Řekněme, že $S \subseteq V(G)$ splňuje Tutteho podmínku, pokud platí předchozí
nerovnost.
\end{definice}

Podle nutné podmínky pro existenci perfektního párování vidíme, že jakýkoliv
graf s lichým počtem vrcholů nesplňuje Tutteho podmínku. Stačí zvolit $S =
\emptyset$.

\begin{veta}[Tutte]\label{veta:tutte}
$G$ má perfektní párování iff každá $S \subseteq V(G)$ splňuje Tutteho podmínku.
\end{veta}

\begin{definice}
Třešnička jsou dva vrcholy $x, y$ takové, že $(x,y) \notin E$ a $x, y$ mají
společného souseda.
\end{definice}

\begin{lemma}[O třešničce]\label{lemma:o-tresnicce}
Pokud v souvislém grafu existují dva vrcholy mezi nimiž nevede hrana, pak v
grafu existuje třešnička.
\end{lemma}
\begin{proof}
Nechť $x$ a $y$ jsou dva vrcholy mezi nimiž není v grafu hrana. Uvažujme
nejkratší cestu z $x$ do $y$. Ta jistě obsahuje alespoň tři vrcholy. Vezměme
libovolné tři po sobě jdoucí vrcholy $a,b,c$ na této cestě. Mezi $a$ a $c$
nevede hrana, protože jinak by cesta nebyla nejkratší. Vrcholy $a,c$ tedy
tvoří třešničku.
\end{proof}

\begin{proof}[Důkaz Tutteho věty \ref{veta:tutte}]\leavevmode
\begin{itemize}
\rightimpl zjevné

\leftimpl $G$ nemá perfektní párování, ale po přidání libovolné hrany perfektní
  párování mít bude.

  \eye Pokud $G$ obsahuje množinu $S$ porušující Tutteho podmínku, pak pro
  libovolný graf $G'$, kde $V(G) = V(G'), E(G') \subseteq E(G)$, $S$ také
  podmínku porušuje.

  Pokud $G = K_n$, potom pro $n$ sudé nelze, protože $K_n$ má p.p.
  Předpokládejme tudíž, že $G$ obsahuje nehranu. Volíme $S$ jako množinu
  vrcholů, které jsou spojeny se všemi ostatními, tedy
  $S = \{ v \mid \deg v = |V(G)| - 1\}$. Víme, že $S \neq V(G)$.

  Nechť komponenty $G \setminus S$ jsou úplné grafy. Pokud $S$ splňuje
  Tuttovou podmínku, $G$ obsahuje p.p. Z předpokladu neexistence p.p proto
  $S$ podmínku nesplňuje.

  Nyní nechť $G \setminus S$ má komponentu, která není úplným grafem. Pak podle
  lemmatu o třešničce má třešničku. Označme si ji $a$ -- $c$ -- $b$. Nutně tedy
  existuje $d$ nesousedící s $c$. Z našich předpokladů o $G$:

\begin{itemize}
  \item v $G + (a,b)$ existuje p.p. $M_1 \ni (a,b)$.
  \item v $G + (c,d)$ existuje p.p. $M_2 \ni (c,d)$.
\end{itemize}

  Uvažujme graf $H = (V(G), M_1 \Delta M_2)$. Tento graf má pouze vrcholy stupně
  0 a 2, je to disjunktní sjednocení kružnic. Dále $a, b, c, d$ mají stupně 2.

\begin{itemize}
  \item$(a,b)$ a $(c,d)$ leží na jiné kružnici. Vezmeme kružnici $C$ obsahující
    $(c,d)$. Když na $C$ prohodíme párovací hrany, je p.p. v $G$.
  \item$(a,b)$ a $(c,d)$ leží na stejné kružnici. Pak nastane jedna z možností.
  \begin{itemize}
    \item cesty mezi hranami $(a,b)$ a $(c,d)$ mají lichou délku. Pak můžeme
      opět prohodit párovací hrany jako v předchozím bodu.
    \item cesty mezi hranami $(a,b)$ a $(c,d)$ mají sudou délku. Pak v grafu
      $H$ tedy nejsou hrany $(a,c)$ ani $(b,c)$. Nechť $P$ je cesta po $C$ z
      $b$ do $c$ jdoucí přes vrchol $a$. Pak $M_1 \setminus E(P) \cup ( M_2
      \cap E(P)) \cup \{(b,c)\}$ je hledané perfektní párování. \qedhere
\end{itemize}
\end{itemize}
\end{itemize}
\end{proof}

\begin{dusledek}[Petersen]
Každý 3-regulární graf bez mostu má perfektní párování.
\end{dusledek}

\begin{proof}
Vezměme si libovolnou $S \subseteq V(G)$. Ukážeme, že splňuje Tutteho podmínku.

Pokud $|\odd(G \setminus S)| = 0$, jsme hotovi. Předpokládejme, tedy že v
$G\setminus S$ existuje lichá komponenta $K$. Potom $\sum_{v \in V(K)} \deg_G v
= 3 |V(K)| = 2|E(K)| + {}$počet hran vycházející mimo $K$, což je liché číslo.

Počet hran mezi $K$ a $S$ musí být alespoň 2, jinak máme most, je to tedy
alespoň 3. Maximální počet hran ze $S$ je $3|S|$, tudíž lichých komponent může
být nejvýše $\frac{3|S|}{3}$, tedy $|S|$.
\end{proof}

\begin{definice}
$G$ je kritický na párování, pokud $\forall v \in V(G)$ platí, že $G \setminus
v$ má perfektní párování.
\end{definice}

\begin{veta}[Gallai-Edmonds]\label{veta:gallai-edmonds}
Každý graf obsahuje množinu vrcholů $S$ splňující:

\begin{enumerate}
\item $S$ je párovatelná s $\cc(G \setminus S)$, tedy existuje párování mezi
  vrcholy $S$ a komponentami $G \setminus S$ takové, že žádné dvě hrany nekončí
  ve stejné komponentě a všechny vrcholy $S$ jsou spárováné.
\item Každá komponenta $G \setminus S$ je kritická na párování.
\end{enumerate}

$G$ má perfektní párování iff $|S| = |\cc(G \setminus S)|$.
\end{veta}

\begin{proof}
Poslední tvrzení plyne z Tutteho věty \ref{veta:tutte}. Podmínky 1. a 2. budeme
dokazovat indukcí podle počtu vrcholů.

Pokud $|V(G)| = 0$, můžeme mít $S$ prázdné. Proto předpokládejme $|V(G)| > 0$.

Deficit množiny $S \subseteq V(G)$ definujme jako $d(S) = |\odd(G \setminus S)|
- |S|$. Vidíme, že $d(\emptyset) \geq 0$.

Vezmeme $S$ s největším deficitem a mezi nimi vybereme největší co do počtu
vrcholů. Pak $d(S) \geq 0$. Sporem dokážeme, že $(G \setminus S)$ nemá
komponenty sudé velikosti.

Nechť $K$ je taková komponenta. Vezmeme $v \in K$ a zkoumáme, jestli $S \cup
\{v\}$ není lepší, než $S$. $d(S \cup \{v\}) \geq |\odd(G \setminus S)| + 1 -
(|S| + 1) = d(S)$. Máme spor.

Nyní ukážeme kritičnost. Nechť pro spor komponenta $K$ grafu $G-S$ není
kritická na párování, tedy $\exists x \in V(K)$ takové, že $K \setminus x$ nemá
perfektní párování. Tudíž nesplňuje Tutteho podmínku a existuje $S' \subseteq
V(K\setminus x)$, že $|\odd(K \setminus x \setminus S')| > |S'|$.

Jelikož $K \setminus x$ má sudý počet vrcholů, parita $|\odd(K \setminus x
\setminus S')|$ i $|S'|$ je stejná. Proto $|\odd(K \setminus x \setminus
S')|\ge|S'|+2$. Zvolme $T = S \cup \{x\} \cup S'$. Potom $d(T) = |\odd(G
\setminus T)| - |T| = d(S) + |\odd(K \setminus x \setminus S')| - |S'| - 2 \geq
d(S)$. 

Protože jsou všechny liché komponenty kritické na párování, můžeme je nahradit
kontrakcí za jejich kritický vrchol. Tím dostáváme bipartitiní graf $H$, kde
jedna partita je $S$ a druhá je tvořena těmito kontrakcemi.

Pro spor předpokládejme, že $S$ nejde v $H$ spárovat. Podle Hallovy věty
existuje $A \subseteq S$, kde vrcholy z $A$ sousedí s méně, než $|A|$ vrcholy
$H - S$. Potom v původním grafu $d(S \setminus A) = |\odd(G \setminus (S
\setminus A))| - |S| + |A| \geq d(S) - |N(A)| + |A| > d(S)$.
\end{proof}

\section{Kontrakce a minory}

\begin{definice}
Graf $G$ je $k$-souvislý, pokud má aspoň $k+1$ vrcholů a po odebrání
libovolných $k-1$ vrcholů bude souvislý.
\end{definice}

Každý $k$-souvislý graf má u všech vrcholů stupeň alespoň $k$.

\begin{lemma}[O kontrahovatelné hraně]\label{lemma:contract}
Každý $3$-souvislý graf $G \not\cong K_4$ obsahuje hranu $e$ takovou, že $G.e$
je $3$-souvislý.
\end{lemma}

\eye Pokud $G.e$ není 3-souvislý (a $G$ byl), tak existuje 3-řez obsahující oba
koncové vrcholy hrany $e$.

\eye Je-li $S$ minimální řez, každý vrchol z $S$ má hranu do všech komponent $G
\setminus S$.

\begin{proof}[Důkaz lemmatu \ref{lemma:contract}]
Předpokládejme, že žádná hrana nejde zkontrahovat. Tudíž pro každou hranu
existuje nějaký 3-řez obsahující oba její koncové vrcholy. Vezmeme hranu
$(x,y)$ a vrchol $z$ takové, že $\{x,y,z\}$ je 3-řez a nejmenší komponenta $K$
grafu $G \setminus \{x,y,z\}$ je minimální.

Víme, že $z$ má souseda $w$ v $K$. Ukážeme, že lze zkontrahovat $(w,z)$. Pokud
nejde, existuje vrchol $u$ takový, že $\{u,w,z\}$ je 3-řez. Navíc $w$ má
souseda v každé komponentě $G \setminus \{u,w,z\}$. Tudíž znova existuje
komponenta $K'$, která neobsahuje $x, y$.

Tedy platí, že v $K'$ nejsou vrcholy $x,y,z,u,w$, ale obsahuje souseda $w$.
Proto je $K'$ podmnožinou $K \setminus w$. Tudíž $|K'| < |K|$ a máme spor.
\end{proof}

Umíme tedy jakýkoliv 3-souvislý graf kontrakcemi převést na $K_4$. Nyní
ukážeme, že to jde i naopak.

\begin{veta}[Tutteova charakterizace 3-souvislých grafů]
Graf $G$ je 3-souvislý iff existuje posposloupnost grafů $G_0, \dots G_n$
takových, že:
\begin{itemize}
\item $G_0 \cong K_4, G_n \cong G$
\item $\forall 1 \leq i \leq n: G_{i-1}$ vznikne z $G_i$ kontrakcí hrany
\item $\forall 0 \leq i \leq n: G_i$ má minimální stupeň alespoň $3$
\end{itemize}
\end{veta}

\begin{proof}\leavevmode
\begin{itemize}
\rightimpl plyne z lemmatu \ref{lemma:contract}.

\leftimpl Mějme $G_0, \dots, G_n$. Ukážeme indukcí, že $\forall i: G_i$ je
   3-souvislý.

   Víme, že $G_{i-1}$ je 3-souvislý a $G_i$ má minimální stupeň alespoň 3.
   Předpokládejme, že $G_i$ má 2-řez. Každá komponenta 2-řezu má alespoň 2
   vrcholy, protože minimální stupeň je $\geq 3$. Tudíž libovolný 2-řez $G_i$ by
   musel existovat i v $G_{i-1}$, což je spor.\qedhere
\end{itemize}
\end{proof}

\begin{definice}
Mějme $G,H$ grafy. Řekneme, že $H$ je minor $G$ (nebo $G$ obsahuje $H$ jako
minor), pokud lze $H$ získat z $G$ mazáním hran, vrcholů a kontrakcí hran.
Píšeme $H \preceq_m G$.
\end{definice}

\eye Relace $\preceq_m$ je tranzitivní a reflexivní. Pokud je $H$ podgrafem
$G$, je i jeho minorem. Pokud je $G$ rovinný, je rovinný i jeho minor.

\begin{veta}\label{veta:minor-jako-podgrafy}
Nechť $H$ je graf s vrcholy $v_1, \dots, v_k$. $H$ je minor $G$ iff $G$
obsahuje $k$ souvislých neprázdných disjunktních podgrafů $P_1,\dots,P_k$
takových, že pokud $(v_i,v_j)$ je hrana $H$, tak v $G$ existuje hrana mezi
vrcholem z $P_i$ a $P_j$.
\end{veta}

\begin{proof}\leavevmode
\begin{itemize}
\leftimpl Všechny vrcholy v jednotlivých podgrafech zkontrahujeme (to můžeme
   udělat díky souvislosti podgrafů), ostatní vrcholy mimo $P$ a nepotřebné
   hrany odstraníme, tím dostaneme $H$. Všechny tyto operace zachovají minoritu.

\rightimpl Máme minor $H$, a tím i posloupnost odstraňování a kontrakcí $G_i$,
   kde $G_1 = H$ a $G_n = G$. Ukážeme indukcí, že každý $G_i$ splňuje podmínku.

   Pro $H$ vezmeme $P_i = v_i$. Pokud $G_{j-1}$ vznikl odstraněním, přidanou
   věc v $G_j$ budeme ignorovat. Pokud $G_{j-1}$ vznikl kontrakcí $(u,v)$ a
   vzniklý vrchol $w \in P_i$, v $G_j$ jsou vrcholy $u,v$ v $P_i$.\qedhere
\end{itemize}
\end{proof}

\begin{veta}[Kuratowski, Wagner]\label{veta:kuratowski-wagner}
Následující tvrzení jsou ekvivalentní:
\begin{itemize}
\item $G$ je rovinný
\item $G$ neobsahuje dělení $K_{3,3}$ ani $K_5$
\item $G$ neobsahuje $K_{3,3}$ ani $K_5$ jako minor
\end{itemize}
\end{veta}

\begin{proof}\leavevmode
\begin{itemize}
\item[\uv{$1 \Rightarrow 3$}] Plyne z toho, že $K_5$ ani $K_{3,3}$ nejsou
rovinné.

\item[\uv{$3 \Rightarrow 2$}] Pokud má $G$ dělení $H$ jako podgraf, má jej i
jako minor.

\item[\uv{$2 \Rightarrow 3$}] Předpokládejme, že $G$ obsahuje $K_{3,3}$ jako
minor. Potom podle věty \ref{veta:minor-jako-podgrafy} obsahuje $G$ souvislé
neprázdné disjunktní $P_1,\dots,P_6$, kde BÚNO vedou hrany mezi každou dvojicí
$P_i,P_j$, kde $i=\{1,2,3\},j=\{4,5,6\}$.

Tudíž z každé komponenty vedou tři hrany do tří \uv{opačných} komponent $P_j$,
označme je $q_{i,j}$. Nechť $q_{j,i}=q_{i,j}$ (pokud existují dvě takové hrany,
zvolíme z obou komponent stejnou). Potom rovněž existuje v každé komponentě
$P_i$ vrchol $p_i$, pro který platí, že existují tři disjunktní cesty $Q_{i,j}$
mezi vrcholem $p_i$ a hranou $q_{i,j}$.

Toto nám již dokazuje existenci dělení $K_{3,3}$, kde jeho vrcholy jsou $p_i$ a
hrany jsou sjednocení cest $Q_{i,j},q_{i,j},Q_{j,i}$.

Pro $K_5$ postupujeme podobně, abychom získali dělení $K_5$, ale kdyby v jedné
komponentě neexistoval vrchol obsahující čtyři disjunktní cesty, tak jeho
komponentu rozdělíme na dvě tak, že z každé nové komponenty povedou dvě původní
hrany ven.  A tak získáme komponenty, které podle věty
\ref{veta:minor-jako-podgrafy} odpovídají minoru $K_{3,3}$.

\item[\uv{$3 \Rightarrow 1$}] Indukcí podle počtu vrcholů.

Pokud $n \leq 4$, tvrzení triviálně platí. Tedy předpokládejme, že $n \ge 5$.

Pro každý rovinný graf $G$ a jeho vrchol $v$ existuje rovinné zakreslení $G$ s
$v$ na vnější stěně.

Pokud je graf nesouvislý, můžeme použít indukční předpoklad na jeho komponenty.

Pokud má $G$ artikulaci $v$, můžeme jej podle artikulace rozdělit na dvě
komponenty, ty jsou podle IP rovinné. Tudíž můžeme $G$ zakreslit rovinně, kde
$v$ je na vnější stěně.

Pokud má $G$ 2-řez, můžeme jej rozdělit na dvě části podle 2-řezu z vrcholů
$x,y$. Ty jsou podle IP rovinné. Nyní v každé komponentě dodáme hranu $(x,y)$,
pokud neexistuje. Tím potom budeme moct tuto hranu zakreslit na vnější stěnu,
grafy spojit rovinně a případně odebrat $(x,y)$.

Navíc, přidání hrany $(x,y)$ nám neporuší IP, jelikož kdyby jejím přidáním
vznika v jednom podgrafu $K_5$ nebo $K_{3,3}$, už bychom našli tento minor
nahrazením $(x,y)$ za zkontrahovanou cestu v druhém podgrafu.

Pokud je graf $3$-souvislý, lze zkontrahovat hranu $e$ tak, že $G.e$ je
3-souvislý a neobsahuje z tranzitivity $K_{3,3}$ ani $K_5$ jako minory. Tedy z
IP $G.e$ je rovinný.

Vezměme $(G.e) \setminus \{v_e\}$, tedy zkontrahovaný graf bez vrcholu
vzniklého kontrakcí. Každá stěna 2-souvislého grafu je kružnice. Tudíž stěna,
uvnitř které ležel $v_e$, je ohraničená kružnicí $C$. Dostáváme 3 případy podle
sousedství konců $e = (x,y)$:

\begin{enumerate}
\item $|N(x) \cap N(y)| \geq 3$. Potom existuje $K_5$ jako minor.
\item $\exists a_1, a_2 \in N(x) \cap C, \exists b_1, b_2 \in N(y) \cap C$ v
  pořadí $a_1,b_1,a_2,b_2$ na $C$. Potom existuje $K_{3,3}$ jako minor.
\item Jinak všichni sousedi $y$ na $C$ leží na stejné cestě mezi dvěma sousedy
  $x$. Dostáváme rovinné zakreslení $G$. \qedhere
\end{enumerate}
\end{itemize}
\end{proof}

\section{Nakreslitelnost na plochu}

\eye Každá uzavřená křivka má okolí homeomorfní otevřenému válci nebo Möbiova
listu.

\begin{definice}
Plocha $\Gamma$ je orientovatelná, pokud je okolí každé uzavřené křivky
homeomorfní válci, jinak je neorientovatelná.
\end{definice}

Plochy vytváříme ze sféry přidáváním uch a křížítek (cross-cup).

\begin{fakt}
Každá plocha je homeomorfní $\Sigma_n$ nebo $\Pi_n$ pro nějaké $n$.

$\Sigma_n$ je \uv{orientovatelná plocha rodu $n$} vzniklá ze sféry přidáváním
$n$ uch, zatímco $\Pi_n$ je \uv{neorientovatelná} a vznikla ze sféry přidáním
$n$ křížítek.
\end{fakt}

\begin{definice}
Eulerova charakteristika plochy $\chi(\Sigma_n) = 2-2n$, $\chi(\Pi_n) = 2-n$
\end{definice}

\begin{itemize}
\item $\Sigma_0$ \dots sféra
\item $\Pi_1$ \dots projektivní rovina
\item $\Sigma_1$ \dots torus
\item $\Pi_2$ \dots Kleinova láhev
\end{itemize}

\begin{definice}
Nakreslení grafu $G$ na plochu $\Gamma$ je zobrazení $\varphi$, které zobrazuje
$x \in V(G)$ na bod $\varphi(x) \in \Gamma$ a hranu $e=(x,y) \in E(G)$ na
prostou křivku na $\Gamma$ spojující $\varphi(x)$ a $\varphi(y)$.

Navíc pokud $e \neq f$, $\varphi(e) \cap \varphi(f) = \{\varphi(x) | x \in e
\cap f\}$. Pokud $x \notin e$, $\varphi(x) \notin \varphi(e)$.
\end{definice}

\begin{definice}
Stěna nakreslení je souvislá komponenta $\Gamma \setminus \varphi(G)$.
\end{definice}

\begin{definice}
Nakreslení je buňkové, pokud je každá stěna homeomorfní disku.
\end{definice}

\begin{fakt}
Nakreslení neprázdného rovinného $G$ na $\Sigma_0$ je buňkové právě, když $G$
je souvislý.
\end{fakt}

\begin{veta}[Zobecněná Eulerova formule]
Nechť máme nakreslení $G$ na $\Gamma$, které má $s$ stěn. Pak $|V(G)| - |E(G)|
+ s \geq \chi(\Gamma)$. Pokud je nakreslení buňkové, platí rovnost.
\end{veta}

\begin{proof}[Důkaz buňkové varianty]
Indukcí dle $n$ pro $\Sigma_n$. Pro $\Sigma_0$ platí podle Eulerovy formule.

Nyní pro $n \geq 1$ mějme nějaké ucho. To rozstřihneme a zalepíme konce disky.
Tím jsme mohli rozdělit hrany tímto uchem procházející, přidáme tedy koncové
vrcholy a nakreslíme kružnice mezi nimi na každé straně.

Původní graf má $v$ vrcholů, $e$ hran a $s$ stěn. Rozstřižený graf má parametry
$v+2k, e+3k, s+k+2$. Z IP máme, že $v+2k-e-3k+s+k+2=\chi(\Sigma_{n-1}) + 2$.
Tudíž $v-e+s=\chi(\Sigma_n)$.

Nyní induckí dle $n$ pro $\Pi_n$. Pro $\Pi_0$ platí.

Mějme křížítko, přes něj vedou nějaké hrany. Ty hrany rozpůlíme, přidáme k nim
koncové vrcholy a ty spojíme kružnicí. Tím se křížítka zbavíme.

Tento nový graf má parametry $v+k, e+2k, s+k+1$. Tedy podle IP
$v+2k-e-3k+s+k+1=\chi(\Pi_{n-1})+1$. Tudíž $v+e-s=\chi(\Pi_n)$. 
\end{proof}

\begin{dusledek}
$G$ nakreslitelný na $\Gamma$ s alespoň 3 vrcholy splňuje $|E(G)| \leq 3|V(G)|
- 3\chi(\Gamma)$. Tudíž $G$ má průměrný stupeň

$$ \frac{2|E(G)|}{|V|} \leq 6 - 6\frac{\chi(\Gamma)}{|V|} $$
\end{dusledek}

\begin{proof}
BÚNO $G$ je triangulace, každá stěna je disk. Délka hranice stěny nechť je 3.
Potom $2|E(G)|$ je součet délek stěn, a to je $3s$.

Ze zobecněné Eulerovy formule máme $3|E(G)| = 3(|V(G)| + s - \chi(\Gamma))$. Z
toho už dosazením za $3s$ dostaneme správný vzorec.

Druhá nerovnost plyne vydělením počtu vrcholů a vynásobením dvěma.
\end{proof}

\section{Barvení grafu}

\begin{definice}
$\chi(G)$ je minimální počet barev, kterými lze dobře obarvit $G$.

$\delta(G)$ je minimální stupeň, $\Delta(G)$ je maximální stupeň vrholů $G$.
\end{definice}

\begin{definice}
$G$ je $d$-degenerovaný, pokud vrcholy lze seřadit tak, že vlevo od každého
vrcholu je nejvýše $d$ jeho sousedů.
\end{definice}

\eye 1 Každý graf je $\Delta(G)$-degenerovaný.

\eye 2 Pro každý $d$-generovaný graf platí $\chi(G) \leq d+1$.

\begin{tvrzeni}
Nechť $\Gamma \not\cong \Sigma_0$ a $G$ je nakreslitelný na $\Gamma$. Pak $G$
obsahuje alespoň jeden vrchol stupně $\leq \frac{5+\sqrt{49-24\chi(\Gamma)}}{2}
= d_\Gamma$. Tedy $G$ je $d_\Gamma$-degenerovaný.
\end{tvrzeni}

\begin{proof}\leavevmode
\begin{itemize}
\item $\chi(\Gamma) = 1$. Z tvrzení dostáváme existenci vrcholu stupně $\leq 5$.
  Průměrný stupeň $\leq 6 - \frac{6\chi(\Gamma)}{|V|} < 6$. Tudíž máme vrchol
  stupně 5.
\item $\chi(\Gamma) = 0$. Z tvrzení máme stupeň 6 a průměrný stupeň je roven
  $6$. Není tudíž možné, aby všechny vrcholy měly vyšší stupeň. Tvrzení platí.
\item $\chi(\Gamma) < 0$. Potom $\delta < 6 - \frac{\chi(\Gamma)}{|V|}$. Taky
  můžeme odhadnout počet vrcholů díky $\delta \leq |V| + 1$. Dostáváme $\delta
  \leq 6 - \frac{6\chi(\Gamma)}{\delta + 1} \to \delta^2 + \delta \leq 6(\delta
  + 1) - 6\chi(\Gamma)$. Řešíme kvadratickou nerovnici, po úpravách dostaneme
  výsledek tvrzení. \qedhere
\end{itemize}
\end{proof}

\begin{dusledek}[Heawoodova formule]
Pro $\Gamma \not\cong \Sigma_0$ platí, že každý graf nakreslitelný na $\Gamma$
má barevnost nejvýše $d_\Gamma+1$.
\end{dusledek}

\eye 3 $\forall G : \chi(G) \leq \Delta(G)+1$.

Rovnost nastává pro $K_n$ a lichý cyklus. Jsou to jediné takové souvislé grafy.

\begin{lemma}\label{lemma:plochy-1}
Nechť $G$ je souvislý a obsahuje alespoň jeden vrchol stupně $< \Delta(G)$. Pak
$\chi(G) \leq \Delta(G)$.
\end{lemma}

\begin{proof}
Nechť $x$ je vrchol stupně $< \Delta(G)$. Zvolme kostru $T$ grafu $G$, kterou
zakořeníme v $x$. Barvíme hladově od listů (máme uspořádání). Pro vrchol $v
\neq x$, když jej barvíme, předchůdce $v$ není obarven, tudíž obarveno nejvýše
$\Delta(G)-1$ sousedů $v$, takže lze použít jednu z $\Delta(G)$ barev. Vrchol
$x$ nakonec lze obarvit jednou $\Delta(G)$ barev, protože má stupeň $\leq
\Delta(G)-1$.
\end{proof}

\begin{veta}[Brooks]\label{veta:brooks}
Nechť $G$ je souvislý graf, který není úplný ani lichá kružnice. Pak $\chi(G)
\leq \Delta(G)$.
\end{veta}

\begin{proof}
Budeme předpokládat, že $\Delta \geq 3$ (Pro $\Delta = 2$ je $G$ sudý cyklus
nebo cesta, $\chi(G) = 2$). Můžeme předpokládat, že ostatní vrcholy mají stupeň
$\Delta(G)$, jinak můžeme použít lemma \ref{lemma:plochy-1}.

Předpokládejme, že $G$ je $3$-souvislý.  Potom lemmatu o třešničce
(\ref{lemma:o-tresnicce}) existují $x -- z -- y$ tak, že tvoří třešničku.
Seřadíme vrcholy grafu $v_1,\dots,v_n$ tak, že $v_1 = x, v_2 = y, v_n = z$.
Každý vrchol kromě $z$ má souseda vpravo od sebe. Všimněme si, že zde využíváme
$3$-souvislost grafu. Kdyby $x,y$ byl řez, tak bychom toto nemohli udělat.

Sestavíme kostru, zakořeníme se v $z$ a barvíme zleva hladově. Víme, že $x,y$
mají stejnou barvu, každý vrchol má v okamžiku barvení zakázáno nejvýše
$\Delta-1$ barev.

Pokud má $G$ artikulaci $x$, potom umíme $G$ rozdělit tak, že $G_1 \cap G_2 =
x, G_1 \cup G_2 = G$. Pokud máme obarvení $G_1$ a $G_2$ nejvýše $\Delta$
barvami, lze barvy zpermutovat tak, aby barva $x$ byla v obou barveních stejná.

Obarvení $G_1$ a $G_2$ existují dle lemmatu \ref{lemma:plochy-1}, protože $x$
má v $G_1$ i v $G_2$ stupeň menší, než $\Delta(G)$.

Pokud má $G$ 2-řez $x,y$, zkusíme jako v předchozím případě obarvit $G_1$ a
$G_2$. Pokud mají $x,y$ v obou obarveních stejnou nebo různé barvy, vyhráli
jsme. Může se ale stát, že jedno obarvení obarvilo $x,y$ stejně, ale druhé
různě.

Pokud $x$ nebo $y$ mají v $G_1$ i $G_2$ stupeň $\geq 2$, můžeme barvit
$G_1+(x,y)$ a $G_2+(x,y)$. Jinak BÚNO $\deg_{G_1} x,y = \Delta - 1, \deg_{G_2}
x,y = 1$. Dle lemmatu \ref{lemma:plochy-1} obarvíme $G_1$.
\begin{itemize}
\item $x,y$ dostaly různé barvy. Pak obarvíme $G_2 + (x,y)$. Po permutaci můžeme
  slepit.
\item $x,y$ dostaly stejnou barvu. Pak obarvíme $G_2$ s vrcholy $x,y$ slepenými
  do jednoho vrcholu, po obarvení a permutaci můžeme slepit.\qedhere
\end{itemize}
\end{proof}

\subsection{Hranové barvení grafu}

\begin{definice}
Hranové barvení grafu je funkce $b: E(G) \to B$ taková, že pokud $e \neq f$ a 
$e,f$ mají společný vrchol, potom $b(e) \neq b(f)$.
\end{definice}

\begin{definice}
Hranová barevnost $\chi_e(G)$ je nejmenší velikost $B$, pro kterou existuje
obarvení $G$.
\end{definice}

\eye $\chi_e(G) \geq \Delta(G)$.

\begin{definice}
Line-graf $L(G)$ grafu $G = (V,E)$ je $(E, F)$ taková, že $\{e,f\} \in F$,
pokud hrany $e,f$ mají společný vrchol.
\end{definice}

\eye $\chi_e(G) = \chi(L(G)) \leq \Delta(L(G))+1 \leq 2\Delta(G)-1$, protože
$\deg_{L(G)}(uv) \leq \deg u-1 + \deg v-1$.

\begin{veta}[Vizing (1964)]
Pro každý jednoduchý graf $G$ platí $\Delta(G) \leq \chi_e(G) \leq \Delta(G)+1$.
\end{veta}

Je NP-úplné rozhodnout, jestli $\Delta(G)$ nebo $\Delta(G)+1$.

\begin{proof}
To, že $\Delta(G) \leq \chi_e(G)$, už víme.

Nyní ukážeme, že $G$ lze obarvit barvami z množiny $B = [\Delta + 1]$. Nechť
$H$ je maximální podgraf $G$ hranově obarvitelný hranami z $B$. Pokud $H = G$,
jsme hotovi.

Jinak $\exists (x,y_0) \in E(G) - E(H)$. Barva $\alpha$ je volná v vrcholu $x$,
pokud žádná hrana incidentní s $x$ nemá barvu $\alpha$.

\eye Každý vrchol má volnou barvu.

Podívejme se na vrchol $x$. Z něj vede neobarvená hrana do $y_0$. Hledejme
nejdelší posloupnost $y_1,\dots,y_k$ sousedů $x$, že $\alpha_j=b(xy_j)$ je
volná u $y_{j-1}$. Nechť $\alpha$ je barva volná u $y_k$.

\begin{itemize}
\item $\alpha$ je volná u $x$, potom přebarvíme $(x,y_k)$ na $\alpha$ a
  $(x,y_{j-1})$ na $\alpha_j$ pro každé $j \in [k]$.
\item $\alpha$ je použita pro hranu $(x,y')$, kde $y' \neq y_j \forall j \in
  [k]$. Toto je ale spor s maximalitou posloupnosti, protože lze $y'$ do
  posloupnosti přidat.
\item $\alpha$ použitá pro hranu $(x,y_j)$, kde $j \in [1,\dots,k-1]$. Označme
  $\beta$ volnou barvu u $x$, definujeme graf $H_{\alpha\beta}$ jako podgraf $H$
  tvořený jenom hranami barev $\alpha, \beta$. $\Delta(H_{\alpha\beta}) \leq 2$,
  tedy komponenty souvislosti jsou cesty nebo kružnice.

  Nechť $P$ je komponenta $H_{\alpha\beta}$ obsahující $(x,y_j)$. $P$ je nutně
  cesta, kde $x$ je koncový vrchol. Druhý konec označme $z$. Nechť $b'$ je
  obarvení $H$ vzniklé prohozením barev $\alpha$ a $\beta$ na $P$.

  Všechny vrcholy až na $x$ a $z$ mají stejnou volnou barvu v $b'$.
\begin{itemize}
  \item $z = y_{j-1}$, potom $z$ měl původně volnou barvu $\alpha$. Po
    prohození má $x$ volnou barvu $\alpha$ a $z$ barvu $\beta$. Posloupnost
    $y_0,\dots,y_k$ nebyla porušena, ale máme $\alpha$ volnou u $x$.
  \item $z \neq y_{j-1}$, potom prohození barev neovlivnilo $y_{j-1}$, které má
    volnou barvu $\alpha$, posloupnost se zkrátí na $y_1,\dots,y_{j-1}$.
\end{itemize}
\end{itemize}

Jak vidíme, vždy najdeme pro barvu $(x,y_0)$ jednu z $B$ barev, spor s
neobarvitelností.
\end{proof}

Tím víme vše potřebné o hranové barevnosti grafů. Vraťme se k barevnosti
vrcholové.

\section{Perfektní grafy}

$\alpha(G)$ je velikost největší nezávislé množiny, $\omega(G)$ je velikost
největší kliky.

$H \leq G$ znamená, že $H$ je indukovaný podgraf $G$.

\eye $\omega(G) \leq \chi(G)$. Ostrou nerovnost splňuje lichý cyklus.

\begin{definice}
$G$ je perfektní, pokud $\forall H \leq G: \chi(H) = \omega(H)$.
\end{definice}

\eye Pokud je $G$ je perfektní, každý jeho indukovaný podgraf je rovněž
perfektní. Obyčejný podgraf toto splňovat nemusí, protože to může být lichý
cyklus délky alespoň 5.

Příklady perfektních grafů:
\begin{itemize}
\item $K_n$
\item bipartitní grafy
\end{itemize}

\begin{definice}
Nezávislá množina $I$ v grafu $G$ je rozlehlá, pokud každá klika v $G$
velikosti $\omega(G)$ obsahuje vrchol z $I$ (průnik kliky a nezávislé množiny
je nejvýše jeden vrchol).
\end{definice}

\begin{lemma}\label{lemma:perfektni-1}
Graf $G$ je perfektní právě, když každý jeho indukovaný podgraf obsahuje
rozlehlou nezávislou množinu.
\end{lemma}

\begin{proof}\leavevmode
\begin{itemize}
\rightimpl Mějme $H \leq G$. Potom podle perfektností $G$ platí $\chi(H) =
  \omega(H)$.  Z každé kliky velikosti $\omega(H)$ zvolme vrcholy stejné barvy.
  Ty tvoří nezávislou množinu, která je navíc rozlehlá.

\leftimpl Víme, že pro každý indukovaný podgraf $H$ máme rozlehlou množinu $I$.
   Každý vrchol z $I$ obarvíme barvou $\omega(H)$. Potom vezmeme graf $H-I$,
   který má podle předpokladu rozlehlou množinu $I'$ a zároveň $\omega(H-I)$ o
   1 menší.
   
   Tudíž můžeme postupovat stejným způsobem až po prázdný graf a nikdy
   nevyužijeme stejnou barvu vícekrát. Máme tedy pro každé $H$ obarvení
   velikosti $\omega(H)$.\qedhere
\end{itemize}
\end{proof}

Navíc, pokud zvolíme $x \in G$ perfektním grafu, existuje rozlehlá nezávislá
množina obsahující $x$ a to tak, že podle předchozího důkazu zvolíme přesně
barvu $x$. Pokud $x$ je v klice velikosti $\omega(H)$, pak $x$ \uv{zafixuje}
barvu, kterou volíme vrcholy z každé kliky velikosti $\omega(H)$. Jinak jde o
vrchol mimo kliku velikosti $\omega(H)$ a existuje nesousední vrchol v této
klice se stejnou barvou, tedy stále najdeme rozlehlou nezávislou množinu.

\begin{definice}
Nafouknutí vrcholu $x$ do kliky velikosti $r$ je vrchol $x$ nahrazený klikou s
vrcholy $x_1,\dots,x_r$ a každá hrana $(x,y)$ je nahrazená hranami $(x_i,y)$.
\end{definice}

\begin{lemma}\label{lemma:perfektni-2}
Pokud $G$ je perfektní, potom $\forall x, r$ $G'$ vzniklý z $G$ nafouknutím
vrcholu $x$ do kliky $|r|$ je také perfektní.
\end{lemma}

\begin{proof}
Nechť $X$ je množina vrcholů vzniklých nafouknutím $x$. Pokud $K$ je největší
klika v $G'$ tak $X \subseteq K$ nebo $X \cap K = \emptyset$, ale potom je $K$
největší klika i v $G$..

Nechť $I$ je rozlehlá množina v $G$ obsahující $x$. Pro $G'$ vezmeme $I'$ tak,
že za $x$ zvolíme jeden z vrcholů vzniklých nafouknutím. Pokud $X \subseteq K$,
v $I'$ máme vrchol z $X$, a proto i z $K$.

Jinak protože $K$ byla největší už v $G$, už měla vrchol v $I$, tudíž má vrchol
i v $I'$. Tudíž $I'$ je rozlehlá nezávislá množina. Podobně najdeme rozlehlou
nezávislou množinu i v každém $H' \leq G'$.

Tudíž je i $G'$ perfektní.
\end{proof}

\begin{definice}
Doplněk grafu $G = (V,E)$ je graf $\bar G = (V, \binom{V}{2} \setminus E)$.
\end{definice}

\eye $\omega(\bar G) = \alpha(G)$.

\begin{veta}[Slabá věta o perfektních grafech (1972, Lovász)]
$G$ je perfektní právě, když $\bar G$ je perfektní.
\end{veta}

\begin{proof}
Protože doplňek grafu je duální, stačí jednu implikaci.

Nechť $G$ je nejmenší perfektní graf takový, že $\bar G$ není perfektní.

Tudíž musí existovat $H \leq \bar G$, který nemá rozlehlou nezávislou množinu.
Pokud $H \neq \bar G$, $H$ není perfektní a navíc $\bar H \leq G$, ale $\bar H
\neq G$. Tedy $\bar H$ je perfektní. Tím dostáváme spor s minimalitou $G$.

Tedy $\bar G$ nemá rozlehlou nezávislou množinu, tedy pro každou nezávislou
množinu $I$ v $\bar G$ existuje klika $Q$ velikosti $\omega(\bar G)$ taková, že
$Q \cap I = \emptyset$.

Toto tvrzení obrátíme na $G$: pro každou kliku $Q$ v $G$ existuje nezávislá
množina $I$ velikosti $\alpha(G)$ disjunktní s $Q$.

Nechť $Q_1,\dots,Q_t$ jsou všechny kliky v $G$ a $I_j$ je nezávislá množina
velikosti $\alpha(G)$ disjunktní s $Q_j\;\forall j \in [t]$.

Definujme nyní $f(x)$ jako počet množin $I_j$, které obsahují $x$, tedy $|\{j
\in [t] \mid x \in I_j \}|$

Nyní provedeme trik, mějme $G^*$ jako graf vzniklý z $G$ nafouknutím každého
vrcholu $x$ do kliky velikosti $f(x)$. Pokud $f(x) = 0$, vrchol $x$ smažeme.
Nyní každá nezávislá množina $I_j$ si může vybrat jeden z vrcholů ze vzniklé
kliky, který si nevybrala žádná jiná, tím dostaneme $I^*_j$. Všimněme si, že
$I^*_i \cap I^*_j = \emptyset$ a $\bigcup_k I^*_k = V(G^*)$. 

Podle lemmatu 2 je $G^*$ perfektní. Odhadneme $|V(G^*)| = \sum_{x \in V(G)}
f(x) = t\cdot\alpha(G)$. Navíc $\alpha(G^*) = \alpha(G)$. Protože je $G^*$
perfektní, $\omega(G^*) = \chi(G^*)$. Největší klika v $G^*$ vznikla
nafouknutím kliky $Q$ v $G$. Tedy $|Q^*| = \sum_{x \in Q} f(x) = \sum_{j = 1}^t
|Q \cap I_j| \leq t - 1$, každá nezávislá množina má nejvýše jeden vrchol z
$Q$. Proto $\omega(G^*) \leq t-1$.

Dále podle definice barevnosti víme, že $\chi(G^*) \geq \frac{|V(G^*)|}
{\alpha(G^*)} = t$. Máme spor barevnosti, tedy $G^*$ není perfektní, a proto
není perfektní ani $G$.
\end{proof}

\begin{veta}[Silná věta o perfektních grafech (2002, Chudnovsky, Robertson,
Seymour, Thomas)]
$G$ je perfektní právě, když $G$ ani $\bar G$ neobsahuje lichý cyklus délky
$\geq 5$ jako indukovaný podgraf.
\end{veta}

\subsection{Chordální grafy}

\begin{definice}
$G$ je chordální, pokud neobsahuje kružnici délky $\geq 4$ jako indukovaný
podgraf.
\end{definice}

Třída chordálních grafů je uzavřená na $\leq$. 

\begin{definice}
Nechť $G$ je graf a $x,y$ nesousedící vrcholy $G$. Pak $xy$-řez v $G$ je
množina $R \subseteq V(G)$ taková, že $x,y$ jsou v různých komponentách $G -
R$.

Komponenty obsahující $x$ nebo $y$ budeme značit $G_x$ nebo $G_y$.
\end{definice}

\begin{veta}
$G$ je chordální iff $\forall x, y$ nesousedící existuje $xy$-řez, který tvoří
kliku.
\end{veta}

\begin{proof}\leavevmode
\begin{itemize}
\leftimpl Nechť $G$ není chordální, tedy obsahuje indukovanou kružnici $C$
   délky $\geq 4$. Nechť $x,y$ jsou nesousední vrcholy $C$. Pak po jejich
   odebrání $C - \{x,y\} = P_1 \cup P_2$, kde $P_1$ a $P_2$ jsou disjunktní
   cesty a navíc nevedou žádné hrany mezi vrcholy $P_1$ a $P_2$.

   Každý $xy$-řez obsahuje alespoň 1 vrchol z $P_1$ a $P_2$. Tyto dva vrcholy
   nejsou spojeny hranou, tudíž $xy$-řez není klika.

\rightimpl Nechť $x,y$ jsou nesousední vrcholy v chordálním grafu $G$ a $R$ je
   nejmenší $xy$-řez. Tvrdíme, že $R$ tvoří kliku. Pro spor předpokládejme, že
   ne, tedy $\exists u,v \in R$, které jsou nesousední.

   Z minimality řezu víme, že $u$ i $v$ musí mít souseda v $G_x$ i v $G_y$.
   Existuje nejkratší cesta $P_x$ z $u$ do $v$, jejíž vnitřní vrcholy jsou v
   $G_x$, $P_y$ analogicky.

   Sjednocením $P_x$ a $P_y$ dostaneme kružnici délky $\geq 4$, která je
   indukovaným podgrafem $G$, což je spor s chordalitou $G$. \qedhere
\end{itemize}
\end{proof}

\begin{definice}
$N_G(x)$ je množina sousedů $x$ v $G$.

Vrchol $x$ je simpliciální v $G$, pokud $N_G(x)$ tvoří kliku.
\end{definice}

\begin{lemma}
Každý (neprázdný) chordální graf $G$ obsahuje simpliciální vrchol.
\end{lemma}

\begin{proof}
Budeme dokazovat silnější tvrzení, že každý chordální graf je úplný, nebo
obsahuje 2 nesousední simpliciální vrcholy.

Nyní budeme postupovat indukcí podle $n = |V(G)|$. Pro $n = 1$ platí.

Dále pro $n > 1$ je buď $G$ úplný, nebo $G$ obsahuje $x$ a $y$ nesousedící.
Z předchozí věty víme, že existuje $xy$-řez $R$, který tvoří kliku. Mějme
$G^*_x = G[G_x \cup R]$ (graf indukovaný na $G_x \cup R$), analogicky $G^*_y$.

Tyto dva grafy jsou chordální a počet jejich vrcholů je menší, než $n$. Podle
IP jsou to buď kliky nebo mají dva nesousední simpliciální vrcholy. V každém
případě obsahují simpliciální vrchol $s_x$ a $s_y$ mimo $R$.

\eye $N_G(s_x) = N_{G^*_x}(S_x)$, pro $s_y$ analogicky. Kdyby ne, nebyl by $R$
řez. tedy $s_x$ a $s_y$ jsou simpliciální a nesousední v $G$.
\end{proof}

\begin{definice}
Perfektní eliminační schéma grafu $G$ je uspořádání vrcholů $V(G)$
$v_1,\dots,v_n$ takové, že $\forall i \in [n]$ platí, že $N_G(v_i) \cap
\{v_1,\cdots,v_{i-1}\}$ tvoří kliku.
\end{definice}

\begin{veta}
$G$ je chordální právě, když má perfektní eliminační schéma.
\end{veta}

\begin{proof}
Pro implikaci zleva doprava budeme postupovat indukcí dle počtu vrcholů. Podle
předchozího lemmatu má $G$ simpliciální vrchol $s$. Zvolíme $v_n = s$. Sousedi
$v_n$ s indexy menšími než $n$ pak zjevně tvoří kliku. Třída chordálních grafů
je uzavřená na indukovaný podgraf, a na $G \setminus s$ tedy můžeme aplikovat
indukční předpoklad.

Nyní dokážeme druhou implikaci. Graf není chordální, a tedy máme indukovaný
$C_k$ pro $k > 3$. Uvažujme vrchol $C_k$ který je v uspořádání vrcholů
největší. Ten pak má v uspořádání vrcholů dva menší sousedy, které mezi sebou
nemají hranu, a tedy se nejedná o perfektní eliminační schéma.
\end{proof}

\section{Tutteův polynom}

\begin{definice}
\emph{Multigraf} je $G = (V,E)$, kde $E$ je multimnožina prvků $\binom V 2$ a
$V$ (smyčky). 
\end{definice}

Které operace můžeme dělat na multigrafu?
\begin{itemize}
\item Odstranění hrany $e$ \dots $G - e$
\item Kontrakce hrany $e$ \dots $G.e$
\end{itemize}

Pokud $e$ je smyčka, pak $G - e = G.e$. Hrana $e$ je most, pokud $G - e$ má
více komponent, než $G$.

{\bf Značení.}
\begin{itemize}
\item $K(G)$ je počet komponent $G$
\item $r(E) = |V| - K(G)$ je hodnost $E$
\item $n(E) = |E| - r(E)$ je nulita $E$
\end{itemize}

Mějme například prázdný graf $G(V, \emptyset)$. Potom $r(\emptyset) = 0,
n(\emptyset) = 0$.

Když máme graf $G = (V,E)$ a přidáme do něj hranu $e \notin E$, potom rank buď
zůstane stejný když počet komponent se nezmění, nebo se zvýší o 1. Podobně i
nulita se může zvýšit o 1.

\eye $r(E)$ je velikost největší podmnožiny $E$ bez kružnice. $n(E)$ je
velikost největší podmnožiny $F \subseteq E$ takové, že $K((V,E \setminus F)) =
K((V,E))$, tedy jejich odstraněním se nám nezmění počet komponent.

\begin{definice}
Tutteův polynom multigrafu $(V,E)$ je polynom dvou proměnných $x$ a $y$
definovaný:
$$ T_G(x,y) = \sum_{F \subseteq E} (x-1)^{r(E) - r(F)} (y-1)^{n(F)} $$
\end{definice}

Například pro graf trojúhelník je $T (x,y) = (x-1)^{2-1} (y-1)^0 +
3((x-1)^{2-1} (y-1)^0) + 3((x-1)^{2-2} (y-1)^0 + (x-1)^{2-2} (y-1)^1 = (x-1)^2
+ 3(x-1) + 3 + (y-1)$.

\begin{veta}
Pro $G = (V,E)$ souvislý je $T_G(1,1)$ roven počtu koster $G$.
\end{veta}

\begin{proof}
Výraz $(x-1)^{r(E)-r(F)} (y-1)^{n(F)}$ je pro $x,y = 1$ nenulový právě, když
$r(E) = r(F)$ a $n(F) = 0$. V takovém případě je hodnota 1. Toto nastává právě,
když $F$ je kostra grafu.
\end{proof}

Počítání takového polynomu přímo je však velmi otravné. Pojďme si ukázat, jak
skládat polynomy z podgrafů.

\begin{veta}
Nechť $G_1 = (V_1,E_1)$ a $G_2 = (V_2,E_2)$ a $|V_1 \cap V_2| \leq 1$ a $|E_1
\cap E_2| = 0$.  Pro $G = (V,E)$ kde $V = V_1 \cup V_2$ a $E = E_1 \cup E_2$
máme $T_G(x,y) = T_{G_1}(x,y) \cdot T_{G_2}(x,y)$.
\end{veta}

\begin{proof}
Zjevně $F \subseteq E$ lze jednoznačně zapsat jako $F_1 \cup F_2$ takové, že
$F_1 \subseteq E_1$ a $F_2 \subseteq E_2$. Navíc $r_G(F) = r_{G_1}(F_1) +
r_{G_2}(F_2)$ a $n_G(F) = n_{G_1}(F_1) + n_{G_2}(F_2)$.

$T_G(x,y) = \sum_{F \subseteq E} (x-1)^{r(E) - r(F)} (y-1)^{n(F)} \hfil\break
= \sum_{F_1 \subseteq E_1} \sum_{F_2 \subseteq E_2} (x-1)^{r(E) - r(F_1 \cup
F_2)} (y-1)^{n(F_1 \cup F_2)} \hfil\break
= \sum_{F_1 \subseteq E_1} \sum_{F_2 \subseteq E_2} (x-1)^{r_{G_1}(E_1) -
r_{G_1}(F_1) + r_{G_2}(E_2) - r_{G_2}(F_2)} (y-1)^{n_{G_1}(F_1) +
n_{G_2}(F_2)}$.

Tedy můžeme tyto dvě sumy rozdělit na součin dvou sum, což nám dá součin dvou
polynomů.
\end{proof}

\begin{dusledek}
Pokud $e$ je most nebo smyčka, platí $T_{G - e} (x,y) = T_{G . e} (x,y)$.
\end{dusledek}

\begin{veta}
Nechť $G = (V,E)$. Pak $T_G(x,y)$ je jednoznačně určen následujícími rovnostmi:
\begin{enumerate}
\item Pokud $E = \emptyset$, pak $T_G(x,y) = 1$
\item Pokud $E \neq \emptyset$ a $e \in E$, pak:
\begin{enumerate}
\item Pokud $e$ je most, $T_G(x,y) = x T_{G-e}(x,y) = x T_{G.e}(x,y)$.
\item Pokud $e$ je smyčka, $T_G(x,y) = y T_{G-e}(x,y) = y T_{G.e}(x,y)$.
\item Jinak $T_G(x,y) = T_{G-e}(x,y) + T_{G.e}(x,y)$.
\end{enumerate}
\end{enumerate}
\end{veta}

\begin{proof}\leavevmode
\begin{enumerate}
\item Platí zřejmě.
\item Sumu $T_G$ si rozdělíme na $S_1$ pro sčítance neobsahující $e$ a $S_2$
  jej obsahující. Ukážeme:
\begin{itemize}
\item $e$ není most, potom $S_1 = T_{G-e} (x,y)$.
\item $e$ je most, potom $S_1 = (x-1) T_{G-e} (x,y)$.
\item $e$ není smyčka, potom $S_2 = T_{G.e} (x,y)$.
\item $e$ je smyčka, potom $S_2 = (y-1) T_{G.e} (x,y)$.
\end{itemize}

  Spojením těchto podmínek dostaneme postupně různé možnosti.\qedhere
\end{enumerate}
\end{proof}

\begin{definice}
Chromatický polynom multigrafu $G(V,E)$ je $ch_G(b)$ jako počet dobrých
obarvení $G$ pomocí $b$ barev. Pokud $G$ má smyčku, $ch_G(b) = 0$.
\end{definice}

\begin{veta}
Pro každý multigraf $G = (V,E)$ platí $ch_G(b) = (-1)^{|V| + K(G)} b^{K(G)}
T_G(1-b,0)$.
\end{veta}

\textbf {Poznámka.} $ch_G(b)$ lze upravit na výraz $\sum_{F \subseteq E}
(-1)^{|F|} b^{k(v,F)}$.

\begin{proof}
Všimněme si, že $ch_G$ zachovává rekurzivitu, speciálně je to 0, pokud má
smyčku.

\textsl{Tuto část je potřeba doplnit\dots}
\end{proof}

\section{Formální mocninné řady}

\begin{definice}
Pro posloupnost $a_0,a_1,\dots$ reálných čísel je \emph{formální mocninná řada}
zápis tvaru $\sum_{n=0}^\infty a_n x^n$.

Množinou formálních mocninných řad budeme myslet $\R[\![x]\!]$.

$A(x) = \sum_{n=0}^\infty a_nx^n, a_n = [x^n]A(x)$.
\end{definice}

\paragraph{Operace.}
Mějme $A(x) = \sum_{n=0}^\infty a_n x^n$, $B(x) = \sum_{n=0}^\infty b_n x^n$.
Potom:
\begin{align*}
A(x) + B(x) &= \sum_{n=0}^\infty (a_n + b_n) x^n \\
A(x)B(x) &= \sum_{n=0}^\infty \sum_{j=0}^n (a_j + b_{n-j}) x^n
\end{align*}

\begin{fakt}
$\R[\![x]\!]$ tvoří komutativní okruh. Neutrální prvek vůči sčítání je 0,
neutrální prvek vůči násobení je 1.
\end{fakt}

\begin{definice}
Převrácená hodnota formální mocninné řady $A(x)$ je mocninná řada $B(x)$
taková, že $A(x)B(x) = 1$. Pak píšeme, že $B(x) = \frac{1}{A(x)}$ nebo
$A^{-1}(x)$
\end{definice}

\begin{itemize}
\item $A(x) = a_0 \dots A^{-1}(x) = \frac{1}{a_0}$ pro $a \neq 0$
\item $A(x) = \sum_{i=0}^\infty x^i \dots A^{-1}(x) = 1-x$.
\end{itemize}

\begin{veta}
Nechť $A(x) \in \R[\![x]\!]$. Pak $A^{-1}(x)$ existuje právě, když $[x^0]A(x)
\neq 0$.  V takovém případě je $A^{-1}(x)$ jednoznačně určen.
\end{veta}

\begin{proof}
Hledáme $B(x)$ takové, že $A(x)B(x) = 1$, píšeme $A(x) = \sum_{n=0}^\infty
a_nx^n$, $B(x) = \sum_{n=0}^\infty b_nx^n$. Podívejme se na jednotlivé členy.

$1 = a_0b_0 \Rightarrow b_0 = \frac{1}{a_0}$ \\
$0 = a_0b_1 + a_1b_0 \Rightarrow b_1 = \frac{-a_1b_0}{a_0}$ \\
Obecně $b_n = \frac{a_1b_{n-1}+\dots+a_nb_0}{a_0}$.

Z výpočtu $b_n$ plyne, že pokud $a_0 \neq 0$, $B(x)$ existuje a je určena
jednoznačně.
\end{proof}

$\frac{A(x)}{B(x)}$ není definované, ale používáme jako zkrácený zápis
$A(x)B^{-1}(x)$, pokud $B(x)$ má inverzi.

\subsection{Skládání řad}

\begin{definice}
Nechť $A(x) = \sum_{n=0}^\infty a_nx^n$, $B(x) = \sum_{n=0}^\infty b_nx^n$ jsou
mocninné řady.
\begin{enumerate}
\item Pokud $A(x)$ je polynom (tedy od určitého $n_0$ jsou členy $a_n$ nulové),
  $A(B(x)) = a_0B^0(x) + a_1B^1(x) + \dots + a_{n_0} B^{n_0}(x)$, tedy konečně
  mnoho sčítanců.
\item Pokud $b_0 = 0$, potom $A(B(x)) = a_0B^0(x) + a_1B^1(x) + \dots + a_k
  B^k(x)+\dots$.
\end{enumerate}
\end{definice}

\eye Pokud $b_0 = 0$, prvních $k$ koeficientů $B^k(x)$ je nula.

Druhá varianta definice je dobře definovaná, protože dle pozorování
$[x^k](A(B(x))$ závisí pouze na prvních $k+2$ sčítancích.

\begin{definice}
Pro $A(x) = \sum_{n=0}^\infty a_nx^n$ definujeme derivaci $\frac{d}{dx} A'(x) =
\sum_{n=0}^\infty (n+1) \cdot a_{n+1} x^n$.
\end{definice}

Při derivaci se nám tedy celá řada posune vlevo.

\subsection{Obyčejné vytvořující funkce}

\begin{definice}
Nechť ${\cal A}$ je množina objektů, jejíž každý prvek $\alpha$ má definovanou
velikost $|\alpha| \in \N_0$ a pro každé $n \in \N_0$ je v ${\cal A}$ konečně
mnoho prvků velikosti $n$.

Označíme ${\cal A}_n = \{\alpha \in {\cal A} \mid |\alpha| = n\}$ a $a_n =
|{\cal A}_n|$.

Pak obyčejná vytvořující funkce pro ${\cal A}$ je formální mocninná řada
$\OVF({\cal A}) = \sum_{n=0}^\infty a_n x^n$.
\end{definice}

\eye Pokud ${\cal A}$ a ${\cal B}$ jsou disjunktní množiny, potom ${\cal \OVF(A
\cup B) = \OVF(A) + \OVF (B)}$.

\eye ${\cal \OVF(A \times B) = \OVF(A) \cdot \OVF(B)}$, kde $|(\alpha,\beta)| =
|\alpha| + |\beta|$.

\eye $\OVF({\cal A}^k) = (\OVF({\cal A}))^k$.

\smallbreak
Mějme například \textsl{Cukrárnu}, ve které se prodávají z množiny
\textit{Z}\/ákusků:
\begin{itemize}
\item Větrník \dots $30$ Kč
\item Kremrole \dots $30$ Kč
\item Dort \dots $40$ Kč
\item Zmrzlina \dots $50$ Kč
\end{itemize}
A z množiny \textit{N}\/ápojů:
\begin{itemize}
\item Čaj \dots $30$ Kč
\item Káva \dots $30$ Kč
\end{itemize}

Potom $\OVF(Z) = 2x^{30} + x^{40} + x^{50}$, $\OVF(N) = x^{30} + x^{40}$. Pro
$M = Z \cup N$ dostáváme $\OVF(M) = \OVF(N) + \OVF(Z)$.  Dále pak $\OVF(Z)
\times \OVF(N) = \OVF(Z \times N) = 2x^{60} + 3x^{70} + 2x^{80} + x^{90}$.

Nyní, když si zvolíme mocninnou řadu $\frac{1}{1-\OVF(Z)} = 1 + \OVF(Z) +
(\OVF(Z))^2 + (\OVF(Z))^3 + \dots$, koeficient u $x^n$ vyjadřuje, kolika
způsoby si můžeme koupit zákusky za $n$ Kč (záleží na uspořádání). To je dobře
definováno pouze, pokud $[x^0]\OVF(Z) = 0$ (Jinak bychom mohli donekonečna brát
první koeficient). 

\subsection{Exponenciální vytvořující funkce}

\begin{definice}
Exponenciální vytvořující funkce $\EVF({\cal A}) = \sum a_n \frac{x^n}{n!}$.
\end{definice}

\paragraph*{Motivační příklad.}

Mějme $s_n$ počet stromů na vrcholech $1,\dots,n$. Potom $S(x) =
\sum_{n=0}^\infty s_n \frac{x^n}{n!} \in \R[\![x]\!]$.

Nechť $k_n$ odpovídá počtu hamiltonovských kružnic na vrcholech $1,\dots,n$.
Pak $K(x) = \sum_{n=0}^\infty k_n \in \R[\![x]\!]$.

Nyní nechť $A(x) = \sum_{n=0}^\infty \frac{x^n}{n!} n! \sum_{j=0}^n
\frac{s_j}{j!} \cdot \frac{k_{n-1}}{(n-j)!} = \sum_{n=0}^\infty \binom nj s_j
k_{n-j} \frac{x^n}{n!}$.

Dostali jsme počet grafů na vrcholech $1,\dots,n$ složených ze dvou komponent
souvislosti, z nichž jedna je strom a druhá je kružnice.

Když vezmeme $S^2(x)$, dostaneme uspořádané dvojice disjunktních stromů
$(T_1,T_2)$ takové, že $V(T_1) \cup V(T_2) = [n]$. Neuspořádané $k$-tice
získáme pomocí $\frac{S^k(x)}{k!}$.

Nyní bychom chtěli mít počet všech lesů. Uspořádané lesy odpovídají $1 + S(k) +
S^2(k) + \dots$, čímž získáme $\frac{1}{1-S(x)}$, ale pouze v případě, kdy
prohlásíme, že $s_0 = 0$.

Neuspořádané lesy na vrcholech $1,\dots,n$ ale odpovídají $\sum_{n = 0}^\infty
\frac{s^n(x)}{n!} = \exp(S(x))$.

\begin{definice}
Mějme ${\cal A}$ splňující:
\begin{enumerate}
\item $\forall \alpha \in {\cal A}$ má množinu vrcholů $V(\alpha) \subseteq
  \N$, kde $V(\alpha)$ je konečná.
\item $\forall V \subseteq \N$ je konečně mnoho $\alpha \in {\cal A}$ takových,
  že $V(\alpha) = V$.
\item pro konečné množiny $V, W \subseteq \N, |V| = |W|$ platí, že počet
  $\alpha \in {\cal A}$ takových, že $V(\alpha) = V$ je stejný, jako počet
  $\alpha \in {\cal A}$ takových, že $V(\alpha) = W$.
\end{enumerate}

Pak exponenciální vytvořující funkce pro ${\cal A}$ je $\sum a_n
\frac{x^n}{n!}$ kde $a_n$ je počet prvků $\alpha \in {\cal A}$ splňující
$V(\alpha) = \{1,\dots,n\}$.
\end{definice}

EVF má následující vlastnosti:
\begin{itemize}
\item Pokud ${\cal A, B}$ jsou disjunktní s $\EVF({\cal A}) = A(x), \EVF({\cal
  B}) = B(x)$, pak $\EVF({\cal A \cup B}) = A(x) + B(x)$
\item $A(x) \cdot B(x) = \sum c_n \frac{x^n}{n!}$, kde $c_n$ je počet
  uspořádaných dvojic $(\alpha, \beta)$ takových, že $V(\alpha)$ a $V(\beta)$ 
  jsou disjunktní a jejich sjednocení je $\{1,\dots,n\}$.
\item $A^k(x) = \sum d_n \frac{x^n}{n!}$, kde $d_n$ je počet $k$-tic
  $(\alpha_1,\dots,\alpha_k)$, tak, že $V(\alpha_i)$ jsou po dvou disjunktní
  a jejich sjednocení dává $\{1,\dots,n\}$.
\item $\frac{A^k(x)}{k!} = \sum e_n \frac{x^n}{n!}$, kde $e_n$ je počet $k$-tic
  $\{\alpha_1,\dots,\alpha_k\}$, tak, že $V(\alpha_i)$ jsou po dvou disjunktní
  a jejich sjednocení dává $\{1,\dots,n\}$, pokud $a_0=0$.
\item Pokud $\forall \alpha \in {\cal A}$ platí, že $V(\alpha) \neq \emptyset$
  (tedy $a_0 = 0$), pak $\exp(A(x)) = \sum f_n \frac{x^n}{n!}$, kde $f_n$
  je počet množin ${\cal A' \subseteq A}$ takové, že ${\cal A'} =
  \{\alpha_1,\dots,\alpha_k\}$ a $V(\alpha_i)$ jsou po dvou disjunktní a jejich 
  sjednocení je $\{1,\dots,n\}$.
\end{itemize}

Uveďme si nyní příklady EVF:

\nobreak
\begin{itemize}
\item ${\cal A} = \{\text{množina jednoprvkových podmnožin $\N$}\}$, potom
  $V(\{\alpha\}) = \{\alpha\}$, tedy $\EVF({\cal A}) = x$.

  Z toho zjistíme $\EVF$ pro permutace: posloupnost jednoprvkových množin, tedy
  $\EVF(\pi) = 1 + x + x^2 + \dots = \frac{1}{1-x}$.

  Přímým výpočtem $\EVF(\pi) = \sum n! \frac{x^n}{n!} = \sum x^n =
  \frac{1}{1-x}$.

\item Uvažujme počet surjektivních zobrazení $[n] \to [k], n \geq k$.

  $\EVF(\text{$n$-prvkové množiny}) = e^x-1$.

  Potom počet s.z. odpovídá $k$-prvkovým posloupnostem podmnožin $[n]$, které
  pokrývají $[n]$. Tudíž $\EVF = (e^x - 1)^k$.

  Chceme nyní najít koeficient u $x^n$ pro $(e^x-1)^k = \sum_{j=0}^k \binom kj
  (-1)^j e^{(k-j)x} = \sum_{j=0}^k \binom kj (-1)^j \sum_{n=0}^\infty
  \frac{(k-j)^nx^n}{n!}$. Koeficient je proto $a_n = \sum_{j=0}^k \binom kj
  (-1)^j (k-j)^n$.

\item $\EVF(\text{rozklady $[n]$ na $k$ částí}) = \frac{(e^x - 1)^k}{k!}$.

  $\EVF(\text{rozklady $[n]$ na neprázdné částí}) = e^{(e^x - 1)}$.
\end{itemize}

\section{Akce grup a Burnsideovo Lemma}

\begin{definice}
Nechť ${\cal A}$ je množina a $\Gamma$ je grupa s neutrálním prvkem $1_\Gamma$.

Pak akce grupy $\Gamma$ na množině ${\cal A}$ je operace $\cdot: \Gamma \times
{\cal A} \to {\cal A}$ taková, že:

\begin{itemize}
\item $\forall a \in {\cal A} : 1_\Gamma \cdot a = a$
\item $\forall \gamma,\delta \in \Gamma\;\forall a \in {\cal A} : \gamma \cdot
  (\delta \cdot a)  = (\gamma\delta) \cdot a$.
\end{itemize}
\end{definice}

\begin{dusledek}
$\gamma \cdot a = b \Rightarrow \gamma^{-1} \cdot (\gamma \cdot a) =
\gamma^{-1} \cdot b \Rightarrow a = \gamma^{-1} \cdot b$. Tedy zobrazení
$\gamma \cdot {}$ je bijekce.
\end{dusledek}

\begin{definice}
Pro $\gamma \in \Gamma$ je $a \in {\cal A}$ pevný bod, pokud $\gamma \cdot a = a$. $Fix(\gamma) = \{a \mid \gamma \cdot a = a\}$.

Stabilizátor prvku $a \in {\cal A}$ je naopak množna prvků $\gamma \in \Gamma$, které \uv{nemění $a$}. Píšeme $Stab(a)$.
\end{definice}

\eye $a \in Fix(\gamma) \Leftrightarrow \gamma \in Stab(a)$.

\begin{definice}
Nechť $\Gamma$ je grupa a $\cdot$ akce $\Gamma$ na množině ${\cal A}$.
\emph{Orbita prvku} $a \in {\cal A}$ je $[a] = \{b \in {\cal A} \mid \exists
\gamma \in \Gamma : \gamma \cdot a = b \}$
\end{definice}

\begin{definice}
Definujeme relaci $\sim$ na ${\cal A}$: $a \sim b$ pokud $\exists \gamma \in
\Gamma : \gamma \cdot a = b$.
\end{definice}

Relace $\sim$ je ekvivalence a orbity jsou její třídy:
\begin{itemize}
\item Reflexivní: $1_\Gamma \cdot a = a$
\item Symetrická: $\gamma \cdot a = b$, pak $\gamma^{-1} \cdot b = a$
\item Tranzitivní: $\gamma \cdot a = b$ a $\delta \cdot b = c$, pak $(\delta
  \cdot \gamma) \cdot a = c$
\end{itemize}

\begin{priklad}
Mějme koláčky $K$, které jsou rozdělené na čtyři části $a,b,c,d$, kde každá
část má jednu nálpň $N$: $T$varohovou, $P$ovidlovou, nebo $M$akovou.

Triviální počty nám dají, že existuje $3^4 = 81$ různých koláčků. Ale nesmíme
zapomenout na to, že tyto koláčky můžou být různě otočené. Třebá koláček s
náplněmi $TMTM$ je stejný, jako koláček $MTMT$.

Zaveďme si nyní grupu $\Gamma = \{0^\circ, 90^\circ, 180^\circ, 270^\circ\}$
označující možné otočení koláčků. Naším cílem bude nyní spočítat počet orbit.

Nejprve spočtěme pevné body:
\begin{itemize}
\item $Fix(0^\circ) = K$
\item $Fix(90^\circ) = Fix(270^\circ) = \{MMMM, TTTT, PPPP\}$
\item $Fix(180^\circ) = \{abab \mid a, b \in N\}$
\end{itemize}

Nyní počítejme stabilizátory a orbity podle koláčků:
\begin{itemize}
\item $Stab(TPTP) = \{0^\circ, 180^\circ\}, [TPTP] = \{TPTP, PTPT\}$
\item $Stab(MMMM) = \Gamma, [MMMM] = \{MMMM\}$
\item $Stab(TPMT) = \{0^\circ\}, [TPMT] = \{TPMT, TTPM, MTTP, PMTT\}$
\end{itemize}

Jak vidíme, velikost orbity souvisí přímo s velikostí stabilizátoru.
\end{priklad}

\begin{lemma}
Nechť $\Gamma$ je konečná grupa s akcí na množině ${\cal A}$. Pak pro každé $a
\in {\cal A}: |Stab(a)| \cdot |[a]| = |\Gamma|$.
\end{lemma}

\begin{proof}
Ukažeme $|[a]| = \frac{|\Gamma|}{|Stab(a)|}$

Vezměme $b \in [a]$. Kolik existuje prvků $\gamma \in \Gamma$, pro které
$\gamma \cdot a = b$? Určitě alespoň jeden, který označíme $\delta$.

Nechť $S_{ab} = \{\gamma \in \Gamma \mid \gamma \cdot a = b\}$. Tvrdíme
$|S_{ab}| = |Stab(a)|$, zkonstruujeme bijekci $\varphi: Stab(a) \to S_{ab}$
tak, že $\varphi(\gamma) = \gamma \cdot \delta$.

Vidíme, že $\varphi$ je prosté. Pokud $\delta \cdot \gamma = \delta \cdot
\gamma'$, vynásobíme rovnici zleva $\delta^{-1}$ a dostáváme $\gamma =
\gamma'$. Podobně ukážeme, že je i na. Pokud $\delta' \in S_{ab}: \delta' \cdot
a = b$, potom $\delta \cdot (\delta^{-1} \cdot \delta') a = \delta \cdot
\delta^{-1} \cdot b = b$. Tedy $\delta^{-1} \cdot \delta' \in Stab(a)$ a
$\varphi(\delta^{-1} \cdot \delta') = \delta'$.
\end{proof}

\begin{veta}[Burnsideovo lemma, Cauchyho-Frobeniova formule]
Nechť $\Gamma$ je konečná grupa s akcí na ${\cal A}$.
\begin{enumerate}
\item Pokud ${\cal A}$ je konečná, tak počet orbit je $|\faktor{\cal
  A}{\Gamma}| = \frac{1}{|\Gamma|} \sum_{\gamma \in \Gamma} Fix(\gamma)$.
\item (Vážená verze) Nechť má každá orbita $o \in \faktor{\cal A}{\Gamma}$
  přiřazenou váhu $w(o)$. Pak 
\[\sum\limits_{o \in \faktor{\cal A}{\Gamma}} w(o)=
  \frac{1}{|\Gamma|} \cdot \sum\limits_{\gamma \in \Gamma} \sum\limits_{a \in Fix(\gamma)}
  w([a]).\]
\end{enumerate}
\end{veta}

\begin{proof}
Stačí ukázat druhý případ, protože první případ je speciální.

$$\sum_{\gamma \in \Gamma} \sum_{a \in Fix(\gamma)} w([a]) = \sum_{a
\in {\cal A}} \sum_{\gamma \in Stab(a)} w([a]) = \sum_{o \in \faktor{\cal
A}{\Gamma}} \sum_{a \in o} \sum_{\gamma \in Stab(a)} w([a]) = \sum_{o \in
\faktor{\cal A}{\Gamma}} w(o) \sum_{a \in o} |Stab(a)|.$$

Nyní využijeme předchozí lemma a dostáváme

$$ \sum_{o \in \faktor{\cal A}{\Gamma}} w(o) \sum_{a \in o} \frac{\Gamma}{|o|}
= \sum_{o \in \faktor{\cal A}{\Gamma}} w(o) \cdot \frac{\Gamma}{|o|} \cdot |o|
= \sum_{o \in \faktor{\cal A}{\Gamma}} w(o) \cdot |\Gamma|. \eqno{\mbox{\qedhere}}$$
\end{proof}

Díky této větě už můžeme spočítat, kolik různých koláčků skutečně existuje:
$ \left|\faktor{K}{\Gamma}\right| = \frac14 (81 + 3 + 9 + 3) = 24. $

Nyní uvažujme koláčky $R$ jiného druhu, speciálně s rozinkami. Tentokrát na
každou část budeme dávat nezáporný počet rozinek. Tedy $R = \{(a,b,c,d) \mid
a,b,c,d \in \N_0\}$. Chceme spočítat počet různých koláčků, pokud máme $n$
rozinek. To nám dá mocninnou řadu $A(x) = \sum_{n \geq 0} a_n x^n = 1 + x +
3x^2 + \dots$

Využijeme stejnou grupu $\Gamma$ jako v předchozím příkladě. Všechny koláčky v
každé orbitě mají stejný počet rozinek. Za váhu orbity $o$ prohlásíme $x^n$,
kde $n$ je počet rozinek v koláčcích z $o$.  Potom $A(x) = \sum_{o \in
\faktor{R}{\Gamma}} w(o)$. Z vážené verze dískáváme:
%
$$ A(x) = \frac{1}{|\Gamma|} \cdot \sum_{\gamma \in \Gamma} \sum_{k \in
Fix(\gamma)} w([k]) $$

Všechny možnosti si zapíšeme do tabulky, kterou následně sečteme a vydělíme 4. Tím dostaneme výslednou vytvořující funkci:

\begin{tabular}{r|c|c|c}
 & $0^\circ$ & $90^\circ$, $270^\circ$ & $180^\circ$ \\ \hline
$Fix(\gamma)$ & $R$ & $(a,a,a,a)$ & $(a,b,a,b)$ \\
$\sum w([k])$ & $\frac{1}{(1-x)^4}$ & $\frac{1}{1-x^4}$ & $\frac{1}{(1-x^2)^2}$
\\
\end{tabular}

\section{Extremální věty}

\begin{definice}
$\ex(n,H)$ je největší možný počet hran v grafu na $n$ vrcholech, který
neobsahuje $H$ jako podgraf.
\end{definice}

\begin{definice}
Turánův graf na $n$ vrcholech s $r$ partitami, značený $T_{n,r}$ je úplný
$r$-partitiní graf na $n$ vrcholech, jehož partity mají velikosti $n/r$
(zaokrouhlené nahoru nebo dolů).
\end{definice}

Například $T_{n,2}$ je úplný bipartitní graf $K_{\lfloor n/2 \rfloor,\lceil n/2
\rceil}$.

Počet hran grafu $T_{n,r}$ budeme značit $t_{n,r}$.

\eye $\ex(n,K_{r+1}) \geq t_{n,r}$, protože $T_{n,r}$ neobsahuje $K_{r+1}$ jako podgraf.

\begin{lemma}\label{lemma:r_partit_max_hran}
Každý $r$-partitní graf na $n$ vrcholech má nejvýše $t_{n,r}$ hran.
\end{lemma}

\begin{proof}
Nechť $G = (V,E)$ je $r$-partitní graf na $n$ vrcholech s co nejvíce hranami.
Ukážeme, že $G \cong T_{n,r}$.

Nechť $P_1,P_2,\dots,P_r$ jsou partity $G$ a $|P_1| \leq |P_2| \leq \dots \leq
|P_r|$. Pokud $|P_r| \leq |P_1| + 1$, tak $G \cong T_{n,r}$ máme splněno.

Předpokládejme, že $|P_r| \geq |P_1| + 2$. Potom ale můžeme přesunout jeden
vrchol z $P_r$ do $P_1$ a doplnit hrany, čímž najdeme $G'$ o více hranách.

V $G'$ všem vrcholům $P_r$ se při přesunu zvýší stupeň alespoň o 1 a vrcholům
$P_1$ sice klesne stupeň o 1, ale má stále alespoň o 1 vrchol méně. To je spor
s maximalitou hran.
\end{proof}

\begin{lemma}\label{lemma:r_partit_vice_hran}
Nechť $G = (V,E)$ je graf na $n$ vrcholech neobsahující $K_{r+1}$. Potom
existuje úplný $r$-partitní graf $H = (V,F)$ takový, že $\forall x \in V :
\deg_G(x) \leq \deg_H(x)$.
\end{lemma}

\begin{proof}
Indukcí podle $r$. Pro $r = 1$ každý graf bez $K_2$ je $1$-partitní, lze vzít
$G=H$.

Předpokládejme, že $r \geq 2$ a platí lemma pro grafy bez $K_r$. Nechť $G$ je
graf neobsahující $K_{r+1}$, $v \in V$ je vrchol největšího stupně, $S$ je
množina jeho sousedů a $G_S$ je podgraf $G$ indukovaný $S$.

$G_S$ neobsahuje $K_r$ (jinak by $G$ obsahoval $K_{r+1}$ na množině $S \cup
\{v\}$). Tedy podle indukce existuje $r-1$-partitní graf $H_S = (S,F_S)$
splňující $\forall y \in S: \deg_{G_S}(y) \leq \deg_{H_S}(y)$.

Nechť $H$ je úplný $r$-partitní graf vzniklý z $H_S$ přidáním $V \setminus S$
jako $r$-tou partitu. Tvrdíme, že $\forall x \in V : \deg_G(x) \leq \deg_H(x)$.
Rozlišíme dva případy:
\begin{itemize}
\item $x \in S$, potom $\deg_G(x) \leq \deg_{G_S}(x) + |V \setminus S|\le 
\deg_{H_S}(x) + |V\setminus S| =
  \deg_{H}(x)$.
\item $x \notin S$, potom $\deg_G(x) \leq \deg_G(v) = |S| = \deg_H(x)$.\qedhere
\end{itemize}
\end{proof}

\begin{veta}[Turán, 1941]
$\ex(n,K_{r+1}) = t_{n,r}$.
\end{veta}

\begin{proof}
Už víme, že $\ex(n,K_{r+1}) \geq t_{n,r}$. Nechť $G = (V,E)$ je graf na $n$
vrcholech bez $K_{r+1}$ s co nejvíce hranami. Podle lemmatu
\ref{lemma:r_partit_vice_hran} existuje pro $G$ nějaký úplný $r$-partitní graf
$H=(V,F)$ s $|E| \leq |F|$. Podle lemmatu \ref{lemma:r_partit_max_hran} $|F|
\leq t_{n,r}$.

Tedy $\ex(n,K_{r+1}) \leq t_{n,r}$.
\end{proof}

\begin{definice}
$k$-uniformní hypergraf je dvojice $(V,E)$, kde $E$ je množina $k$-prvkových
podmnožin $V$.
\end{definice}

$f(n,k)$ bude největší počet hyperhran v $k$-uniformním hypergrafu na $n$
vrcholech, který neobsahuje $2$ disjunktní hyperhrany.

\eye Pokud $n < 2k$, tak $f(n,k) = \binom nk$.

\eye Pokud $n \geq 2k$, tak $f(n,k) \geq \binom{n-1}{k-1}$.

Označme si $\Z_n$ množinu $[n]$ s operací sčítání $\bmod n$. Interval délky $k$
je jakákoliv podmnožina $\Z_n$, jejíž tvar je \{i,i+1,\dots,i+k-1\}.

\begin{lemma}\label{lemma:ex_hypergraf_intervaly}
Nechť $I_1,I_2,\dots,I_m$ je množina intervalů $\Z_n$ délky $k$ takových, že
každé dva se protínají a $n \geq 2k$. Potom $m \leq k$.
\end{lemma}

\begin{proof}
BÚNO $I_1 = \{0,1,\dots,k-1\}$. Označme ${\cal S} = \{I_2,\dots,I_m\}$. Pro
každé $i \in \{1,\dots,k-1\}$ mějme intevaly $J_{<i} = \{i-1,\dots,i-k\}$ a
$J_{\geq i} = \{i,i+1,\dots,i+k-1\}$.

Každý interval z $\cal S$ je roven $J_{<i}$ nebo $J_{\geq i}$ pro nějaké $i \in
\{1,\dots,k-1\}$, jinak by neprotínal $I_1$. Navíc $J_{<i} \cap J_{\geq i} =
\emptyset$, protože $n \geq 2k$. Takže pro každé $i \in \{1,\dots,k-1\}$
existuje nejvýše jeden interval.

Tedy $|{\cal S}| \leq k-1$, tudíž $m \leq k$.
\end{proof}

\begin{veta}[Erd\H os-Ko-Rado,1961]
Pro každé $k$ a $n$ takové, že $n \geq 2k$, platí $f(n,k) = \binom{n-1}{k-1}$.
\end{veta}

\begin{proof}
Nechť $G = (V,E)$ je $k$-uniformní hypergraf na $n$ vrcholech, jehož každé dvě
hyperhrany se protínají, splňující $|E| = f(k,n)$.

Vezměme si náhodnou bijekci $\pi$ z $V$ na $\Z_n$. Nechť $X$ je počet hyperhran
z $|E|$, které se pomocí $\pi$ převedou na interval. Dle lemmatu
\ref{lemma:ex_hypergraf_intervaly} platí $X \leq k$ pro každé $\pi$.

Navíc platí, $\mathbb E[X] = |E| \cdot {\rm Pr}_\pi[\pi \text{ zobrazí danou
$k$-prvkovou množinu na interval}] = |E| \cdot n/\binom nk$.  Protože $\mathbb
E[X] \leq k$, máme $|E| \cdot n/\binom nk \leq k$, tedy $|E| \leq \frac kn
\cdot \binom nk = \binom{n-1}{k-1}$.
\end{proof}

\subsection{Lemma o slunečnici}

\begin{definice}
Slunečnice ($\Delta$-systém) s $k$ lístky a centrem $Y$ je systém množin
$S_1,\dots,S_k$ takový, že $S_i \cap S_j = Y\;\forall i,j \in [k], i \neq j$.
\end{definice}

$S_i \setminus Y$ jsou lístky, požadujeme aby byly neprázdné, zatímco centrum
$Y$ prázdné být může.

\begin{lemma}[O slunečnici; Erd\H os-Rado, 1960]
Nechť $\cal F$ je systém $s$-prvkových množin. Pokud $|{\cal F}| > s!(k-1)^s$,
pak $\cal F$ obsahuje slunečnici s $k$ lístky.
\end{lemma}

\begin{proof}
Indukcí dle $s$: $s = 1$, $|{\cal F}| > k-1$, tudíž ${\cal F}$ obsahuje alespoň
$k$ různých jednoprvkových množin, což je slunečnice.

Nyní nechť $S \geq 2$. Mějme ${\cal A} = \{A_1,\dots,A_t\}$ maximální systém po
dvou disjunktních množin v ${\cal F}$. Uvažujme $B = \bigcup {\cal A}$. Rovněž
$t < k$, jinak máme slunečnici s $k$ lístky.

\eye Každá množina z ${\cal F \setminus \cal A}$ obsahuje prvek z $B$.

Potom $|B| \leq s \cdot (k-1)$. Budeme počítat dvěma způsoby. Z Dirichletova
principu existuje $x \in B$, který je obsažen alespoň v $\frac{|{\cal
F}|}{|B|}$ množinách $\cal F$. To je ostře víc, než $\frac{s!(k-1)^s}{s(k-1)} =
(s-1)!(k-1)^{s-1}$.

Zafixujeme si takový prvek $x$ a definujeme ${\cal F}_x = \{S \setminus \{x\}
\mid S \in {\cal F}, x \in S\}$. To je systém ostře víc než $(s-1)!(k-1)^{s-1}$
množin velikosti $s-1$. Ten z indukčního předpokladu obsahuje slunečnici s $k$
lístky. Když do množin slunečnice přidáme $x$, dostaneme novou slunečnici s $k$
lístky ve $\cal F$.
\end{proof}

Toto lemma je ale celkem staré a máme velmi vysoké číslo. Nešlo by to zlepšit?

\smallskip
\textbf{Domněnka} (Erd\H os-Rado, 1960).\; \textit{$s!(k-1)^s$ jde nahradit
$[C(k)]^s$.}
\smallskip

Co je známo:
\begin{itemize}
\item Existuje systém $s$-prvkových množin velikosti $(k-1)^s$ bez slunečnice s
  $k$ lístky. Vezměme $s$-tici disjunktních množin $A_i,\dots,A_s$ velikosti
  $k-1$, ze které uděláme systém množin $S$, kde $S$ obsahuje právě 1 prvek z
  každého $A_i$.
\end{itemize}

\section{Hamiltonovské grafy}

Jistě jsme už dříve slyšeli o nejznámějším NP-úplným problému, a to problému
obchodního cestujícího. V něm je za úkol najít kružnici obsahující všechny
vrcholy takovou, že její váha je co nejmenší.

Avšak dá se ukázat, že jen nalezení této kružnice, zvané hamiltonovské, je samo
o sobě NP-úplný problém. Pojďme nyní alespoň zjistit, které grafy tuto kružnici
určitě obsahují nebo neobsahují.

\begin{definice}
Graf je hamiltonovský, pokud obsahuje hamiltonovskou kružnici, tedy kružinci
procházející všemi vrcholy.

Hamiltonovská cesta je cesta procházející všemi vrcholy.
\end{definice}

\begin{definice}
Bondyho-Chvátalův uzávěr grafu $cl(G)$ je graf vzniklý z $G$ postupným
přidáváním hran mezi vrcholy $x$ a $y$ takové, že $\deg(x) + \deg(y) \geq
|V(G)|$.
\end{definice}

Tento uzávěr má pěkné vlastnosti vzhledem k existenci hamiltonovské kružnice,
respektive nám dokazuje její existenci:

\begin{veta}[Bondy-Chvátal]\label{veta:bondy-chvatal}
$G$ je hamiltonovský právě tehdy, když $cl(G)$ je hamiltonovský.
\end{veta}

Z této ekvivalence již získáváme důsledky:

\begin{dusledek}[Oreho věta]
Graf s $n \geq 3$ vrcholy je hamiltonovský, pokud pro každý pár nesousedních
vrcholů $x$ a $y$ platí $\deg(x) + \deg(y) \geq n$.
\end{dusledek}

\begin{dusledek}[Diracova věta]
Graf s $n \geq 3$ vrcholy je hamiltonovský, pokud má minimální stupeň $\geq
\frac n2$.
\end{dusledek}

Tento odhad je nejlepší možný, představme si dvě kliky velikosti $m$ spojené
jedním vrcholem. Tento graf není hamiltonovský, má $2m-1$ vrcholů, ale
minimální stupeň je $m-1$, tedy $\lfloor\frac{2m-1}2\rfloor$.

\begin{proof}[Důkaz věty \ref{veta:bondy-chvatal}]
Dokážeme: $G$ je hamiltonovský právě, když $G^+ = G \cup \{xy\}$ je
hamiltonovský, kde $xy$ je hrana mezi nesousedními vrcholy takovými, že
$\deg_G(x) + \deg_G(y) \geq |V(G)|$. Z tohoto tvrzení již věta plyne.

\begin{itemize}
\rightimpl Triviální, přidání hrany určitě neznemožní existenci kružnice.

\leftimpl Nechť $C = \{v_1 = x,\dots,v_n = y\}$ je hamiltonovská kružnice v
   $G^+$.  Pokud pro nějaké $i \in \{2,\dots,n-2\}$ existují hrany $xv_{i+1}$ a
   $yv_i$, můžeme kružnici přesměrovat přes tyto dvě hrany a $G$ má HK.

   Definujme $I_1 = \{i \in \{2,\dots,n-2\} \mid xv_{i+1} \in E(G)\}$ a 
   $I_2 = \{i \in \{2,\dots,n-2\} \mid yv_{i} \in E(G)\}$. Pokud $I_1 \cap I_2
   \neq \emptyset$, našli jsme $i$.

   $|I_1 \cup I_2| \leq n-3$. Dále $|I_1| = \deg_G(x) - 1$ a naopak $|I_2| =
   \deg_G(y) - 1$. Tudíž $|I_1| + |I_2| = \deg_G(x) + \deg_G(y) - 2 \geq n-2$
   podle podmínky na stupně v $G$. Tudíž musí být $|I_1 \cap I_2| > 0$.\qedhere
\end{itemize}

\end{proof}

Zatím umíme ukázat, že graf je hamiltonovský jen podle stupňů vrcholů. Ale
třeba takový cyklus o $n$ vrcholech je hamiltonovský, i když minimální stupeň
je $2$. Proto by se měla hamiltonovskost ukázat pomocí $k$-souvislosti.

\begin{veta}
Každý $k$-souvislý graf s $n \geq 3$ vrcholy a $\alpha(G) \leq k$ je
hamiltonovský.
\end{veta}

\begin{proof}
Nechť $C = v_1,\dots,v_m$ nejdelší kružnice v $G$. Pro spor předpokládejme, že
$C$ není hamiltonovská kružnice, tedy $\exists v \in V(G) - V(c)$.

Nechť $\cal F$ je největší systém cest z $v$ do $C$ navzájem disjunktních.
Potom $|{\cal F}| \geq \min(|C|, k)$ z Mengerovy věty. Pokud $\exists i$
takové, že $P_i, P_{i+1} \in {\cal F}$, vezmeme $C' = C \setminus v_iv_{i+1}
\cup P_i \cup P_{i+1}$ (totéž pro $P_1$ a $P_m$). Proto rovněž $|{\cal F}| <
|C|$.

Přemýšlejme, že existují cesty $P_i, P_j$ a hrana $v_{i+1}v_{j+1}$. Potom $c' =
P_i,v_i,v_{i-1}\dots,v_{j+1},v_{i+1},\dots,v_j,P_j$, což je spor s minimalitou.

Pak $J = \{v_{i+1 \bmod m}\ \mid i \in I\}$ je nezávislá množina velikosti
$|I|$, $|F| \geq k$, tudíž $|I| = k$. Navíc $v_{i+1}v$ není hrana (jinak by
$v_{i+1}v \in \cal F$). Dále $J \cup \{v\}$ je nezávislá množina velikosti
$k+1$ a $\alpha(G) > k$.
\end{proof}

\end{document}
