+Zaveïme fáze stejnì jako v~dùkazu pøedchozí verze lemmatu a rozdìlme je
+na~dva druhy: laciné a~drahé podle toho, kolik se~v~nich provede nenasycených
+pøevedení. Pro ka¾dý druh fází pøitom odhadneme celkový poèet pøevedení
+jiným zpùsobem.
+
+Nech» $k$~je nìjaké kladné èíslo, jeho¾ hodnotu urèíme pozdìji.
+{\I Laciné fáze} budou ty, bìhem nich¾ se~provede nejvý¹e~$k$ nenasycených
+pøevedení. {\I Drahé fáze} budou ty ostatní, tedy takové, ve~kterých
+se~provede více jak~$k$ nenasycených pøevedení.
+
+Teï potøebujeme odhadnout, kolik nás budou stát oba typy fází. Zaènìme tìmi
+jednodu¹¹ími -- lacinými. Jejich poèet shora odhadneme poètem v¹ech fází,
+tedy~$\O(n^2).$ Nenasycených pøevedení se~bìhem jedné laciné fáze provede
+nejvíce~$k$. Bìhem v¹ech laciných fází dohromady jich proto bude $\O(n^2k)$.
+
+Pro~poèet nenasycených pøevedení v~drahých fázích si~zaveïme nový potenciál:
+$$\Psi := \sum_{\scriptstyle{v \ne z,s} \atop \scriptstyle{f^{\Delta}(v) \ne 0}} p(v),$$
+kde~$p(v)$ je poèet vrcholù~$u$, které nejsou vý¹e ne¾~$v$. Neboli:
+$$p(v) = \vert \{ u \in V \mid h(u) \leq h(v) \} \vert.$$
+Tedy platí, ¾e~$p(v)$ je v¾dy nezáporné nikdy nepøesáhne poèet v¹ech vrcholù~$n$.
+Proto~$\Psi$ bude také v¾dy nezáporné a nepøekroèí $n^2$. Rozmysleme si, jak
+bude potenciál ovlivòován operacemi algoritmu:
+
+\itemize\ibull
+\:{\I Inicializace:} Poèáteèní potenciál je nejvý¹e~$n^2$.
+\:{\I Zvednutí vrcholu~$v$}: Hodnota $p(v)$ se zvý¹í nejvý¹e o~$n$
+a v¹echna ostatní~$p(w)$ se buïto nezmìní, nebo klesnou o~1. Bez ohledu
+na pøebytky vrcholù se tedy potenciál zvý¹í nejvý¹e~o~$n$.
+\:{\I Nasycené pøevedení} po~hranì $uv$: Hodnoty $p(\ldots)$ se nezmìní,
+ale mìní se pøebytky -- vrcholu~$u$ se sni¾uje, vrcholu~$v$ zvy¹uje.
+Z~potenciálu proto mù¾e zmizet èlen $p(u)$ a naopak pøibýt $p(v)$.
+Potenciál~$\Psi$ tedy vzroste nejvý¹e o~$n$.
+\:{\I Nenasycené pøevedení} po~hranì $uv$: Hodnoty $p(\ldots)$ se opìt
+nemìní. Pøebytek v~$u$ se vynuluje, co¾ sní¾í~$\Psi$ o~$p(u)$. Pøebytek~$v$
+se naopak zvý¹í, tak¾e pokud byl pøedtím nulový, $\Psi$~se zvý¹í o~$p(v)$.
+Celkovì tedy $\Psi$ klesne alespoò o~$p(u)-p(v)$.
+
+Teï vyu¾ijeme toho, ¾e~pokud pøevádíme po~hranì~$uv$, má tato hrana spád~1.
+Výraz $p(u)-p(v)$ tedy udává poèet vrcholù na~hladinì $h(u)$, co¾ je nejvy¹¹í
+hladina s~pøebytkem. Z~pøedchozího dùkazu víme, ¾e tìchto vrcholù je alespoò
+tolik, kolik je nenasycených pøevedení bìhem dané fáze.
+
+Z~toho plyne, ¾e nenasycená pøevedení provedená bìhem drahých fází sní¾í
+potenciál alespoò o~$k$. Ty v~laciných fázích ho nesni¾ují tak výraznì,
+ale urèitì ho nezvý¹í.
+\endlist
+
+Potenciál~$\Psi$ se~tedy mù¾e zvìt¹it pouze pøi~operacích inicializace, zvednutí a~nasyceného
+pøevedení. Inicializace pøispìje~$n^2$. V¹ech zvednutí se~provede celkem~$\O(n^2)$ a~ka¾dé zvý¹í potenciál nejvý¹e
+o~$n$. Nasycených pøevedení se provede celkem~$\O(nm)$ a~ka¾dé zvý¹í
+potenciál takté¾ nejvý¹e o~$n$. Celkem se~tedy~$\Psi$ zvý¹í nejvý¹e
+o $$n^2 + n \cdot \O(n^2) + n \cdot \O(nm) = \O(n^3 + n^2m).$$
+
+Teï vyu¾ijeme toho, ¾e~$\Psi$ je nezáporný potenciál, tedy kdy¾ ho ka¾dé
+nenasycené pøevedení v~drahé fázi sní¾í~$\Psi$ alespoò o~$k$, mù¾e takových
+pøevedení nastat nejvý¹e $\O(n^3/k + n^2m/k)$. To nyní seèteme s~odhadem
+pro laciné fáze a dostaneme, ¾e v¹ech nenasycených pøevedení probìhne
+$$\O \left(n^2k + {n^3 \over k} + {n^2m \over k} \right) = \O \left(n^2k + {n^2m \over k} \right)$$
+(vyu¾ili jsme toho, ¾e v~souvislých grafech je $m\ge n$, a~tedy $n^2m \ge n^3$).
+
+Tento odhad ov¹em platí pro libovolnou volbu~$k$. Proto zvolíme takové~$k$,
+aby byl co nejni¾¹í. Jeliko¾ první èlen s~rostoucím~$k$ roste a druhý klesá,
+asymptotické minimum nastane tam, kde se tyto èleny vyrovnají, tedy kdy¾
+$n^2k = n^2m / k$.
+
+Nastavíme tedy $k=\sqrt{m}$ a získáme ký¾ený odhad $\O(n^2\sqrt{m})$.
+\qed