From 182c773e9123036973eb35abb64a4f2634c8dd36 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 22 May 2011 14:09:45 +0200 Subject: [PATCH] Kostry: prvni verze zapisku od Paliho --- .../6-kostry.tex => 7-kostry/7-kostry.tex | 31 ++++++++++--------- {2009/6-kostry => 7-kostry}/Makefile | 2 +- 2 files changed, 17 insertions(+), 16 deletions(-) rename 2009/6-kostry/6-kostry.tex => 7-kostry/7-kostry.tex (89%) rename {2009/6-kostry => 7-kostry}/Makefile (66%) diff --git a/2009/6-kostry/6-kostry.tex b/7-kostry/7-kostry.tex similarity index 89% rename from 2009/6-kostry/6-kostry.tex rename to 7-kostry/7-kostry.tex index 3c1a111..c3105ae 100644 --- a/2009/6-kostry/6-kostry.tex +++ b/7-kostry/7-kostry.tex @@ -1,14 +1,14 @@ \input lecnotes.tex -\prednaska{6}{Problém minimální kostry}{} +\prednaska{8}{Problém minimální (nejkrat¹í) 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)$. +chceme najít kostru $T$ s minimálním ohodnocením $w(T):=\sum_{e\in E(T)} w(e)$. \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)$. +\:$\forall e,f \in E(G$) : $e\neq f \Rightarrow w(e)\neq w(f)$ ($w$ je prostá). \endlist Nyní si uká¾eme tøi algoritmy pro hledání minimální kostry, konkrétnì se jedná @@ -22,7 +22,7 @@ o~Jarn \algin Graf~$G$ s~ohodnocením~$w$. \:Zvolíme libovolný vrchol $v_0\in V(G)$. \:$T\leftarrow(\left\{v_0\right\},\emptyset)$ (zatím jednovrcholový strom) -\:Dokud $\vert V(T) \vert \neq n$: +\:Dokud existuji vrcholy mimo $T$: \::Vybereme hranu $uv\in E(G) : u\in V(T), v\notin V(T)$ tak, aby $w(uv)$ byla minimálni. \::$T\leftarrow T+uv$. \algout Minimální kostra~$T$. @@ -37,8 +37,8 @@ je to kostra. Zb {\narrower -\s{Definice:} {\I Øez} v~grafu $G=(V,E)$ je mno¾ina hran $F\subseteq E$ taková, ¾e $\exists U\subset V$ : -$F=\left\{uv\in E:u\in U, v\notin U \right\}$. +\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 @@ -71,7 +71,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)$. -\:Také se dá pou¾ít halda pro uchovávání hran nebo hodnot~$D(v)$. +\: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))$. \endlist \h{Borùvkùv algoritmus} @@ -81,19 +81,20 @@ zlep \algo \algin Graf~$G$ s~ohodnocením~$w$. \:$F\leftarrow(V(G),\emptyset)$ -\:Dokud $F$ má alespoò dvì komponenty: -\::Pro ka¾dou komponentu $T_i$ grafu $F$ vybereme nejlehèí incidentní hranu $t_i$. -\::V¹echny hrany $t_i$ pøidáme do $F$. +\:Dokud $F$ má alespoò dvì komponenty ($F$ není souvislý): +\::Pro ka¾dou komponentu $F_i$ lesa $F$ vybereme nejlehèí incidentní hranu $e_i$. +\::V¹echny hrany $e_i$ pøidáme do $F$. \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$. \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, -ka¾dá s~alespoò jednou sousední, tak¾e se velikosti komponent minimálnì zdvojnásobí). +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, +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í. @@ -160,7 +161,7 @@ algoritmus pak pob \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. +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. Operace \ vystoupá z~obou vrcholù ke~koøeni a koøeny porovná. \ diff --git a/2009/6-kostry/Makefile b/7-kostry/Makefile similarity index 66% rename from 2009/6-kostry/Makefile rename to 7-kostry/Makefile index b86ea6f..31a6fd7 100644 --- a/2009/6-kostry/Makefile +++ b/7-kostry/Makefile @@ -1,3 +1,3 @@ -P=6-kostry +P=7-kostry include ../Makerules -- 2.39.2