Bipartitní matching přes max flow

Největší párování má 3 hrany, např. $M = \{x_1\text{–}y_2,\ x_2\text{–}y_1,\ x_4\text{–}y_3\}$. Hladový postup ale snadno uvázne na dvou: vezmeš $x_1$–$y_1$, pak třeba $x_4$–$y_2$ — a konec. $x_2$ umí jen $y_1$ (obsazeno), $x_3$ jen $y_2$ (obsazeno), $y_3$ by chtělo jen $x_4$ (obsazeno). Žádnou hranu už přidat nejde, a přesto párování není největší — muselo by se přepojit. Tomuhle rozdílu se říká maximal (nerozšiřitelné) vs. maximum (největší) — a přesně na přepojování máme v téhle kapitole nástroj: zpětné hrany reziduálního grafu [L4.2].

Cesta $x_2 - y_1 - x_1 - y_2$: hrany střídavě mimo $M$ ($x_2$–$y_1$), v $M$ ($y_1$–$x_1$), mimo $M$ ($x_1$–$y_2$) — to je M-alternating — a oba konce $x_2$, $y_2$ jsou nepokryté → M-augmenting. Přehození = hrany mimo $M$ do párování přidej, hrany v $M$ vyhoď: nové $M = \{x_2\text{–}y_1,\ x_1\text{–}y_2\}$. Cesta má lichý počet hran, krajních „mimo $M$“ je o jednu víc než vnitřních „v $M$“ — párování se zvětší přesně o 1. A věta ze slidu říká, že tohle je jediné, co kdy potřebuješ: když M-augmentující cesta neexistuje, $M$ už je maximum.

Je to slovo od slova Ford-Fulkerson [L4.3]: augmentující cesta v reziduálním grafu, augmentace, opakuj, dokud cesta existuje — a kritérium maximality „žádná augmentující cesta“ je totéž tvrzení jako věta ze slidu 39. To není náhoda: za chvíli uvidíš, že po převodu na tok M-augmentující cesta = augmentující cesta v $G_f$, včetně přehazování přes zpětné hrany. Stačí tedy umět ten převod.

„Vrchol $x_i$ smí být nejvýš v jedné hraně párování“ = „do $x_i$ smí přitéct nejvýš jednotka“. Tak mu ji přiveď jedinou hranou $s \to x_i$ s kapacitou 1 — Kirchhoff [L4.1] pak zaručí, že z $x_i$ odteče nejvýš 1, tedy nejvýš jedna hrana z $x_i$ ponese tok. Symetricky vpravo: hrana $y_j \to t$ s kapacitou 1 hlídá, že do $y_j$ vstoupí nejvýš jedna párovací hrana. Hrany grafu zorientuješ $X \to Y$. Žádné dolní meze nepotřebuješ — $l \equiv 0$.

Půlka hrany v párování nedává smysl — frakční tok párování není. Zachraňuje nás Integral Flow Theorem (Dantzig-Fulkerson, slide 17 — citovaný v [L4.5]): kapacity jsou celé (samé jedničky), takže existuje celočíselný maximální tok, a Ford-Fulkerson ho rovnou najde (startuje z $f \equiv 0$ a každé $\gamma$ je celé, tady vždy $\gamma = 1$). Celočíselný tok s kapacitami 1 je 0/1 tok — každá hrana buď nese jednotku, nebo nic. U zkoušky tuhle větu vždy zmiň: bez ní jsi vyřešil jen LP relaxaci.

Kdyby dvě hrany $M$ sdílely vrchol $x_i$, odtékaly by z $x_i$ aspoň 2 jednotky — ale přitéct může jen 1 (jediná hrana $s \to x_i$, kapacita 1), spor s Kirchhoffem. Symetricky pro $y_j$ přes hranu $y_j \to t$. Takže $M$ je párování. A velikost: $|f| = \sum_i f(s \to x_i)$ = počet vrcholů $X$ s protékající jednotkou = počet hran s $f = 1$ = $|M|$. Funguje to i obráceně — každé párování $M$ vyrobí přípustný 0/1 tok s $|f| = |M|$ (pusť jednotku po $s \to x_i \to y_j \to t$ pro každou hranu $M$). Tudíž max tok = max párování, ne jen nerovnost.

Vrcholy $X$ nelze spárovat všechny, takže párování pokrývající všechny vrcholy ($X$ i $Y$) — perfect matching [L0.6] — neexistuje (tady ostatně ani nemůže: $|X| \ne |Y|$; ale nejde spárovat ani celé $X$). Certifikátem je minimální řez [L4.4]: $A = \{s, x_1, x_2, x_3, y_1, y_2\}$ má kapacitu $C(A) = u(s \to x_4) + u(y_1 \to t) + u(y_2 \to t) = 3 = |f|$, takže víc než 3 párovací hrany být nemohou. Řez má i čitelnou interpretaci: $x_1, x_2, x_3$ se umí napojit jen na $\{y_1, y_2\}$ — tři vrcholy se „mačkají“ o dva sousedy, jeden z nich zůstane vždy nespárovaný.