ne¾ jsou grafy rovinné. Tím správným universem jsou minorovì uzavøené tøídy:
\s{Definice:}
-Graf $H$ je {\I minorem} grafu $G$ (znaèíme $H \preceq G$) $\equiv$ $H$ lze z $G$ získat
+Graf $H$ je {\I minorem} grafu $G$ (znaèíme $H \preceq G$), pokud lze $H$ získat z~$G$
mazáním vrcholù èi hran a kontrahováním hran (s~odstranìním smyèek a násobných hran).
\s{Pozorování:}
-$H \subseteq G \Rightarrow H \preceq G$.
+Relace $\preceq$ je èásteèné uspoøádání na tøídì v¹ech grafù
+(reflexivita a tranzitivita plynou pøímo z~definice, pro antisymetrii si staèí
+v¹imnout, ¾e jak mazáním, tak kontrakcemi klesá souèet poètu vrcholù s~poètem hran).
+
+\s{Pozorování:}
+Pokud je graf~$H$ podgrafem grafu~$G$, pak je také jeho minorem.
+Opaènì to neplatí: napøíklad $C_3$ je minorem libovolné del¹í kru¾nice,
+ale urèitì ne jejím podgrafem.
\s{Definice:}
-Tøída grafù $\cal C$ je {\I minorovì uzavøená} $\equiv \forall G,H: G \in {\cal C}, H \preceq G \Rightarrow H \in {\cal C}$.
+Tøída grafù $\cal C$ je {\I minorovì uzavøená,} pokud kdykoliv $G\in {\cal C}$
+a $H\preceq G$, platí také $H \in {\cal C}$.
+
+\s{Pøíklady:}
+Tøída v¹ech grafù a prázdná tøída jsou jistì minorovì uzavøené. Tìm øíkáme {\I triviální}
+tøídy. Mezi ty netriviální patøí tøeba lesy, rovinné grafy, grafy nakreslitelné na dal¹í
+plochy, grafy nakreslitelné do ${\bb R}^3$ tak, ¾e ¾ádná kru¾nice netvoøí uzel.
-\s{Vìta:} (Robertson, Seymour)
-Pokud je $\cal C$ minorovì uzavøená tøída grafù, existuje koneèná mno¾ina grafù $Z$ taková,
-¾e pro ka¾dý graf $G$ platí:
-$$G \not\in {\cal C} \iff \exists H \in Z: H \preceq G.$$
-Jinými slovy, ka¾dou minorovì uzavøenou tøídu lze charakterizovat {\I koneèným} poètem zakázaných minorù.
+\def\Forb{{\rm Forb}}
+
+\s{Definice:}
+Pro tøídu grafù ${\cal C}$ definujeme $\Forb({\cal C})$ jako tøídu v¹ech grafù,
+jejich¾ minorem není ¾ádný graf z~${\cal C}$. Pro zjednodu¹ení znaèení budeme pro
+koneèné tøídy psát $\Forb(G_1,\ldots,G_k)$ namísto $\Forb(\{G_1,\ldots,G_k\})$.
+
+\s{Pøíklady:}
+$\Forb(K_1)$ je tøída v¹ech grafù, které neobsahují ¾ádnou hranu.
+$\Forb(C_3)$ je tøída v¹ech lesù.
+$\Forb(K_5,K_{3,3})$ jsou v¹echny rovinné grafy -- to je minorová analogie
+Kuratowského vìty (pokud graf~$G$ obsahuje dìlení grafu~$H$, pak je $H\preceq G$;
+opaènì to obecnì není pravda, ale zrovna pro dvojici $K_5$ a $K_{3,3}$ to funguje;
+zkuste si sami).
+
+Lze ka¾dou minorovì uzavøenou tøídu~${\cal C}$ zapsat jako $\Forb({\cal F})$
+pro nìjakou tøídu~${\cal F}$ zakázaných minorù? Zajisté ano, staèí napøíklad
+zvolit~${\cal F}$ jako doplnìk tøídy~${\cal C}$. Slavná Robertsonova-Seymourova
+vìta \cite{rs:wagner} dokonce zaruèuje existenci {\I koneèné} tøídy zakázaných minorù.
To není samo sebou, dokazuje se to dosti obtí¾nì (a~je to jedna z~nejslavnìj¹ích kombinatorických
vìt za~posledních mnoho let), ale plyne z~toho spousta zajímavých dùsledkù.
-Pìkné shrnutí této teorie najdete napøíklad v~Diestelove knize~\cite{diestel:gt}.
+My si vystaèíme s~daleko jednodu¹¹ími prostøedky a zájemce o~hlub¹í studium minorové
+teorie odká¾eme na Diestelovu knihu~\cite{diestel:gt}.
+
+Ve~zbytku této sekce doká¾eme následující vìtu, která je zobecnìním klasického
+tvrzení o~hustotì rovinných grafù na minorovì uzavøené tøídy:
-\s{Pozorování:} Napøíklad pro rovinné grafy jsou tìmi zakázanými minory právì
-$K_{3,3}$ a $K_5$. To plyne z~Kuratowského vìty: jedna implikace je triviální,
-druhá dá trochu práce: pokud je $K_{3,3} \preceq G$, najde se v~$G$ podgraf
-isomorfní nìjakému dìlení~$K_{3,3}$; pokud je $K_5 \preceq G$, podgraf isomorfní
-dìlení~$K_5$ se v~$G$ najít nemusí, ale pokud se nenajde, najde se tam podgraf isomorfní
-dìlení $K_{3,3}$. (Zkuste si sami.)
+\s{Definice:} {\I Hustotou} neprázdného grafu~$G$ nazveme $\varrho(G) = \vert E(G) \vert
+/ \vert V(G) \vert$. Hustotou tøídy $\varrho(C)$ pak nazveme supremum z~hustot v¹ech
+neprázdných grafù le¾ících v~této tøídì.
-\s{Vìta:} (Robertson, Seymour)
+\s{Vìta (o hustotì minorovì uzavøených tøíd):}
Pokud je tøída grafù $\cal C$ minorovì uzavøená a netriviální (alespoò jeden graf v~ní le¾í
-a alespoò jeden nele¾í), pak $\exists c > 0: \forall G \in {\cal C}:
-\vert E(G) \vert \leq c\cdot \vert V(G) \vert$.
+a alespoò jeden nele¾í), pak má koneènou hustotu.
\s{Dùsledek:}
-Jeliko¾ v¹echny grafy vygenerované pøedchozím algoritmem jsou minory grafu ze~vstupu,
-mù¾eme pro odhad jejich hustoty pou¾ít pøedchozí vìtu a dostaneme lineární èasovou slo¾itost
-dokonce pro ka¾dou netriviální minorovì uzavøenou tøídu grafù.
+Pokud pou¾íváme kontrahující Borùvkùv algoritmus na grafy le¾ící v~nìjaké netriviální
+minorovì uzavøené tøídì, pak v¹echny grafy, které algoritmus v~prùbìhu výpoètu sestrojí,
+le¾í také v~této tøídì, tak¾e na odhad jejich hustoty mù¾eme pou¾ít pøedchozí vìtu.
+Opìt vyjde, ¾e èasová slo¾itost algoritmu je lineární.
+
+\>{\I Dùkaz vìty:}
+Uká¾eme nejprve, ¾e pro ka¾dou tøídu $\cal C$ existuje nìjaké~$k$ takové, ¾e
+${\cal C} \subseteq \Forb(K_k)$.
+
+U¾ víme, ¾e ${\cal C}$ lze zapsat jako $\Forb({\cal F})$ pro nìjakou tøídu~${\cal F}$.
+Oznaème~$F$ graf z~${\cal F}$ s~nejmen¹ím poètem vrcholù; pokud existuje více takových,
+vybereme libovolný. Hledané~$k$ zvolíme jako poèet vrcholù tohoto grafu.
+
+Inkluze tvaru ${\cal A}\subseteq {\cal B}$ je ekvivalentní tomu, ¾e kdykoliv nìjaký graf~$G$
+nele¾í v~${\cal B}$, pak nele¾í ani v~${\cal A}$. Mìjme tedy nìjaký graf $G\not\in\Forb(K_k)$.
+Proto $K_k \preceq G$. Ov¹em triviálnì platí $F\preceq K_k$ a relace \uv{být minorem}
+je tranzitivní, tak¾e $F\preceq G$, a~proto $G\not\in {\cal C}$.
+
+Víme tedy, ¾e ${\cal C} \subseteq \Forb(K_k)$. Proto musí platit $\varrho({\cal C}) \le
+\varrho(\Forb(K_k))$. Tak¾e postaèuje omezit hustotu tøíd s~jedním zakázaným minorem,
+který je úplným grafem, a~to plyne z~následující Maderovy vìty.
+\qed
+
+\s{Vìta (Maderova):}
+Pro ka¾dé~$k\ge 2$ existuje $c(k)$ takové, ¾e kdykoliv má graf hustotu alespoò $c(k)$,
+obsahuje jako podgraf nìjaké dìlení grafu~$K_k$.
+
+\proof
+Viz Diestel \cite{diestel:gt}.
\h{Jarníkùv algoritmus s Fibonacciho haldou}
\:Zaèneme libovolným vrcholem $v_0$, $T\leftarrow \{v_0\}$.
\:Do~haldy $H$ umístíme v¹echny hrany vedoucí z~$v_0$.
\:Opakujeme, dokud $H\neq\emptyset$:
-\::$vw\leftarrow \<DeleteMin>(H)$, pøièem¾ $v\not\in T, w\in T$.
+\::$vw\leftarrow \<ExtractMin>(H)$, pøièem¾ $v\not\in T, w\in T$.
\::$T\leftarrow T\cup\{vw\}$
\::Pro v¹echny sousedy $u$ vrcholu $v$, kteøí dosud nejsou v~$T$, upravíme haldu:
\:::Pokud je¹tì v~$H$ není hrana incidentní s~$u$, pøidáme hranu~$uv$.
\s{Èasová slo¾itost:}
Slo¾itost tohoto algoritmu bude $\O(m+n\log n)$, nebo» vnìj¹í cyklus se provede
-nanejvý¹ $n$-krát, za~\<DeleteMin> v~nìm tedy zaplatíme celkem $\O(n\log n)$, za~pøidávání
+nanejvý¹ $n$-krát, za~\<ExtractMin> v~nìm tedy zaplatíme celkem $\O(n\log n)$, za~pøidávání
vrcholù do~$H$ a~nalézání nejlevnìj¹ích hran zaplatíme celkem $\O(m)$ (na~ka¾dou hranu takto
sáhneme nanejvý¹ dvakrát), za~sni¾ování vah vrcholù v~haldì rovnì¾ pouze $\O(m)$
(nanejvý¹ $m$-krát provedu porovnání vah a \<DecreaseKey> v~kroku~\the\algcnt\ za~$\O(1)$).
projects / ga.git / blobdiff