Fold-Fullkersonova věta pro vrcholy
Úloha číslo: 3834
Vyslovte a dokažte analogii Ford-Fulkersonovy věty pro sítě s omezením kapacit vrcholů místo hran.
Řešení
Tvrzení: Síť s kapacitami vrcholů má tok o velikosti \( k \), právě když minimální vrcholový řez oddělující \( s \) a \( t \) má velikost \( k \).
Důkaz: Nahradíme každou hranu dvojicí protilehlých hran (digon) s neomezenou kapacitou. Každý vrchol \(u\) rozdělíme na dva vrchly \(u’\) a \(u’’\), že \(u’\) je incidentní se všemi hranami vcházejícími do \(u\) a podobně \(u’’\) se všemi vycházejícími. Přidáme hranu \((u’,u’’)\) a přidělíme jí kapaciu, jakou měl vrchol \(u\) v původním grafu.
Maximální tok v novém grafu odpovídá hranovému řezu v novém grafu. Tento řez odpovídá vrcholovému řezu v původním grafu. Navíc existuje přímá korespondence mezi toky ve starém a v novém grafu (až na cirkulace uvnitř digonů).
