\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_{ 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}