From ca75f2703298d96e7314a1ec838458208713cbe5 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Thu, 25 Oct 2007 16:33:30 +0200
Subject: [PATCH] Kus zapisu Dinicova algoritmu, ale zatim ani nejde prelozit,
 nebot mu chybi soubor s obrazkem.

---
 3-dinic/3-dinic.tex | 93 +++++++++++++++++++++++++++++++++++++++++++++
 3-dinic/Makefile    |  3 ++
 2 files changed, 96 insertions(+)
 create mode 100644 3-dinic/3-dinic.tex
 create mode 100644 3-dinic/Makefile

diff --git a/3-dinic/3-dinic.tex b/3-dinic/3-dinic.tex
new file mode 100644
index 0000000..d6cb670
--- /dev/null
+++ b/3-dinic/3-dinic.tex
@@ -0,0 +1,93 @@
+\input ../lecnotes.tex
+
+\prednaska{2}{Toky v sítích (2. èást)}{(zapsali Jakub Melka, Petr Musil)}
+
+Na minulé pøedná¹ce jsme si ukázali \s{Ford-Fulkersonùv} algoritmus. O nìm víme, ¾e kdy¾ se zastaví, tak \uv{vydá} maximální tok. Jen¾e on se zastavit nemusí (napøíklad pro sítì s reálnými kapacitami), nebo trvá pøíli¹ dlouho.
+
+\s{Definice:} 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 : $ 
+\itemize\ibull
+\: $r(e)=c(e)-f(e)$
+\: $r(\overleftarrow{e})=f(e)$
+\endlist
+Kde hrana $\overleftarrow{e}$ vznikne z hrany $e$ tak, ¾e se zorientuje opaèným smìrem. V pøípadì, ¾e tam u¾ opaènì orientovaná hrana je, pak vznikne multigraf\foot{Graf, který mù¾e mít mezi dvìma vrcholy více stejnì orientovaných hran} s multiplikací maximálnì 2.
+
+\s{Vìta:} Je-li $f$ tok v síti $S$ a $g$ tok v pøislu¹né síti rezerv, pak $\exists f'$ v $S$ takový, ¾e $\mid f'\mid = \mid f\mid + \mid g\mid$.
+
+\proof
+Rozebereme si jednotlivé pøípady pro $\forall e\in E$. 
+\numlist\nalpha
+\: $g(e)=g(\overleftarrow{e})=0 \Rightarrow f'(e)=f(e) $
+\: $g(e)>0$ a zároveò $g(\overleftarrow{e})=0\Rightarrow f'(e) = f(e) + g(e)$
+\: $g(e)=0$ a zároveò $g(\overleftarrow{e})>0\Rightarrow f'(e) = f(e) - g(\overleftarrow{e})$
+\: nastává cirkulace, odeèteme $\varepsilon$ od obou hran $e$ a $\overleftarrow{e}$,
+kde $\varepsilon=\min(\lbrace g(e), g(\overleftarrow{e}) \rbrace )$
+\endlist
+
+Je v¹ak $f'$ tok? Tok $f'$ urèitì nemù¾e klesnout pod $0$, proto¾e se odeèítá jen v pøípadì $3$, a tam je z definice vidìt, ¾e to pod $0$ klesnout nemù¾e. Kapacita také nemù¾e
+být pøekroèena, pøièítá se jen v pøípadì $2$ a z definice se \uv{nepokazí}, proto¾e $g(e)=c(e)-f(e)$ - tedy v nejhor¹ím pøípadì $f'(e) = c(e)$.
+
+\qed
+
+\s{Dinicùv algoritmus}
+
+\algo
+\: $f\leftarrow$ nulový tok 
+\: sestrojíme sí» rezerv $R$
+\: $l$ je délka nejkrat¹í cesty $z\rightarrow s$ cesty v $R$
+\: kdy¾ $l=\infty$, tak skonèi
+\: sestrojíme proèi¹tìnou sí» $C$\foot{Ponecháme vrcholy a hrany z $R$, které le¾í na nejkrat¹ích $z\rightarrow s$ cestách} 
+\: $g\leftarrow$ blokující tok v $C$
+\: zlep¹íme tok $f$ podle $g$ a jdi na bod 2
+\endalgo
+
+\figure{sitc.eps}{Pøíklad proèi¹tìné sítì}{\hsize}
+
+\s{Postup tvorby proèi¹tìné sítì :} prohledáním do ¹íøky vytvoøíme vrstvy, zahodímì ty za spotøebièem, ponecháme
+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.
+
+Proèi¹tìní zvládneme v lineárním èase $O(n+m)$, v pøípadì souvislého grafu pouze $O(m)$. 
+
+\s{Definice:} $f$ je blokující tok, pokud na ka¾dé orientované cestì $P$ ze zdroje do spotøebièe $\exists e\in P : f(e)=c(e)$.
+
+\s{Algoritmus hledání blokujícího toku}
+\algo
+\: $g\leftarrow$ nulový tok
+\: Dokud $\exists z\rightarrow s$ cesta $P$ v síti $C$ :
+\:: $\varepsilon = \min\limits_{e\in P}\lbrace c(e)-f(e) \rbrace$
+\:: $\forall e \in P :g(e)=g(e)+\varepsilon$, pokud $g(e)=r(e)$ tak sma¾eme hranu $e$ - proèistíme sí».
+\endalgo
+
+Pøi ka¾dém prùchodu se sma¾e v¾dy alespoò 1 hrana, tedy maximálnì $m$-krát provádíme $O(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(m\cdot n)$.
+
+
+\s{Lemma: } Pøi ka¾dé fázi $l$ vzroste alespoò o jedna.
+
+\proof
+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 mohou jen zrcadlové 
+protìj¹ky ji¾ existujících hran (døíve tam byl tok $O$, zvý¹ením vznikne zrcadlová hrana).
+
+Uva¾me cestu $P$ délky $\leq l$ ze $z\rightarrow s$ :
+\numlist\nalpha
+\: $\not\in P\Rightarrow$ zablokování
+\: $\in P\Rightarrow$ délka $ > l$
+\endlist
+\qed
+
+\s{Vìta: } Dinicùv algoritmus najde maximální tok v èase $O(m\cdot n^2)$.
+
+\proof
+Plyne pøímo z pøedchozího lemmatu a slo¾itosti algoritmu hledání blokujícího toku.
+\qed
+
+Takto napsaný algoritmus je pro implementaci pøíli¹ pracný. Napøíklad namísto pøepoèítávání tokù na rezervy a naopak. Mù¾eme
+minimálnì vnitøní cyklus poèítat jenom v rezervách. Proèi¹tìní se dá dìlat jednou namísto $2\times$. Napøíklad 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, 
+cesta si pamatuje minimum rezerv a pøi vracení se pak hned rezervu sni¾uje.
+
+
+\>Problematika tokù v sítích má velké uplatnìní v kombinatorice a teorii grafù. Zde uvedeme jeden pøíklad :
+
+
+\>\s{Hledání maximálního párování v bipartitních grafech :} Zorientujeme v¹echny hrany zleva do prava a pøidáme zdroj, z nìj
+vedou hrany do 1.partity a stok, do nìj vedou hrany z 2. partity, hrany mezi partitami mají kapacitu 1.
+
+\bye
diff --git a/3-dinic/Makefile b/3-dinic/Makefile
new file mode 100644
index 0000000..fc07c0a
--- /dev/null
+++ b/3-dinic/Makefile
@@ -0,0 +1,3 @@
+P=3-dinic
+
+include ../Makerules
-- 
2.39.5