+
+Ka¾dý tok je tedy vlnou, ale opaènì tomu tak být nemusí -- potøebujeme se
+postupnì zbavit nenulových pøebytkù ve~v¹ech vrcholech kromì zdroje a spotøebièe.
+K~tomu nám bude slou¾it následující operace:
+
+\s{Definice:} {\I Pøevedení pøebytku} po hranì~$uv$, pøièem¾ $f^\Delta(u)>0$ a $r(uv)>0$,
+provedeme tak, ¾e po hranì~$uv$ po¹leme $\delta = \min(f^\Delta(u), r(uv))$ jednotek toku,
+podobnì jako v~pøedchozích algoritmech buï pøiètením po smìru nebo odeètením proti smìru.
+
+\s{Pozorování:} Pøevedení zmìní pøebytky a rezervy následovnì:
+
+$$\eqalign{
+f'^\Delta(u) &= f^\Delta(u) - \delta \cr
+f'^\Delta(v) &= f^\Delta(v) + \delta \cr
+r'(uv) &= r(uv) - \delta \cr
+r'(vu) &= r(vu) + \delta \cr
+}$$
+
+Rádi bychom postupným pøevádìním v¹echny pøebytky buï pøepravili do spotøebièe
+nebo, pokud je vlna pøíli¹ velká, je pøelili zpìt do zdroje. Chceme se ov¹em vyhnout
+pøelévání pøebytkù tam a zase zpìt, tak¾e vrcholùm pøiøadíme {\I vý¹ky} -- to budou
+nìjaká pøirozená èísla $h(v)$.
+
+Pøebytek pak budeme ochotni pøevádìt pouze z~vy¹¹ího vrcholu do~ni¾¹ího. Pokud se
+stane, ¾e nalezneme vrchol s~pøebytkem, ze kterého nevede ¾ádná nenasycená hrana
+smìrem dolù, budeme tento vrchol {\I zvedat} -- tedy zvy¹ovat mu vý¹ku po jedné,
+ne¾ se dostane dostateènì vysoko, aby z~nìj pøebytek mohl odtéci.
+
+Získáme tak následující algoritmus:
+
+\algo{Goldberg}
+\algin Sí».
+\:Nastavíme poèáteèní vý¹ky: \cmt{zdroj ve~vý¹ce~$n$, ostatní ve~vý¹ce~0}
+\::$h(z)\leftarrow n$
+\::$h(v)\leftarrow 0$ pro v¹echny $v\ne z$
+\:Vytvoøíme poèáteèní vlnu: \cmt{v¹echny hrany ze~$z$ na maximum, jinde~0}
+\::$f\leftarrow \hbox{v¹ude nulová funkce}$
+\::$f(zv)\leftarrow c(zv)$, kdykoliv $zv\in E$
+\:Dokud $\exists u \in V \setminus \{z,s\}: f^{\Delta}(u)>0$:
+\::Pokud $\exists v \in V: uv \in E,~r(uv)>0$ a~$h(u)>h(v)$, \hfil\break {\I pøevedeme pøebytek} po~hranì~$uv$.
+\::V~opaèném pøípadì {\I zvedneme} $u$:~$h(u) \leftarrow h(u) + 1$.
+\algout Maximální tok~$f$.
+\endalgo
+
+\h{Analýza algoritmu}
+
+Algoritmus je jednoduchý, ale na první pohled není vidìt ani to, ¾e se v¾dy
+zastaví, nato¾ ¾e by mìl vydat maximální tok. Postupnì o~nìm doká¾eme nìkolik
+invariantù a lemmat a pomocí nich se dobereme k~dùkazu správnosti a èasové slo¾itosti.
+
+\s{Invariant A (základní):}