2007/3-dinic/3-dinic.tex

   1 \input lecnotes.tex
   2
   3 \prednaska{3}{Dinicùv algoritmus}{(zapsali Jakub Melka, Petr Musil)\foot{\rm s~díky Bernardovi Lidickému za obrázky}}
   4
   5 Na~minulé pøedná¹ce jsme si ukázali {\I Fordùv-Fulkersonùv} algoritmus. Víme o~nìm, ¾e kdy¾ se zastaví, tak vydá maximální tok. Jen¾e zastavit se nemusí (napøíklad pro~sítì s~reálnými kapacitami), nebo trvá pøíli¹ dlouho.
   6 Uká¾eme si lep¹í algoritmus, {\I Dinicùv}, který má výraznì men¹í slo¾itost a zastaví se v¾dy.
   7
   8
   9 Idea je následující: v~algoritmu budeme pou¾ívat {\I sí» rezerv}, která bude obsahovat rezervy -- kolik je¹tì po~dané hranì mù¾eme pustit, aby to nepøekroèilo její kapacitu.
  10 Sí» rezerv pak budeme vyu¾ívat k~vylep¹ování toku.
  11
  12 \s{Definice:} {\I Sí» rezerv }$R$ k síti $S=(V,E,z,s,c)$ a toku $f$ v $S$ je  sí» $R=(V,E\cup\overleftarrow{E}, z,s, r)$, pro $\forall e\in E$:
  13 \itemize\ibull
  14 \:$r(e)=c(e)-f(e)$,
  15 \:$r(\overleftarrow{e})=f(e)$,
  16 \endlist
  17 \>kde hrana $\overleftarrow{e}$ vznikne z~hrany $e$ tak, ¾e se zorientuje opaèným smìrem. V pøípadì, ¾e v~síti rezerv u¾ opaènì orientovaná hrana\foot{vznikne tak, ¾e v pùvodní síti jsou dvì opaènì orientované hrany mezi stejnými vrcholy.} je, pak vznikne multigraf\foot{graf, který mù¾e mít mezi dvìma vrcholy více stejnì orientovaných hran.} s~multiplicitou maximálnì dva.
  18
  19
  20 \>Sí» rezerv budeme pou¾ívat v~algoritmu k~hledání vylep¹ujících tokù. K~tomu nám bude slou¾it následující vìta:
  21
  22 \s{Vìta:} Je-li $f$ tok v~síti $S$ a $g$ tok v~pøíslu¹né síti rezerv, pak $\exists$ tok $f'$ v $S$ takový, ¾e $\vert f'\vert = \vert f\vert + \vert g\vert$, co¾ znamená $\forall e \in E : f'(e) = f(e) + g(e) - g(\overleftarrow{e})$.
  23
  24 \proof
  25 Rozebereme si jednotlivé pøípady pro~$\forall e\in E$:
  26 \numlist\nalpha
  27 \:$g(e)=g(\overleftarrow{e})=0 \Rightarrow f'(e)=f(e) $.
  28 \:$g(e)>0$ a zároveò $g(\overleftarrow{e})=0\Rightarrow f'(e) = f(e) + g(e)$.
  29 \:$g(e)=0$ a zároveò $g(\overleftarrow{e})>0\Rightarrow f'(e) = f(e) - g(\overleftarrow{e})$.
  30 \:Nastává cirkulace, tu snadno odstraníme: odeèteme $\varepsilon$ od obou hran $e$ a $\overleftarrow{e}$,
  31 kde $\varepsilon=\min( g(e), g(\overleftarrow{e})  )$. Pøevedeme tím tento pøípad na jeden ze tøí uvedených vý¹e.
  32 \endlist
  33
  34 Je v¹ak $f'$ tok? Víme, ¾e $f'$ urèitì nemù¾e klesnout pod nulu, proto¾e se odeèítá jen v pøípadì c), a tam je z~definice vidìt, ¾e $f'$ pod nulu klesnout nemù¾e. Kapacita také nemù¾e
  35 být pøekroèena, pøièítá se jen v~pøípadì b) a z~definice se nepokazí, proto¾e $g(e)=c(e)-f(e)$, tedy v~nejhor¹ím pøípadì $f'(e) = c(e)$.
  36
  37 Dále doká¾eme, ¾e $f'$ dodr¾uje Kirchhoffùv zákon. V~následujících sumách pøedpokládejme, ¾e v¹echny vrcholy jsou rozdílné od~zdroje a stoku. Musí platit, ¾e:
  38 $$\sum\limits_{ab \in E} f'(ab) = \sum\limits_{ba \in E} f'(ba).$$
  39 Rozepí¹eme si tuto rovnici dle definice:
  40 $$\sum\limits_{ab \in E} f'(ab) - \sum\limits_{ba \in E} f'(ba) = 0,$$
  41 $$\sum\limits_{uv\in E}(f(uv)+g(uv)-g(\overleftarrow{uv})) - \sum\limits_{vu\in E}(f(vu)+g(vu)-g(\overleftarrow{vu})) = 0.$$
  42 Roztrhneme si to na ètyøi sumy a dostaneme:
  43 $$\underbrace{\sum\limits_{uv\in E}f(uv)-\sum\limits_{vu\in E}f(vu)}\limits_0+$$
  44 $$+\underbrace{\sum\limits_{uv\in E}g(uv)-g(\overleftarrow{uv})-\sum\limits_{vu\in E}g(vu)-g(\overleftarrow{vu})}\limits_0 = 0,$$
  45 nebo» $f$ i $g$ jsou toky a musí splòovat Kirchhoffùv zákon.
  46 \qed
  47
  48 Tato vìta nám øíká, ¾e pokud existuje nenulový tok v~síti rezerv, pak lze tok v~pùvodní síti je¹tì zvìt¹it. Naopak pokud takový tok neexistuje, je tok v~pùvodní síti maximální.
  49
  50
  51 \s{Definice:} $f$ je {\I blokující tok}, pokud na~ka¾dé orientované cestì $P$ ze~zdroje do~spotøebièe $\exists e\in P : f(e)=c(e)$.
  52
  53 \s{Definice:} $C$ je {\I proèi¹tìná sí»}, pokud obsahuje pouze vrcholy a hrany na~nejkrat¹ích $z\rightarrow s$ cestách. Proèi¹tìná sí» nemá slepé ulièky, ani hrany vedoucí ze~stoku nìkam do~dal¹ího vrcholu.
  54
  55 \figure{dinic-cistasit.eps}{Pøíklad proèi¹tìné sítì}{0.5\hsize}
  56
  57 \s{Algoritmus (hledání maximálního toku v síti, Dinicùv)}
  58
  59 \algo
  60 \:$f\leftarrow$ nulový tok.
  61 \:Sestrojíme sí» rezerv $R$, vynecháme hrany s nulovou rezervou.
  62 \:$l\leftarrow$ délka nejkrat¹í cesty $z\rightarrow s$ v~$R$.
  63 \:Kdy¾ $l=\infty$, tak skonèíme.
  64 \:Sestrojíme proèi¹tìnou sí» $C$, a to následujícím zpùsobem:%\foot{Ponecháme vrcholy a hrany z $R$, které le¾í na nejkrat¹ích $z\rightarrow s$ cestách}
  65 \::Spustíme BFS\foot{Breadth-First Search, standardní prohledávání do ¹íøky.} algoritmus ze zdroje.
  66 \::BFS nám rozdìlí uzly do vrstev, vyhodíme hrany za spotøebièem a slepé ulièky.
  67 \:$g\leftarrow$ blokující tok v $C$.
  68 \:Zlep¹íme tok $f$ podle $g$ a jdeme na bod 3.
  69 \endalgo
  70
  71 \s{Postup tvorby proèi¹tìné sítì podrobnìji:} Prohledáním do~¹íøky vytvoøíme vrstvy $C_i$, zahodíme ty za~spotøebièem, ponecháme
  72 pouze hrany mezi $C_i$ a $C_{i+1}$. Je¹tì musíme odstranit slepé ulièky -- cesty, které konèí v~$C_m : m < l$, proto¾e ty urèitì nejsou souèástí nejkrat¹í $z\rightarrow s$ cesty.
  73
  74 Proèi¹tìní zvládneme v~lineárním èase $\O(N+M)$, v~pøípadì souvislého grafu pouze $\O(M)$.
  75
  76
  77 \figure{dinic-neprocistenasit.eps}{Pøíklad neproèi¹tìné sítì}{0.5\hsize}
  78
  79 Na obrázku neproèi¹tìné sítì vidíme, co se má smazat. Èerné hrany ponecháme, ty tam jsou správnì. Èervené hrany jsou zpìtné, ty sma¾eme. Modré hrany jsou hrany ve~stejné vrstvì, ty rovnì¾ sma¾eme. Èervené teèkované hrany nevedou vùbec do stoku, tak¾e ty rovnì¾ sma¾eme.
  80
  81 \s{Definice:} {\I Fází} algoritmu oznaèíme jeden bìh cyklu -- kroky 3 a¾ 9.
  82
  83 \>Provedeme podrobnou analýzu algoritmu z~hlediska slo¾itosti a uvidíme, ¾e má slo¾itost $\O(N^2M)$. Nejprve analyzujeme hledání
  84 blokujícího toku, pak se podíváme, kolik fází maximálnì mù¾e Dinicùv algoritmus mít.
  85
  86
  87 \s{Algoritmus hledání blokujícího toku}
  88 \algo
  89 \:$g\leftarrow$ nulový tok.
  90 \:Dokud $\exists z\rightarrow s$ cesta $P$ v proèi¹tìné síti $C$:
  91 \::$\varepsilon \leftarrow \min\limits_{e\in P} (c(e)-f(e)) $.
  92 \::$\forall e \in P :g(e)\leftarrow g(e)+\varepsilon$, pokud $g(e)$ vzroste na $r(e)$, tak sma¾eme hranu $e$.
  93 \::Doèistíme sí» tím, ¾e odstraníme slepé ulièky, které mohly vzniknout smazáním hrany $e$.
  94 \endalgo
  95
  96 Pøi ka¾dém prùchodu se sma¾e v¾dy alespoò jedna hrana, tedy maximálnì $M$-krát provádíme $\O(N)$ -- právì tolik trvá nalezení cesty $P$, proto¾e délka cesty bude krat¹í nebo rovna $N$. Èi¹tìní pak maximálnì sma¾e celý graf, jedno mazání nás stojí konstantní èas, tedy celková slo¾itost tohoto algoritmu bude $\O(MN)$.
  97
  98 Doká¾eme si, ¾e poèet fází je men¹í nebo roven $N$. Algoritmus se ukonèí, pokud $l>N$, proto¾e pak u¾ neexistuje nejkrat¹í $z\rightarrow s$ cesta, pro¹li jsme v¹echny vrcholy.
  99
 100 \s{Lemma:} Pøi ka¾dé fázi vzroste $l$ alespoò o~jedna.
 101
 102 \proof
 103 Uva¾me sí» $R$, rozdìlenou na~vrstvy, je¹tì pøed~proèi¹tìním. Po~proèi¹tìní nìkteré hrany zmizí. Pøibýt\foot{Pøibudou tak, ¾e po~hranì s~nulovým tokem po¹leme nìjaký tok, v~opaèném smìru v~síti rezerv vytvoøíme z~nulové hrany nenulovou.} mohou jen zrcadlové
 104 protìj¹ky ji¾ existujících hran.
 105
 106 Uva¾me cestu $P$ délky $l$ nebo men¹í ze $z\rightarrow s$ a novou hranu $e$ vzniklou pøi~poslání toku po~hranì s~nulovým tokem:
 107 \numlist\nalpha
 108 \:Hrana $e \not\in P\Rightarrow$ zablokování, taková cesta neexistuje.
 109 \:Hrana $e \in P\Rightarrow$ délka $ > l$, proto¾e hrana $e$ vede z nìjakého vrcholu ve vrstvì $C_i$ do vrcholu ve vrstvì $C_{i-1}$.
 110 \qeditem
 111 \endlist
 112
 113 \s{Vìta:} Dinicùv algoritmus najde maximální tok v~èase $\O(MN^2)$.
 114
 115 \proof
 116 Slo¾itost plyne pøímo z~pøedchozího lemmatu a slo¾itosti algoritmu hledání blokujícího toku.
 117
 118 Korektnost (najde v¾dy maximální tok) doká¾eme takto: Nech» algoritmus probìhne. Skonèit mù¾e jedinì tehdy, kdy¾ nenajde ¾ádnou cestu ze~zdroje do~spotøebièe v~síti rezerv, kterou by
 119 mohl být tok vylep¹en. Tedy tok musí být nutnì maximální.
 120 \qed
 121
 122
 123 Takto napsaný algoritmus je je¹tì pøíli¹ pomalý, ale jde výraznì zrychlit. Napøíklad namísto pøepoèítávání tokù na~rezervy a naopak mù¾eme
 124 minimálnì vnitøní cyklus poèítat jenom v~rezervách. Proèi¹tìní se dá dìlat jednou namísto dvakrát, mù¾eme prohledávat do~hloubky a mazat pøi vracení se z~vrcholù. Dokonce i~hledání blokujícího toku lze øe¹it v~rámci prohledávání do~hloubky.
 125 Cesta si pamatuje minimum rezerv a pøi vracení se rezerva sni¾uje.
 126
 127
 128 \>Problematika tokù v~sítích má velké uplatnìní v~kombinatorice a teorii grafù. Zde uvedeme jeden pøíklad:
 129
 130
 131 \>\s{Hledání maximálního párování v bipartitních grafech:} Zorientujeme v¹echny hrany zleva doprava a pøidáme zdroj, z~nìho¾
 132 vedou hrany do první partity, a stok, do~nìho¾ vedou hrany z~druhé partity. Hrany mezi partitami mají jednotkovou kapacitu.
 133
 134 \bye