7-kostry/7-kostry.tex

   1 \input lecnotes.tex
   2
   3 \prednaska{7}{Problém minimální kostry}{}
   4
   5 \s{Zadání úlohy:} Pro neorientovaný graf $G$ s~ohodnocením hran {\I váhami} $w: E(G) \rightarrow \bb R$,
   6 chceme najít kostru $T$ s minimálním ohodnocením $w(T):=\sum_{e\in E(T)} w(e)$.
   7
   8 \s{Navíc pøedpokládáme:} (bez újmy na~obecnosti)
   9 \itemize\ibull
  10 \:Graf $G$ je souvislý (jinak ho nejprve rozlo¾íme na komponenty).
  11 \:Váhy hran jsou navzájem rùzné
  12 \endlist
  13
  14 Nyní si uká¾eme tøi algoritmy pro hledání minimální kostry, konkrétnì se jedná
  15 o~Jarníkùv, Borùvkùv a Kruskalùv algoritmus.
  16
  17 \h{Jarníkùv algoritmus}
  18
  19 \s{Algoritmus:}
  20
  21 \algo
  22 \algin Graf~$G$ s~ohodnocením~$w$.
  23 \:Zvolíme libovolný vrchol $v_0\in V(G)$.
  24 \:$T\leftarrow(\left\{v_0\right\},\emptyset)$ (zatím jednovrcholový strom)
  25 \:Dokud existuji vrcholy mimo $T$:
  26 \::Vybereme hranu $uv\in E(G) : u\in V(T), v\notin V(T)$ tak, aby $w(uv)$ byla minimálni.
  27 \::$T\leftarrow T+uv$.
  28 \algout Minimální kostra~$T$.
  29 \endalgo
  30
  31 \s{Vìta:} Jarníkùv algoritmus se zastaví po maximálnì $n$ iteracích a vydá minimální kostru grafu $G$.
  32
  33 \proof
  34 Pøi ka¾dé iteraci algoritmus pøidá jeden vrchol do~$T$, a~proto se po~maximálnì $n$ iteracích zastaví.
  35 Vydaný graf je strom, proto¾e se stále pøidává list k ji¾ existujícímu stromu, a~jeliko¾ má $n$~vrcholù,
  36 je to kostra. Zbývá nám u¾ jen dokázat, ¾e nalezená kostra je minimální. K~tomu pomu¾e následující lemma:
  37
  38 {\narrower
  39 \smallskip
  40
  41 \s{Definice:} {\I Øez} v~grafu $G=(V,E)$ je mno¾ina hran $F\subseteq E$ taková, ¾e $\exists A\subset V$ :
  42 $F=\left\{\left\{u,v\right\}\in E:u\in A, v\notin A \right\}$.
  43
  44 \s{Lemma (øezové):} Pokud $G$ je graf, $w$ jeho prosté ohodnocení, $F$ je øez v~grafu $G$ a $f$
  45 je nejlehèí hrana v øezu $F$, pak pro ka¾dou minimální kostru~$T$ grafu $G$ je $f\in E(T)$.
  46
  47 \proof
  48 Sporem: Buï $T$ kostra a $f=uv\notin E(T)$. Pak existuje cesta $P\subseteq T$ spojující $u$ a $v$.
  49 Cesta musí øez alespoò jednou pøekroèit. Proto existuje $e\in P \cap F$ a navíc víme, ¾e $w(e) > w(f)$. Uva¾me $T'=T-e+f$.
  50 Tento graf je rovnì¾ kostra grafu $G$, proto¾e odebraním hrany $e$ se graf rozpadne na dvì komponenty a pøidáním
  51 hrany $f$ se tyto komponenty opìt spojí. Navíc $w(T')=w(T)-w(e)+w(f)<w(T)$, co¾ je spor s minimalitou~$F$.
  52 \qed
  53
  54 \smallskip
  55 }
  56
  57 \>V~dùkazu korektnosti Jarníkova algoritmu toto lemma vyu¾ijeme tak, ¾e si v¹imneme, ¾e hrany mezi
  58 vrcholy stromu~$T$ a zbytkem grafu tvoøí øez a algoritmus nejlehèí hranu tohoto øezu pøidá
  59 do~$T$. Podle lemmatu tedy v¹echny hrany~$T$ musí být souèástí ka¾dé minimální kostry a jeliko¾~$T$ je strom,
  60 musí být minimální kostrou.
  61
  62 \qed
  63
  64
  65 \s{Dùsledky:} Graf $G$ s prostým ohodnocením má pravì jednu minimální kostru. Minimální kostra je
  66 jednoznaènì urèená lineárním uspoøádáním hran podle vah (na~konkrétních hodnotách vah nezále¾í).
  67
  68 \s{Implementace:}
  69 \itemize\ibull
  70 \:Pøímoèará: pamatujeme si, které vrcholy a hrany jsou v kostøe $T$ a které ne. Èasová slo¾itost je $\O(nm)$.
  71 \:Chytøej¹í: Pro ka¾dý vrchol $v\notin V(T)$ si pamatujeme $$D(v)=\min\left\{w(uv):u\in T\right\},$$
  72 tedy nejlehèí hranu, která vede mezi~$T$ a~$v$. Pøi ka¾dém
  73 prùchodu hlavním cyklem pak procházíme v¹echna~$D(v)$ (to v¾dy trvá $\O(n)$) a pøi pøidání vrcholu do~$T$ kontrolujeme
  74 okolní~$D(w)$ pro $vw\in E$ a pøípadnì je sni¾ujeme (za~ka¾dou hranu~$\O(1)$). Èasovou slo¾itost tím celkovì
  75 zlep¹íme na~$\O(n^2+m)=\O(n^2)$.
  76 \:S pou¾itím haldy: $D(v)$ ukládáme do haldy. Potom provedeme nanejvý¹ $n$-krát {\I ExtractMin}, nanejvý¹ $n$-krát {\I Insert} a nanejvý¹ $m$-krát {\I Decrease}. Pro binární haldu to má èasovou slo¾itost $\O(m \log n)$. V¹imnìte si, ¾e Jarníkùv algoritmus s $D(v)$ je velmi podobný Dijk\-stro\-vu algoritmu pro nejkrat¹í cesty. Rozbor slo¾itosti pro rùzné typy hald proto také dopadne stejnì.
  77 \endlist
  78
  79 \h{Borùvkùv algoritmus}
  80
  81 \s{Algoritmus:}
  82
  83 \algo
  84 \algin Graf~$G$ s~ohodnocením~$w$.
  85 \:$F\leftarrow(V(G),\emptyset)$
  86 \:Dokud $F$ má alespoò dvì komponenty ($F$ není souvislý):
  87 \::Pro ka¾dou komponentu $F_i$ lesa $F$ vybereme nejlehèí incidentní hranu $e_i$.
  88 \::V¹echny hrany $e_i$ pøidáme do $F$.
  89 \algout Minimální kostra~$F$.
  90 \endalgo
  91
  92 \s{Vìta:} Borùvkùv algoritmus se zastaví po $\left\lfloor \log_2 n\right\rfloor$ iteracích a vydá minimální kostru grafu $G$.
  93
  94 \proof
  95 V¹imnìme si nejprve, ¾e po~$k$ iteracích mají v¹echny komponenty grafu~$F$ minimálnì $2^k$ vrcholù.
  96
  97 To nahlédneme indukcí -- na~poèátku jsou v¹echny komponenty jednovrcholové, v~ka¾dé dal¹í iteraci se komponenty sluèují do~vìt¹ích,
  98 ka¾dá s~alespoò jednou sousední, tak¾e se velikosti komponent minimálnì zdvojnásobí.
  99
 100 Proto nejpozdìji po~$\left\lfloor \log_2 n\right\rfloor$ iteracích u¾~velikost ka¾dé komponenty dosáhne poètu v¹ech vrcholù a algoritmus se zastaví, tak¾e komponenta mù¾e být jen jedna.
 101
 102 Hrany mezi ka¾dou komponentou a~zbytkem grafu tvoøí øez, tak¾e podle øezového
 103 lemmatu v¹echny hrany pøidané do~$F$ musí být souèástí (jednoznaènì
 104 urèené) minimální kostry. Graf $F\subseteq G$ je tedy v¾dy les a a¾ se
 105 algoritmus zastaví, bude tento les roven minimální kostøe.
 106 \qed
 107
 108 \s{Implementace:}
 109 \itemize\ibull
 110 \:Inicializace pøímoèará.
 111 \:Pomocí DFS rozlo¾íme les na komponenty. Pro ka¾dý vrchol si pamatujeme èíslo komponenty.
 112 \:Pro ka¾dou hranu zjistíme, do které komponenty patøí, a pro ka¾dou komponentu
 113 si uchováváme nejlehèí hranu.
 114 \endlist
 115
 116 \>Takto doká¾eme ka¾dou iteraci provést v~èase $\O(m)$ a celý algoritmus dobìhne v~$\O(m\log n)$.
 117
 118 \h{Kruskalùv neboli hladový algoritmus}
 119
 120 \s{Algoritmus:}
 121
 122 \algo
 123 \algin Graf~$G$ s~ohodnocením~$w$.
 124 \:Setøídíme v¹echny hrany z $E(G)$ tak, aby platilo $w(e_1)<...<w(e_m)$.
 125 \:$F\leftarrow (V(G),\emptyset)$.
 126 \:Pro $i=1$ do $m$:
 127 \::Pokud $F+e_i$ je acyklický, provedeme $F\leftarrow F+e_i$.
 128 \algout Minimální kostra~$F$.
 129 \endalgo
 130
 131 \s{Vìta:} Kruskalùv algoritmus se zastaví po~$m$ iteracích a vydá minimální kostru.
 132
 133 \proof
 134 Ka¾dá iterace algoritmu zpracovává jednu hranu, tak¾e iterací je~$m$. Indukcí doká¾eme,
 135 ¾e~$F$ je v¾dy podgrafem minimální kostry: prázdné poèáteèní~$F$ je podgrafem èehokoliv,
 136 ka¾dá hrana, kterou pak pøidáme, je minimální v~øezu oddìlujícím nìjakou
 137 komponentu~$F$ od~zbytku grafu (ostatní hrany tohoto øezu je¹tì nebyly
 138 zpracovány, a~tudí¾ jsou tì¾¹í). Naopak ¾ádná hrana, kterou jsme se rozhodli
 139 do~$F$ nepøidat, nemù¾e být souèástí minimální kostry, jeliko¾ s~hranami,
 140 o~kterých ji¾ víme, ¾e v~minimální kostøe le¾í, tvoøí kru¾nici. \qed
 141
 142 % Toto jsme na pøedná¹ce dìlali sporem a mì se to líbí více, ale oba dùkazy
 143 % urèitì fungují.
 144
 145 \s{Implementace:}
 146 \itemize\ibull
 147 \:Setøídìní v èase $\O(m\log m)=\O(m\log n)$.
 148 \:Potøebujeme udr¾ovat komponenty souvislosti grafu~$F$, abychom umìli rychle
 149   urèit, jestli právì zpracovávaná hrana vytvoøí kru¾nici. Potøebujeme tedy strukturu
 150   pro udr¾ování komponent souvislosti, které se $m$-krát zeptáme, zda dva vrcholy
 151   le¾í v~té¾e komponentì (tomu budeme øíkat operace \<Find>), a~$(n-1)$-krát spojíme
 152   dvì komponenty do jedné (\<Union>).
 153 \endlist
 154
 155 \>Kruskalùv algoritmus tedy pobì¾í v~èase $\O(m\log n + mT_f + nT_u)$, kde~$T_u$ je
 156 èas na~provedení jedné operace \<Union> a $T_f$ na~operaci \<Find>.
 157
 158 \s{Jednoduchá struktura pro komponenty:}
 159 Budeme si pamatovat v~poli èísla komponent, ve~kterých le¾í jednotlivé
 160 vrcholy. \<Find> zvládneme v~èase $\O(1)$, ale \<Union> bude stát $\O(n)$. Celý
 161 algoritmus pak pobì¾í v~èase $\O(m\log n+ m + n^2) = \O(m\log n+n^2)$.
 162
 163 \s{Chytøej¹í struktura:} Ka¾dou komponentu si ulo¾íme jako strom orientovaný smìrem ke koøeni
 164 -- ka¾dý vrchol si pamatuje svého otce, navíc ka¾dý koøen si pamatuje hloubku stromu.
 165 Operace \<Find> vystoupá z~obou vrcholù ke~koøeni a koøeny porovná. \<Union>
 166 rovnì¾ najde koøeny a pøipojí koøen mìlèí komponenty pod koøen té hlub¹í
 167 (pokud jsou obì stejnì hluboké, vybere si libovolnì). Obojí
 168 zvládneme v~èase lineárním v~hloubce stromu a jak si uká¾eme, tato hloubka je
 169 v¾dy nejvý¹e logaritmická, a proto celý Kruskalùv algoritmus pobì¾í v~èase
 170 $\O(m\log n + m\log n + n\log n) = \O(m\log n)$.\foot{%
 171 Drobnou úpravou bychom mohli dosáhnout daleko efektivnìj¹í struktury, ale tu
 172 bychom neupotøebili,
 173 jeliko¾ by nás stejnì brzdilo tøídìní, a analýza slo¾itosti by byla \dots\ inu, slo¾itìj¹í.}
 174
 175 \s{Lemma:} \<Union-Find> strom hloubky $h$ má alespoò $2^h$ prvkù.
 176
 177 \proof
 178 Indukcí: Pokud \<Union> spojí strom s~hloubkou $h$ s jiným s~hloubkou men¹í ne¾ $h$, pak hloubka výsledného
 179 stromu zùstává~$h$. Pokud spojuje dva stromy stejné hloubky~$h$, pak má výsledný strom hloubku $h+1$.
 180 Z~indukèního pøedpokladu víme, ¾e strom hloubky $h$ má minimálnì $2^h$ vrcholù,
 181 a~tedy výsledný strom hloubky $h+1$ má alespoò $2^{h+1}$ vrcholù. \qed
 182
 183 % Union-find je jsme mìli na pøedná¹ce detailnìji rozebraný (i s pseudokódem),
 184 % není to nutnost, ale mù¾u ho klidnì rozepsat trochu výøeènìji, aby mìl ètenáø
 185 % vìt¹í jistotu. Zále¾í na tobì.
 186
 187 \bye