-\:Je pro pøirozené kapacity F.F. algoritmus koneèný? Ano - v ka¾dém zlep¹ujícím kroku algoritmu se celkový tok zvìt¹í aspoò o 1. Proto¾e máme horní odhad na maximální tok (napø. souèet kapacit v¹ech hran), máme i~horní odhad na dobu bìhu algoritmu.
-\:Je F.F. algoritmus koneèný pro racionální kapacity hran? Ano - v¹echny kapacity vynásobíme spoleèným jmenovatelem a pøevedeme na pøedchozí pøípad (pro obecné kapacity ov¹em takto definovaný F.F. algoritmus nemusí být koneèný).
-\:Kolik krokù bude muset algoritmus na následující síti maximálnì udìlat, aby úspì¹nì dobìhl? (2M krokù)
+\:Je pro pøirozené kapacity F-F algoritmus koneèný? Ano -- v ka¾dém zlep¹ujícím
+kroku algoritmu se celkový tok zvìt¹í aspoò o jedna. Proto¾e máme horní odhad
+na velikost maximálního toku (napø. souèet kapacit v¹ech hran), máme i~horní odhad na dobu
+bìhu algoritmu.
+\:Je F-F algoritmus koneèný pro racionální kapacity hran? Ano -- v¹echny
+kapacity vynásobíme spoleèným jmenovatelem a pøevedeme na pøedchozí pøípad.
+Algoritmus se pøitom chová stejnì jako s~pùvodními kapacitami.
+\:A~pro reálné kapacity? Obecnì ne -- zkuste najít sí» s~nìkterými kapacitami
+iracionální, kde se algoritmus pøi ne¹ikovné volbì zlep¹ujících cest nikdy
+nezastaví a dokonce ani nekonverguje k~maximálnímu toku.
+\:Kolik krokù bude muset algoritmus na následující síti maximálnì udìlat, aby
+úspì¹nì dobìhl? ($2M$ krokù)
+\figure{2M.eps}{Pøíklad sítì. Kolik krokù musí maximálnì udìlat F-F algoritmus?}{2in}
+\:Pokud bychom v¾dy hledali {\I nejkrat¹í} zlep¹ující cestu, co¾ je snad
+nejpøímoèaøej¹í mo¾ná implementace (prohledávání do ¹íøky), algoritmus by
+se zastavil po~$\O(M^2N)$ krocích (tomu se øíká Edmondsùv-Karpùv algoritmus).
+To si nebudeme dokazovat a místo toho si na~pøí¹tí pøedná¹ce rovnou odvodíme
+efektivnìj¹í Dinicùv algoritmus.