From a7009df29e20be5774ae8edd7477b23abf47a2f6 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 4 Nov 2011 20:15:16 +0100 Subject: [PATCH] Toky: Prepsana cast o parovani + spousta dalsich dilcich zmen --- 2-toky/2-toky.tex | 120 ++++++++++++++++++++++++++-------------------- 1 file changed, 68 insertions(+), 52 deletions(-) diff --git a/2-toky/2-toky.tex b/2-toky/2-toky.tex index 06259d8..ad59d82 100644 --- a/2-toky/2-toky.tex +++ b/2-toky/2-toky.tex @@ -2,64 +2,68 @@ \prednaska{2}{Toky v sítích}{} -\s{První motivaèní úloha:} {\I Rozvod èajovodu do~v¹ech uèeben.} -\smallskip +\h{Motivaèní úlohy} Pøedstavme si, ¾e~by v~budovì fakulty na~Malé Stranì existoval èajovod, který -by rozvádìl èaj do~ka¾dé uèebny. Znázornìme si to orientovaným grafem, kde by -jeden významný vrchol pøedstavoval èajovar a~druhý uèebnu, ve~které sedíme. -Hrany mezi vrcholy by pøedstavovaly vìtvící se trubky, které mají èaj rozvádìt. -Jak rozvést co nejefektivnìji dostatek èaje do~dané uèebny? +by rozvádìl èaj do~ka¾dé uèebny. Znázornìme si to orientovaným grafem, v~nìm¾ +jeden významný vrchol pøedstavuje èajovar a~druhý uèebnu, ve~které sedíme. +Hrany mezi vrcholy pak pøedstavují vìtvící se trubky, které mají èaj rozvádìt. +Jak dopravit co nejvíce èaje do~dané uèebny? \figure{toky01.eps}{Èajovod}{2in} -\s{Druhá motivaèní úloha:} {\I Pøenos dat.} -\smallskip - Jiným pøíkladem mù¾e být poèítaèová sí» na~pøenos dat, která se sestává z~pøenosových linek spojených pomocí routerù. Data se sice obvykle pøená¹ejí po~paketech, ale to mù¾eme pøi dne¹ních rychlostech pøenosu zanedbat a pova¾ovat data za spojitá. Jak pøená¹et data mezi dvìma poèítaèi v~síti co nejrychleji? +\h{Toky v~sítích} + \s{Definice:} {\I Sí»} je uspoøádaná pìtice $(V,E,z,s,c)$, pro ní¾ platí: \itemize\ibull \:$(V,E)$ je orientovaný graf. \:$c:E\to{\bb R}_{0}^{+}$ je {\I kapacita} hran. \:$z,s \in V$ jsou dva vrcholy grafu, kterým øíkáme {\I zdroj} a~{\I stok} (spotøebiè). -\:Graf je symetrický, tedy $\forall u,v \in V: uv \in E \Leftrightarrow vu \in E$ (tuto podmínku si~mù¾eme zvolit bez~újmy na~obecnosti, nebo» v¾dy mù¾eme do~grafu pøidat hranu, která v~nìm je¹tì nebyla, a~dát jí nulovou kapacitu). -\endlist - -\figure{sit.eps}{Pøíklad sítì. Èísla pøedstavují kapacity jednotlivých hran.}{2.5in} - -\s{Konvence:} Nebude-li hrozit nedorozumìní, budeme hranu z~vrcholu~$u$ do vrcholu~$v$ +\:Graf je symetrický, tedy $\forall u,v \in V: uv \in E \Leftrightarrow vu \in E$\foot{% +Nebude-li hrozit nedorozumìní, budeme hranu z~vrcholu~$u$ do vrcholu~$v$ znaèit $uv$ namísto formálnìj¹ího, ale ménì pøehledného $(u,v)$. Podobnì pro neorientovaný -pí¹eme $uv$ namísto $\{u,v\}$. +pí¹eme $uv$ namísto $\{u,v\}$.} +(tuto podmínku si~mù¾eme zvolit bez~újmy na~obecnosti, nebo» v¾dy mù¾eme +do~grafu pøidat hranu, která v~nìm je¹tì nebyla, a~dát jí nulovou kapacitu). + +\endlist \s{Definice:} {\I Tok} je funkce $f:E \to {\bb R}_{0}^{+}$ taková, ¾e~platí: \numlist{\ndotted} \:Tok po~ka¾dé hranì je omezen její kapacitou: $\forall e \in E : f(e)\le c(e)$. -\:Kirchhoffùv zákon: $$\forall v \in V \setminus \{z,s\}: \sum_{u: uv \in E}{f(uv)}=\sum_{u: vu \in E}{f(vu)}.$$ Neboli pro~ka¾dý vrchol kromì zdroje a~stoku platí, ¾e~to, co do~nìj pøitéká, je stejnì velké jako to, co z~nìj odtéká (\uv{sí» tìsní}). +\:{\I Kirchhoffùv zákon:} +$$\forall v \in V \setminus \{z,s\}: \sum_{u: uv \in E}{f(uv)}=\sum_{u: vu \in E}{f(vu)}.$$ +Neboli pro~ka¾dý vrchol kromì zdroje a~stoku platí, ¾e~to, co do~nìj pøitéká, +je stejnì velké jako to, co z~nìj odtéká (\uv{sí» tìsní}). \endlist +\figure{sit.eps}{Pøíklad sítì. Èísla pøedstavují kapacity jednotlivých hran.}{2.5in} + +%% \figure{tok.eps}{Pøíklad toku. Èísla pøedstavují toky po~hranách, v~závorkách jsou kapacity.}{4in} + \s{Definice:} Pro libovolnou funkci $f:E \to {\bb R}$ se nám bude hodit následující znaèení: \itemize\ibull -\:$f^+(v) = \sum_{u: uv \in E}{f(uv)}$ (celkový pøítok do vrcholu) -\:$f^-(v) = \sum_{u: vu \in E}{f(vu)}$ (celkový odtok) -\:$f^\Delta(v) = f^+(v) - f^-(v)$ (pøebytek ve~vrcholu) +\:$f^+(v) = \sum_{u: uv \in E}{f(uv)}$ (celkový {\I pøítok} do vrcholu) +\:$f^-(v) = \sum_{u: vu \in E}{f(vu)}$ (celkový {\I odtok} z~vrcholu) +\:$f^\Delta(v) = f^+(v) - f^-(v)$ ({\I pøebytek} ve~vrcholu) \endlist \>(Kirchhoffùv zákon pak øíká prostì to, ¾e $f^\Delta(v)=0$ pro v¹echna $v\ne z,s$.) -\figure{tok.eps}{Pøíklad toku. Èísla pøedstavují toky po~hranách, v~závorkách jsou kapacity.}{4in} - \s{Pozorování:} Nìjaký tok v¾dy existuje. V libovolné síti mù¾eme v¾dy zvolit konstantnì nulovou funkci (po~¾ádné hranì nic nepoteèe). To je korektní tok, ale sotva u¾iteèný. Budeme chtít najít tok, který pøepraví co nejvíce tekutiny ze~zdroje do~spotøebièe. \s{Definice:} {\I Velikost toku} $f$ budeme znaèit $\vert f\vert$ a polo¾íme ji -rovnou rozdílu souètu velikostí toku na~hranách vedoucích do~$s$ a~souètu velikostí -toku na~hranách vedoucích z~$s$. Neboli $\vert f\vert:=f^\Delta(s).$ +rovnu souètu velikostí toku na hranách vedoucích do spotøebièe minus souèet +velikostí tokù na~hranách ze~spotøebièe ven. V~na¹í terminologii je to tedy +pøebytek ve~spotøebièi: $\vert f\vert:=f^\Delta(s).$ \s{Pozorování:} Jeliko¾ sí» tìsní, mìlo by být jedno, zda velikost toku mìøíme u~spotøebièe nebo u~zdroje. Vskutku, krátkým výpoètem ovìøíme, ¾e tomu tak je: @@ -241,33 +245,45 @@ To, e,f \in F : e \cap f = \emptyset$. {\I Velikostí} párování myslíme poèet jeho hran. -\s{Øe¹ení:} -Mìjme bipartitní graf $G = (V,E)$. V~nìm hledáme nejvìt¹í párování. Sestrojme -si~sí» takovou, ¾e~vezmeme vrcholy $V$ grafu $G$ a~pøidáme k~nim dva speciální -vrcholy $z$ (zdroj) a~$s$ (stok) a~ze~zdroje pøidáme hrany do~v¹ech vrcholù -levé partity a~ze~v¹ech vrcholù pravé partity povedeme hrany do~stoku. V¹echny -kapacity nastavme na~1. Hrany bipartitního grafu zorientujme z levé partity do -pravé. Nyní staèí jen na~tuto sí» spustit Fordùv-Fulkersonùv algoritmus (nebo -libovolný jiný algoritmus, který najde maximální celoèíselný tok) a~a¾~dobìhne, -tak prohlásit hrany s~tokem 1 za~maximální párování. - -\figure{toky04.eps}{Hledání maximálního párování v~bipartitním grafu.}{2in} - -Existuje toti¾ bijekce mezi párováním a~celoèíselnými toky, je¾ zachovává -velikost. Z ka¾dého celoèíselného toku na~vý¹e zmínìném grafu (viz obrázek) lze sestrojit -párování o~stejné velikosti (velikost toku zde odpovídá poètu hran bipartitního -grafu, po~kterých poteèe 1) a~naopak. Dùle¾ité je uvìdomit si, ¾e~definice toku -(omezení toku kapacitou a~Kirchhoffovy zákony) nám zaruèují, ¾e~hrany -s~nenulovým tokem (tedy jednièkovým) budou tvoøit párování (nestane se, ¾e~by -dvì hrany zaèínaly nebo konèily ve~stejném vrcholu, nebo» by se~nutnì poru¹ila -jedna ze~dvou podmínek definice toku). Potom i~maximální tok bude odpovídat -maximálnímu párování a~naopak. - -V~bipartitním grafu najdeme maximální párování v~èase $\O(n \cdot (m+n))$. -Fordùv-Fulkersonùv algoritmus stráví jednou iterací èas $\O(m+n)$ -(za~prohledání do~¹íøky) a~pøi~jednotkových kapacitách bude iterací -nejvý¹e~$n$, proto¾e ka¾dou se~tok zvìt¹í alespoò o~1 a v¹echny toky jsou -omezené øezem kolem zdroje, který má kapacitu nejvý¹e~$n$. Výsledná èasová -slo¾itost hledání maximálního párování bude tedy $\O(n \cdot (m+n))$. +Chceme-li v~daném bipartitním grafu $(V,E)$ nalézt nejmen¹í párování, +pøetvoøíme jej nejprve na sí» $(V',E',c,z,s)$ takto: + +\itemize\ibull +\:Nalezneme partity grafu, budeme jim øíkat {\I levá} a {\I pravá.} +\:Pøidáme zdroj~$z$ a vedeme z~nìj hrany do v¹ech vrcholù levé partity. +\:Pøidáme spotøebiè~$s$ a vedeme do nìj hrany ze~v¹ech vrcholù pravé partity. +\:Hrany zadaného grafu zorientujeme zleva doprava. +\:V¹em hranám nastavíme jednotkovou kapacitu. +\endlist + +\figure{toky04.eps}{Hledání nejvìt¹ího párování v~bipartitním grafu.}{2in} + +\>Nyní v~této síti najdeme maximální celoèíselný tok. Jeliko¾ v¹echny hrany +mají kapacitu~1, musí po ka¾dé hranì téci buï~0 nebo~1. Do~výsledného párování +dáme právì ty hrany pùvodního grafu, po~kterých teèe~1. + +Dostaneme opravdu párování? Kdybychom nedostali, znamenalo by to, ¾e nìjaké +dvì hrany mají spoleèný vrchol. Ov¹em kdyby se setkaly ve~vrcholu v~pravé +partitì, pøitekly by do tohoto vrcholu alespoò 2 jednotky toku a ty by nemìly +kam odtéci. Analogicky pokud by se setkaly nalevo, musely by z~vrcholu odtéci +alespoò 2 jednotky, ale ty se tam nemají kudy dostat. + +Zbývá nahlédnout, ¾e párování je nejvìt¹í mo¾né. K~tomu si staèí v¹imnout, +¾e z~toku vytvoøíme párování o~tolika hranách, kolik je velikost toku, a naopak +z~ka¾dého párování umíme vytvoøit celoèíselný tok odpovídající velikosti. +Jinými slovy nalezli jsme bijekci mezi mno¾inou v¹ech celoèíselných tokù +a mno¾inou v¹ech párování a tato bijekce zachovává velikost. Nejvìt¹í +tok tedy musí odpovídat nejvìt¹ímu párování. + +Snadno tak získáme následující vìtu: + +\s{Vìta:} Nejvìt¹í párování v~bipartitním grafu lze nalézt v~èase $\O(mn)$. + +\proof +Pøedvedená konstrukce vytvoøí z~grafu sí» o~$n'=n+2$ vrcholech a~$m'=m+2n$ +hranách a spotøebuje na to èas $\O(m'+n')$. Pak nalezneme maximální celoèíselný +tok Fordovým-Fulkersonovým algoritmem, co¾ trvá $\O(m'n')$. Nakonec tok v~lineárním +èase pøelo¾íme na~párování. V¹e dohromady trvá $\O(m'n') = \O(mn)$. +\qed \bye -- 2.39.2