Definice: Množina hran $M\subseteq E$ v grafu $G=(V,E)$ je párování pokud žádný vrchol $v\in V$ neleží ve dvou hranách $M$. Jinými slovy, párování je množina nezávislých hran. Párování $M$ je maximální, pokud pro každé párování $M’$ platí $|M|\geq |M’|$.
Věta: Maximální párování v bipartitním grafu $G=(V_1 \cup V_2, E)$ můžeme spočítat pomocí toku v síti v čase $\OO(n^2m)$.
Důkaz: Zkonstruujeme orientovaný graf $G’=( V_1 \cup V_2\cup \{S,T\}, E‘)$ následujícím způsobem. K původnímu grafu $G$ přidáme super-zdroj $S$ a super-spotřebič $T$. Super-zdroj spojíme se všemi vrcholy $v_1\in V_1$ hranou $Sv_1$. Každý vrchol $v_2\in V_2$ spojíme se super-spotřebičem hranou $v_2T$. Původní hrany grafu orientujeme z množiny $V_1$ do $V_2$. Kapacity všech hran nastavíme na $1$.



Tvrdíme, že v grafu $G’$ existuje maximální tok velikosti $k$ právě tehdy, když v bipartitním grafu $G$ existuje maximální párování velikosti $k$.

Nejprve ukažme první implikaci. Protože jsou kapacity hran v grafu $G’$ celočíselné, tak v $G’$ existuje celočíselný maximální tok (důsledek „existence celočíselného toku„). Tok po každé hraně je buď $0$ nebo $1$. Protože do každého vrcholu $v\in V_1$ může přitékat nejvýše tok velikosti $1$ a z každého vrcholu $v\in V_2$ může odtékat nejvýše tok velikosti $1$, tak je maximální celočíselný tok v $G’$ sjednocením $k$ vrcholově disjunktních1 $(S,T)$-cest. Ty obsahují disjunktní hrany tvořící párování.

Na druhou stranu můžeme hrany tvořící párování v $G$ rozšířit do vrcholově disjunktních $(S,T)$-cest grafu $G’$.

Pro nalezení maximálního párování v bipartiním grafu $G$ tedy stačí najít maximální tok v pomocném grafu $G’$.

Pomocný graf $G’$ má speciální tvar a dá se ukázat, že v něm Dinicův algoritmus trvá jen čas $\OO(n^{2/3}m)$ (viz cvičení).2 Takže maximální párování ve skutečnosti najdeme rychleji.