%%%%%%%%%%%%%%%%%%%%%%%
% Zápisek prvého semináøe z grafových algoritmù - ze dne ? 7.6.2006 ?
% Téma Toky v sítích a zejména Ford-Fulkersonùv algoritmus.
% Zapsal Radovan ©esták - radovan.sestak@gmail.com
%%%%%%%%%%%%%%%%%%%%%%

\input ../sgr.tex

\prednaska{1}{Toky v sítích a FF algoritmus}{zapsal Radovan ©esták}

\h{Toky v sítích}

V následujícím odstavci uká¾eme nìkolik tvrzení o sítích, které je
mo¾né si pøedstavit jako sí» potrubí køí¾ící se v uzlech. Vrchol
z kterého se kapalina ¹íøí nazveme zdroj a vrchol kde odtéká stok. Pro
ostatní vrcholy platí, ¾e objem kapaliny pøitékající se rovná objemu
kapaliny odtékající. Toto pravidlo, které pochází z teorie o elektrických obvodech,
se zvykne nazývat Kirchhoffùv zákon. Hledání maximálního toku je duální úlohou k hledání 
minimálního øezu. Ford-Fulkersonùv(FF) algoritmus, který bude popsán ní¾e je základním 
algoritmem pro hledání tokù. Na úlohu hledání maximálního toku se dají pøevést mnohé
grafové problémy a i proto existuje mnoho algoritmù a nìkteré z nich jsou pouze modifikace 
základního FF algoritmu. V dal¹í pøedná¹ce najdete Dinitzùv algoritmus pro tenhle problém.


\s{Definice:}

\itemize\ibull
\:sí»: $N=(V,E,s,t,w)$ kde $V$ je mno¾ina vrcholù, $E\subseteq V\times V$,
$s\in V$ je zdroj, $t\in V$ je stok, $w:\, E\rightarrow{R}^{+}$ jsou kapacity hran
\:tok: $f:\, E\rightarrow{R}^{+}$kde $\forall e\in E\, f(e)\leq w(e)$ a
$\forall v\in V,\, v\neq s,\, v\neq t\,\,\sum_{uv\in E}f(uv)=\sum_{vw\in E}f(vw)$
\:velikost toku: $\|f\|=\sum_{sv\in E}f(sv)-\sum_{vs\in E}f(vs)$ kde $s$ je zdroj
\:øez: $st$-øez je mno¾ina hran $C\subseteq E$ taková, ¾e v grafu $(V,\, E\setminus C)$ neexistuje
cesta z s do t
\:separátor: $st$-separátor je mno¾ina vrcholù $S\subseteq V$ taková, ¾e v grafu
$(V\setminus S,\, E\cap(V\setminus S)\times(V\backslash S))$ neexistuje
cesta z s do t
\:velikost øezu: $\|c\|=\sum_{e\in c}w(e)$ je velikost øezu
\endlist

\figure{graf.eps}{Pøíklad orientovaného grafu ze zvoleným zdrojem a stokem.}{0.4\hsize}

\s{Vìta(Ford-Fulkerson) o souvislosti tokù a øezù}
Nech» $N=(V,E,s,t,w)$ je sí», $F$ je mno¾ina pøípustných tokù pro tuto sí» a $C$ je
mno¾ina øezù oddìlující zdroj od stoku. Pak 
$$max_{f\in F}|f|=min_{c\in C}\|c\|$$. 
Vìta platí pro v¹echny výbìry zdrojù a stokù $\forall s,t\in V, s\neq t$ nech» $st-F$ je mno¾ina
v¹ech tokù ze zdroje $s$ do stoku $t$ a $st-C$ je mno¾ina v¹ech øezù oddìlujících $s$ od $t$. Pak
$$max_{f\in st-F}\|f\|=min_{c\in st-C}\|c\|$$
pro graf $G=(V,E,w)$.

\s{Dùkaz vìty:}

\s{$max_{f}\|f\|\leq min_{c}\|c\|$:} Vìznìme libovolný øez oddìlující zdroj od stoku $c$ a uva¾me
graf $G'=(V,E\setminus c)$, který vznikl odebráním hran nacházejících se v øezu. Buï $S$ mno¾ina 
vrcholù dosa¾itelných ze zdroje v $G'$.
Pro libovolnej tok  $f$ platí: 

$$\|f\| =  \sum_{uv\in E, u\in S, v\notin S}f(uv) - \sum_{uv\in E, u\in S, v\notin S}f(vu)$$
velikost toku je rovna rozdílu velikostí tokù pøes hrany opou¹tìjící $S$ a pøicházející do $S$.
$$\|f\| = \sum_{u\in V}f(su) - \sum_{u\in V}f(us)$$
proto¾e se tok zachovává ve v¹ech vrcholech partity $S$ kromì $s$ dostáváme
$$= \sum_{v\in S}(\sum_{u\in V}f(uv)-\sum_{u\in V}f(vu))$$
$f(uv)$ pro $u,v\in S$ jsme jednou pøièítali a jednou odèítali
$$= \sum_{uv\in E, u\in S, v\notin S}f(uv) - \sum_{uv\in E, u\in S, v\notin S}f(vu)$$

Teï si u¾ staèí jenom uvìdomit, ¾e 
$$\|f\| = \sum_{uv\in E, u\in S, v\notin S}f(uv)- \sum_{uv\in E, u\in S, v\notin S}f(vu) \leq \sum_{uv\in E, u\in S, v\notin S}f(uv)
\leq \sum_{uv\in E, u\in S, v\notin S}w(uv) \leq \|c\|$$
Poslední nerovnost je dùsledkem toho, ¾e øez obsahuje v¹echny hrany opou¹tìjící $S$.

$max_{f}|f|\geq min_{c}|c|$: dùkaz plyne z korektnosti
Ford-Fulkersonova algoritmu viz. algoritmus dále

\s{Dùsledek:}Pro ka¾dou sí» s celoèíselnými kapacitami je její maximální tok celoèíselný.

\h{Maximální párování v bipartitním grafu}
Maximální párování v bipartitním grafu $(A\cup B,E)$ se dá najít
pomocí maximálního toku v síti $(A\cup B\cup s\cup t,E',s,t,w)$ kde
$w(e)=1$ a $E'=\{ uv\| u\in A, uv\in E\} \cup \{su\| u\in A\} \cup\{ut\| u\in B\}$ a
obdobnì mù¾eme nalézt minimální vrcholové pokrytí.

\figure{bip-graf.eps}{Bipartitní graf pro který hledáme maximální párování.}{0.2\hsize}
\figure{bip-tok.eps}{Sí» v které najdeme maximální tok.}{0.3\hsize}

\s{Definice}
\itemize\ibull
\:neorientovaný graf G je vrcholovì k-souvislý $\Leftrightarrow$ G má alespoò
k+1 vrcholù a neexistuje separátor s ménì ne¾ k vrcholy
\:neorientovaný graf G je hranovì k-souvislý $\Leftrightarrow$ G má alespoò k+1 vrcholù
a neexistuje øez s ménì ne¾ k hranami
\:orientovaný graf je silnì souvislý $\Leftrightarrow$ existuje orientovaná cesta mezi
v¹emi vrcholy v obou smìrech
\:cirkulace je nulový tok t.j.  $\forall v\in V, \sum f(uv)=\sum f(vu)$
\endlist

\s{Vìta:}(Menger) o souvislosti existencí disjunktních cest a souvislostí
grafù

buï $G$ neorientovaný graf, pak:
\itemize\ibull
\:$G$ je vrcholovì k-souvislý $\Leftrightarrow$$\forall v,w\in V\,\exists$
k vrcholovì disjunktních cest z $v$ do $w$
\:$G$ je hranovì k-souvislý $\Leftrightarrow$$\forall v,w\in V\,\exists$
k hranovì disjunktních cest z $v$ do $w$
\:kdy¾ $u$ a $v$ jsou nesousední vrcholy v $G$ pak maximální poèet vrcholovì disjunktních
cest mezi $u$ a $v$ se rovná minimálnímu poètu vrcholù z $G-{u,v}$ kterých odebrání oddìlí
$u$ od $v$ 
\:kdy¾ $u$ a $v$ jsou vrcholy v $G$ pak maximální poèet hranovì disjunktních
cest mezi $u$ a $v$ se rovná minimálnímu poètu hran, kterých odebrání oddìlí $u$ od $v$
\endlist
buï $G$ orientovaný graf, pak:
\itemize\ibull
\:kdy¾ $u$ a $v$ jsou vrcholy $G$, $uv\notin E(G)$ pak maximální poèet vrcholovì disjunktních
cest z $u$ do $v$ je rovný minimálnímu poètu vrcholù z $G-{u,v}$ kterých odebrání oddìlí $u$ od $v$
\:kdy¾ $u$ a $v$ jsou vrcholy $G$ pak maximální poèet hranovì disjunktních cest z $u$ do $v$ je
rovný minimálnímu poètu hran, kterých odebrání oddìlí $u$ od $v$
\endlist

Vrcholová i hranová souvislost grafu se dá zjistit pomocí maximálního
toku. Pro hranovou souvislost pøímo zjistíme maximální tok pro ka¾dou
dvojici vrcholù (volba zdroje a stoku). V pøípadì neorientovaného grafu vyrobíme orientovaný graf tak, ¾e ka¾dou
neorientovanou hranu nahradíme orientovanými v obou smìrech. Pro vrcholovou souvislost
navíc musíme ka¾dý vrchol nahradit dvìma novými a spojit je hranou
v obou smìrech (pod-rozdìlení vrcholu). Kapacity hran volíme 1.
Pro nalezení tìchto cest staèí v¾dy v síti odebírat postupnì cestu
z $s$ do $t$. Odebrání jedné cesty sní¾í tok o jedna a tedy cest
musíme nalézt $k$.
\figure{vrchol.eps}{Vrchol který chceme pod-rozdìlit.}{0.1\hsize}
\figure{podrozdeleni.eps}{Výsledek pod-rozdìlení vrcholu.}{0.15\hsize}


\s{Ford-Fulkersonùv algoritmus}
Algoritmus nepracuje pøímo s kapacitami a s toky pøes hrany, ale s rezervami
tìchto hran. Funkce rezerv definujeme jako $r(uv)\equiv w(uv)-f(uv)+f(vu)$.
Jestli $uv\notin E(G)$ pak $w(uv)=0$.
Kdy¾ zmen¹ujeme rezervu hrany tak o stejnou hodnotu zvý¹íme hodnotu
rezervy opaèné hrany. Dále pak FF cesta, je cesta pro kterou má ka¾dá hrana kladnou rezervu.

\algo
\:nastav rezervy pro nulový tok na v¹ech hranách (rezervy se rovnají kapacitám)
\:while $\exists$FF cesta z $s$ do $t$
\::buï $p$ FF cesta z $s$ do $t$
\::zvìt¹i tok zmen¹ením rezerv, o $m=min_{uv\in p}r(uv)$ 
\:end while
\:spoèti tok z rezerv
\endalgo

Pro dùkaz korektnosti algoritmu uva¾ mno¾inu $X=\{ v,\,\exists$FF
cesta z $s$ do $v\}$ po dobìhnutí algoritmu. Proto¾e neexistuje FF cesta z $s$ do $t$, $t\notin X$.
Pak mno¾iny $X$ a $V\setminus X$ urèují øez tvoøený hranami spojujícími
vrcholy z rùzných mno¾in $c=\{uv: uv\in E, u\in X, v\in V\setminus X\}$. V¹echny hrany $uv\in c$
mají nulovou rezervu, nebo» jinak by se dala prodlou¾it FF cesta do vrcholu z $V\setminus X$. Tak¾e velikost
toku se rovná souètu kapacit hran z $X$ do $V\setminus X$ (tohle tvrzení jsme dokázali pøi dùkazu opaèné implikace
FF vìty). Souèasnì tyhle hrany tvoøí $st$-øez, kterého kapacita je rovna velikosti toku. Na¹li jsme tedy øez, 
kterého velikost se rovná velikosti pøípustného toku a tím je dùkaz FF vìty ukonèen. 

Kdy¾ máme celoèíselné kapacity hran tak v ka¾dém kroku se tok zvìt¹í
alespoò o jedna a maximální tok je z hora omezen, napøíklad souètem
v¹ech kapacit hran. Pro racionální kapacity staèí vynásobit kapacity
a dostaneme celoèíselné.  Z toho plyne koneènost FF algoritmu pro hrany s racionálními kapacitami.
Táto varianta FF algoritmu není obecnì koneèná pøi reálných kapacitách. Volíme-li ov¹em zlep¹ující cestu, která
má maximální minimum pøes rezervy tak je FF algoritmus koneèný i pro reálné kapacity hran.

Pro FF algoritmus s jednotkovými kapacitami a vyu¾itím BFS (procházení
do ¹íøky) na hledání FF cest je èasová slo¾itost algoritmu $O(n.m)$.
Edmunds s Karpem dokázali, ¾e pøi volbì nejkrat¹í cesty je èasová
slo¾itost v obecném pøípadì $O(n.m^{2})$.

\bye
