From 8b84a28ab001d2a4fdd3c87f2683498c0bcb0894 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 24 May 2011 14:41:02 +0200 Subject: [PATCH] Kostry: Korektury od Paliho --- 7-kostry/7-kostry.tex | 49 +++++++++++++++++++------------------------ 1 file changed, 21 insertions(+), 28 deletions(-) diff --git a/7-kostry/7-kostry.tex b/7-kostry/7-kostry.tex index c3105ae..eb3cadd 100644 --- a/7-kostry/7-kostry.tex +++ b/7-kostry/7-kostry.tex @@ -1,6 +1,6 @@ \input lecnotes.tex -\prednaska{8}{Problém minimální (nejkrat¹í) kostry}{} +\prednaska{8}{Problém minimální kostry}{} \s{Zadání úlohy:} Pro neorientovaný graf $G$ s~ohodnocením hran {\I váhami} $w: E(G) \rightarrow \bb R$, chceme najít kostru $T$ s minimálním ohodnocením $w(T):=\sum_{e\in E(T)} w(e)$. @@ -8,7 +8,7 @@ chceme naj \s{Navíc pøedpokládáme:} (bez újmy na~obecnosti) \itemize\ibull \:Graf $G$ je souvislý (jinak ho nejprve rozlo¾íme na komponenty). -\:$\forall e,f \in E(G$) : $e\neq f \Rightarrow w(e)\neq w(f)$ ($w$ je prostá). +\:Váhy hran jsou navzájem rùzné \endlist Nyní si uká¾eme tøi algoritmy pro hledání minimální kostry, konkrétnì se jedná @@ -36,21 +36,22 @@ Vydan 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: {\narrower +\smallskip \s{Definice:} {\I Øez} v~grafu $G=(V,E)$ je mno¾ina hran $F\subseteq E$ taková, ¾e $\exists A\subset V$ : $F=\left\{\left\{u,v\right\}\in E:u\in A, v\notin A \right\}$. -\s{Lemma (øezové):} Pokud $G$ je graf, $w$ jeho prosté ohodnocení, $F$ je øez v -grafu $G$ a $f$ je nejlehèí hrana v øezu $F$, pak pro ka¾dou minimální kostru -$T$ grafu $G$ je $f\in E(T)$. +\s{Lemma (øezové):} Pokud $G$ je graf, $w$ jeho prosté ohodnocení, $F$ je øez v~grafu $G$ a $f$ +je nejlehèí hrana v øezu $F$, pak pro ka¾dou minimální kostru~$T$ grafu $G$ je $f\in E(T)$. \proof -Buï $T$ kostra a $f=uv\notin E(T)$. Pak existuje cesta $P\subseteq T$ spojující $u$ a $v$. +Sporem: Buï $T$ kostra a $f=uv\notin E(T)$. Pak existuje cesta $P\subseteq T$ spojující $u$ a $v$. 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$. Tento graf je rovnì¾ kostra grafu $G$, proto¾e odebraním hrany $e$ se graf rozpadne na dvì komponenty a pøidáním -hrany $f$ se tyto komponenty opìt spojí. Navíc $w(T')=w(T)-w(e)+w(f)V~dùkazu korektnosti Jarníkova algoritmu toto lemma vyu¾ijeme tak, ¾e si v¹imneme, ¾e hrany mezi @@ -62,7 +63,7 @@ mus \s{Dùsledky:} Graf $G$ s prostým ohodnocením má pravì jednu minimální kostru. Minimální kostra je -jednoznaènì urèená lineárním uspoøádáním hran. +jednoznaènì urèená lineárním uspoøádáním hran podle vah (na~konkrétních hodnotách vah nezále¾í). \s{Implementace:} \itemize\ibull @@ -71,7 +72,7 @@ jednozna 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 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ì zlep¹íme na~$\O(n^2+m)=\O(n^2)$. -\:S pou¾itím haldy: $D(v)$ ukladáme do haldy. Potom provedeme nanejvý¹ $n$ krát ExtractMin, nanejvý¹ $n$ krát Insert a nanejvý¹ $m$ krát Decrease. Pro binární haldu to má èasovú slo¾itos» $\O(m \log(n))$. +\: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ý Dijkstrovu algoritmu pro nejkrat¹í cesty. Rozbor slo¾itosti pro rùzné typy hald proto také dopadne stejnì. \endlist \h{Borùvkùv algoritmus} @@ -87,21 +88,20 @@ zlep \algout Minimální kostra~$F$. \endalgo -\s{Vìta:} Borùvkùv algoritmus se zastaví po $\left\lceil \log_2 n\right\rceil$ iteracích a vydá minimální kostru grafu $G$. +\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$. \proof V¹imnìme si nejprve, ¾e po~$k$ iteracích mají v¹echny komponenty grafu~$F$ minimálnì $2^k$ vrcholù. -indukcí -- na~poèátku jsou v¹echny komponenty jednovrcholové, v~ka¾dé dal¹í iteraci se komponenty sluèují do~vìt¹ích, +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, ka¾dá s~alespoò jednou sousední, tak¾e se velikosti komponent minimálnì zdvojnásobí. -Proto nejpozdìji po~$\left\lceil \log_2 n\right\rceil$ iteracích u¾~velikost komponenty dosáhne poètu v¹ech vrcholù a algoritmus -se zastaví. +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. Hrany mezi ka¾dou komponentou a~zbytkem grafu tvoøí øez, tak¾e podle øezového lemmatu v¹echny hrany pøidané do~$F$ musí být souèástí (jednoznaènì urèené) minimální kostry. Graf $F\subseteq G$ je tedy v¾dy les a a¾ se -algoritmus zastaví, bude roven minimální kostøe. +algoritmus zastaví, bude tento les roven minimální kostøe. \qed \s{Implementace:} @@ -109,7 +109,7 @@ algoritmus zastav \:Inicializace pøímoèará. \:Pomocí DFS rozlo¾íme les na komponenty. Pro ka¾dý vrchol si pamatujeme èíslo komponenty. \:Pro ka¾dou hranu zjistíme, do které komponenty patøí, a pro ka¾dou komponentu -si uchováme nejlehèí hranu. +si uchováváme nejlehèí hranu. \endlist \>Takto doká¾eme ka¾dou iteraci provést v~èase $\O(m)$ a celý algoritmus dobìhne v~$\O(m\log n)$. @@ -120,7 +120,7 @@ si uchov \algo \algin Graf~$G$ s~ohodnocením~$w$. -\:Setøídíme v¹echny hrany z $E(G)$ tak, aby: $w(e_1)<...), a~$(n-1)$-krát spojíme @@ -159,13 +159,11 @@ Budeme si pamatovat v~poli vrcholy. \ zvládneme v~èase $\O(1)$, ale \ bude stát $\O(n)$. Celý algoritmus pak pobì¾í v~èase $\O(m\log n+ m + n^2) = \O(m\log n+n^2)$. -\s{Chytøej¹í struktura:} Ka¾dou komponentou si ulo¾íme jako strom orientovaný smìrem ke koøeni --- ka¾dý vrchol si pamatuje svého otce, navíc ka¾dý koøen si pamatuje velikost -komponenty. -%Hloubku podstromu? Zaøazujeme mìlèí pod hlub¹í, ne nutnì men¹í pod vìt¹í. -%Myslím, ¾e s hloubkami to funguje lépe, ovìøit. +\s{Chytøej¹í struktura:} Ka¾dou komponentu si ulo¾íme jako strom orientovaný smìrem ke koøeni +-- ka¾dý vrchol si pamatuje svého otce, navíc ka¾dý koøen si pamatuje hloubku stromu. Operace \ vystoupá z~obou vrcholù ke~koøeni a koøeny porovná. \ -rovnì¾ najde koøeny a pøipojí koøen men¹í komponenty pod koøen té vìt¹í. Obojí +rovnì¾ najde koøeny a pøipojí koøen mìlèí komponenty pod koøen té hlub¹í +(pokud jsou obì stejnì hluboké, vybere si libovolnì). Obojí zvládneme v~èase lineárním v~hloubce stromu a jak si uká¾eme, tato hloubka je v¾dy nejvý¹e logaritmická, a proto celý Kruskalùv algoritmus pobì¾í v~èase $\O(m\log n + m\log n + n\log n) = \O(m\log n)$.\foot{% @@ -173,11 +171,6 @@ Drobnou bychom neupotøebili, jeliko¾ by nás stejnì brzdilo tøídìní, a analýza slo¾itosti by byla \dots\ inu, slo¾itìj¹í.} -% V originále je jen "strom hloubky..." a to pøece pro obecný (napø. -% zdegenerovaný) strom neplatí. - -% Mimochodem, zde se u¾ mluví o spojování podle hloubky, tak¾e to nahoøe je asi -% vá¾nì chyba \s{Lemma:} \ strom hloubky $h$ má alespoò $2^h$ prvkù. \proof -- 2.39.2