\proof{Indukcí a~obrázkem.}
-Zaèneme s øezem ($V \setminus \{s\}, \{s\}$). Pro~tento øez lemma platí z~definice velikosti toku. Dále budu postupnì pøesouvat vrcholy z~mno¾iny $B$ do~mno¾iny $A$. Libovolý øez mù¾e být takto vytvoøen z~toho triviálního.
+Zaèneme s øezem ($V \setminus \{s\}, \{s\}$). Pro~tento øez lemma platí z~definice velikosti toku. Dále budu postupnì pøesouvat vrcholy z~mno¾iny $B$ do~mno¾iny $A$. Libovolný øez mù¾e být takto vytvoøen z~toho triviálního.
Pøedstavme si, ¾e~máme ji¾ libovolný øez ($A,B$) a~pøesouváme vrchol $v$ z~$A$ do~$B$. Tedy $A' = A \setminus \{v\}$ a $B' = B \cup \{v\}$.
\s{Definice:} Párování je maximální, pokud obsahuje nejvìt¹í mo¾ný poèet hran.
-Mìjme bipartitní graf $G = (V,E)$. V~nìm hledáme maximální párování. Sestrojme si~sí» takovou, ¾e~vezmeme vrcholy $V$ grafu $G$ a~pøidáme k~nim dva speciální vrcholy $z$ (zdroj) a~$s$ (stok) a~ze~zdroje pøidáme hrany do~v¹ech vrcholù levé partity a~ze~v¹ech vrcholù pravé partity povedeme hrany do~stoku. V¹echny kapacity nastavme na~1. Hrany bipartitního grafu zorientujme z levé partity do pravé. Nyní staèí jen na~tuto sí» spustit Fordùv-Fulkersonùv algoritmus (nebo libovolný jiný algoritmus, který najde maximální celoèíselný tok) a~a¾~dobìhne, tak prohlásit hrany s~kapacitami 1 za~maximální párování.
+Mìjme bipartitní graf $G = (V,E)$. V~nìm hledáme maximální párování. Sestrojme si~sí» takovou, ¾e~vezmeme vrcholy $V$ grafu $G$ a~pøidáme k~nim dva speciální vrcholy $z$ (zdroj) a~$s$ (stok) a~ze~zdroje pøidáme hrany do~v¹ech vrcholù levé partity a~ze~v¹ech vrcholù pravé partity povedeme hrany do~stoku. V¹echny kapacity nastavme na~1. Hrany bipartitního grafu zorientujme z levé partity do pravé. Nyní staèí jen na~tuto sí» spustit Fordùv-Fulkersonùv algoritmus (nebo libovolný jiný algoritmus, který najde maximální celoèíselný tok) a~a¾~dobìhne, tak prohlásit hrany s~tokem 1 za~maximální párování.
\figure{toky04.eps}{Hledání maximálního párování v~bipartitním grafu.}{2in}