\input ../sgr.tex

\prednaska{6}{Rychlejší algoritmy na minimální kostry}{}

V~této kapitole popíšeme několik pokročilejších algoritmů pro problém minimální
kostry. Vesměs to budou různá vylepšení klasických algoritmů z~minulé kapitoly.

\h{Upravená verze Borůvkova algoritmu pro rovinné grafy}

Vyjdeme z myšlenky, že můžeme po každém kroku původního Borůvkova algoritmu vzniklé komponenty
souvislosti grafu kontrahovat do jednoho vrcholu a tím získat menší graf, který můžeme
znovu rekurzivně zmenšovat. To funguje obecně, ale ukážeme, že pro rovinné grafy tak dosáhneme
lineární časové složitosti.

\s{Pozorování:}
Pokud $F \subseteq {\rm MST}(G)$ (kde ${\rm MST}(G)$ je minimální kostra grafu~$G$), $G'$~je graf vzniklý
z~$G$ kontrakcí podél hran z~$F$, pak kostra grafu~$G$, která vznikne z~${\rm MST}(G')$ zpětným
expandováním kontrahovaných vrcholů, je ${\rm MST}(G)$. Pokud kontrakcí vzniknou
smyčky, můžeme je ihned odstraňovat; pokud paralelní hrany, ponecháme z~nich vždy tu nejlehčí.
To nás vede k následujícímu algoritmu:

\s{Algoritmus: MST v rovinných grafech} \cite{mm:mst}
\algo
\:Ke každému vrcholu najdeme nejlevnější incidentní hranu -- dostaneme množinu hran $F \subseteq E$.
\:Graf kontrahujeme podle $F$ následovně:
\::Prohledáme do šířky graf $(V, F)$ a přiřadíme každému vrcholu číslo komponenty, v~níž se nachází.
\::Přečíslujeme hrany v~$G$ podle čísel komponent.
\:Odstraníme násobné hrany:
\::Setřídíme hrany lexikograficky přihrádkovým tříděním (násobné hrany jsou nyní pospolu).
\::Projdeme posloupnost hran a z~každého úseku multihran odstraníme všechny až na nejlevnější hranu.
Také odstraníme smyčky.
\:Pokud stále máme netriviální graf, opakujeme předchozí kroky.
\:Vrátíme jako MST všechny hrany, které se v~průběhu algoritmu dostaly do~$F$.
\endalgo

\s{Časová složitost:}
Označme si $n_i$ a $m_i$ počet vrcholů a hran na~počátku $i$-té iterace.
Každý z~kroků 1--7 trvá $\O(m_i)$, proto i celý cyklus algoritmu trvá $\O(m_i)$.
Počet vrcholů grafu klesá s~každým cyklem exponenciálně: $n_i \leq n / 2^i$.
Na~začátku každého cyklu je graf rovinný (kontrakcí hrany v~rovinném grafu se rovinnost
zachovává) a není to multigraf, takže počet jeho hran je lineární v počtu vrcholů:
$m_i < 3n_i$. Celkovou časovou složitost dostaneme jako součet dob trvání
všech cyklů: $\O(\sum_i m_i) = \O(\sum_i n_i) = \O(n)$.

\h{Minorově uzavřené třídy}

Předchozí algoritmus ve~skutečnosti funguje v~lineárním čase i pro obecnější třídy grafů,
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$), 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í:}
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á,} 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.

\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_2)$ 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ů.
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{Definice:} {\I Hustotou} neprázdného grafu~$G$ nazveme $\varrho(G) = \vert E(G) \vert
/ \vert V(G) \vert$. Hustotou třídy $\varrho({\cal C})$ pak nazveme supremum z~hustot všech
neprázdných grafů ležících v~této třídě.

\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 má konečnou hustotu.

\s{Důsledek:}
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}

Původní Jarníkův algoritmus s~haldou má díky ní složitost $\O(m\log n)$, to zlepšíme použitím
Fibonacciho haldy $H$, do~které si pro každý vrchol sousedící se zatím vybudovaným stromem~$T$
uložíme nejlevnější z~hran vedoucích mezi tímto vrcholem a stromem~$T$. Tyto hrany bude halda
udržovat uspořádané podle vah.

\newcount\algcnt
\s{Algoritmus: Jarníkův algoritmus~\#2 (Fredman, Tarjan \cite{ft:fibonacci})}
\algo
\: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 \<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$.
\:::Pokud už tam nějaká taková hrana je a je-li těžší než $uv$, nahradíme ji
hranou~$uv$ a provedeme \<DecreaseKey>.
\global\algcnt=\itemcount
\endalgo

\>Správnost algoritmu přímo plyne ze~správnosti Jarníkova algoritmu.

\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~\<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)$).

Toto zlepšení je důležitější, než by se mohlo zdát, protože nám pro grafy s~mnoha hranami
(konkrétně pro grafy s~$m=\Omega(n\log n)$) dává lineární algoritmus.

\h{Kombinace Jarníkova a Borůvkova algoritmu}

K~dalšímu zlepšení dojde, když před předchozím algoritmem spustíme $\log\log n$ cyklů Borůvkova
algoritmu s~kontrahováním vrcholů, čímž graf zahustíme.

\s{Algoritmus: Jarníkův algoritmus~\#3 (původ neznámý)}
\algo
\:Provedeme $\log\log n$ cyklů upraveného Borůvkova algoritmu s~kontrahováním hran popsaného výše.
\:Pokračujeme Jarníkovým algoritmem~\#2.
\endalgo

\s{Časová složitost:}
Složitost první části je $\O(m\log\log n)$.
Počet vrcholů se po~první části algoritmu sníží na~$n'\leq n/\log n$ a složitost druhé části bude
tedy nanejvýš $\O(m+n'\log n')=\O(m)$.

\h{Jarníkův algoritmus s~omezením velikosti haldy}

Ještě většího zrychlení dosáhneme, omezíme-li Jarníkovu algoritmu \#2 vhodně
velikost haldy, takže nám nalezne jednotlivé podkostřičky zastavené v~růstu
přetečením haldy. Podle těchto podkostřiček graf následně skontrahujeme
a budeme pokračovat s~mnohem menším grafem.

\s{Algoritmus: Jarníkův algoritmus~\#4 (Fredman, Tarjan \cite{ft:fibonacci})}
\algo
\:Opakujeme, dokud máme netriviální $G$ (s alespoň jednou hranou):
\::$t\leftarrow\vert V(G)\vert$.
\::Zvolíme $k\leftarrow 2^{2m/t}$ (velikost haldy).
\::$T\leftarrow\emptyset$.
\::Opakujeme, dokud existují vrcholy mimo $T$:
\:::Najdeme vrchol $v_0$ mimo $T$.
\:::Spustíme Jarníkův alg. \#2 pro celý graf od $v_0$. Zastavíme ho, pokud:
\global\algcnt=\itemcount
\::::$\vert H\vert\geq k$ (byla překročena velikost haldy) nebo
\::::$H=\emptyset$ (došli sousedé) nebo
\::::do $T$ jsme přidali hranu oboustranně incidentní s~hranami v~$T$ (připojili
jsme novou podkostru k~nějaké už nalezené).
\::Kontrahujeme $G$ podle podkoster nalezených v~$T$.
\endalgo

\s{Pozorování:}
Pokud algoritmus ještě neskončil, je každá z~nalezených podkoster v~$T$ incidentní s~alespoň $k$ hranami
(do toho počítáme i vnitřní hrany vedoucí mezi vrcholy podkostry).
Jak to vypadá pro jednotlivá ukončení:
\numlist\ndotted
\itemcount=\algcnt
\:$\vert H\vert\geq k$ -- všechny hrany v~haldě jsou incidentní s~$T$ a navzájem různé, takže incidentních je dost.
\:$H=\emptyset$ -- nemůže nastat, algoritmus by skončil.
\:Připojím se k~už existující podkostře -- jen ji zvětším.
\endlist

\s{Časová složitost:}
Důsledkem předchozího pozorování je, že počet podkoster v~jednom průchodu je nanejvýš
$2m/k$. Pro $t'$ a $k'$ v následujícím kroku potom platí $t'\leq 2m/k$ a $k'=2^{2m/t'}\geq 2^k$.
Průchodů bude tedy nanejvýš $\log^* n$\foot{$\log^* n$ je inverzní funkce k~\uv{věži
z~mocnin}, čili $\min\{i:\log^{(i)} n<1 \}$, kde $\log^{(i)} n$ je $i$-krát iterovaný
logaritmus.}, protože průchod s~$k>n$ bude už určitě poslední.
Přitom jeden vnější průchod trvá $\O(m+t\log k)$, což je pro $k=2^{2m/t}$
rovno $\O(m)$. Celkově tedy algoritmus poběží v~čase $\O(m\log^{*}n)$.

I~odhad $\log^* n$ je ale příliš hrubý, protože nezačínáme s~haldou velikosti~1, nýbrž
$2^{2m/n}$. Můžeme tedy počet průchodů přesněji omezit funkcí $\beta(m,n)=\min\{i:\log^{(i)}n<m/n\}$
a časovou složitost odhadnout jako $\O(m\beta(m,n))$. To nám dává lineární algoritmus
pro grafy s~$m\geq n\log^{(k)}n$ pro libovolnou konstantu $k$, jelikož $\beta(m,n)$ tehdy vyjde
omezená konstantou.

\h{Další výsledky}

\itemize\ibull
\:$\O(m\alpha(m,n))$, kde $\alpha(m,n)$ je obdoba inverzní
  Ackermannovy funkce definovaná podobně, jako je $\beta(m,n)$ obdobou $\log^*$.
  \cite{chazelle:ackermann}, \cite{pettie:ackermann}
\:$\O({\cal T}(m,n))$, kde ${\cal T}(m,n)$ je hloubka optimálního rozhodovacího stromu
  pro nalezení minimální kostry v~grafech s~patřičným počtem hran a vrcholů
  \cite{pettie:optimal}.
  Jelikož každý deterministický algoritmus založený na~porovnávání vah lze popsat rozhodovacím stromem,
  je tento algoritmus zaručeně optimální. Jen bohužel nevíme, jak optimální stromy vypadají, takže
  je stále otevřeno, zda lze MST nalézt v~lineárním čase. Nicméně tento algoritmus
  pracuje i na~Pointer Machine, pročež víme, že pokud je lineární složitosti možné dosáhnout, není k~tomu
  potřeba výpočetní síla RAMu.\foot{O výpočetních modelech viz příští kapitola.}
\:$\O(m)$ pro grafy s~celočíselnými vahami (na~RAMu) \cite{fw90trans} -- ukážeme v~jedné
  z~následujících kapitol.
\:$\O(m)$, pokud už máme hrany setříděné podle vah: jelikož víme, že záleží jen na~uspořádání,
  můžeme váhy přečíslovat na~$1\ldots m$ a použít předchozí algoritmus.
\:$\O(m)$ průměrně: randomizovaný algoritmus, který pro libovolný vstupní graf doběhne v~očekávaném
  lineárním čase~\cite{karger:randomized}.
\:Na~zjištění, zda je zadaná kostra minimální, stačí $\O(m)$ porovnání \cite{komlos:verify} a dokonce
  lze v~lineárním čase zjistit, která to jsou \cite{king:verify}. Z~toho ostatně vychází předchozí
  randomizovaný algoritmus.
\endlist

\references
\bye
