Fordova-Fulkersonova věta

Ford - Fulkersonův teorém je graf maximálního toku teorém úzce související s Mengerovou větou .

Zní to takto: hodnota maximálního průtoku v grafu dráhy je rovna hodnotě propustnosti jeho minimálního řezu .

Dostatečnost: jakýkoli tok mezi vrcholy tas je menší nebo roven hodnotě jakéhokoli řezu . Nechat trochu plynout a dát nějaký úsek. Hodnota tohoto toku je součtem hodnot „nákladu“ přepraveného po všech možných trasách z vrcholu t do s . Každá taková cesta musí mít společnou hranu s daným úsekem. Protože pro každou hranu profilu nelze přenést „zatížení“ větší, než je jeho nosnost, je proto součet všech zatížení menší nebo roven součtu všech nosností hran tohoto profilu. Tvrzení bylo prokázáno.

Z toho vyplývá, že jakýkoli průtok je menší nebo roven hodnotě minimálního průřezu, a tudíž maximální průtok je menší nebo roven hodnotě minimálního průřezu.

Ford-Fulkersonův algoritmus pro nalezení maximálního toku v grafu je založen na této větě, je také důkazem nezbytnosti této věty, tedy je konstruktivní.

Další důkaz (pomocí zesílení)

Posílíme Fordovu-Fulkersonovu větu následovně. Pro síť s tokem f prokážeme ekvivalenci následujících tří skutečností najednou: $G(V,E)$

1° Maximální průtok

2° Kapacita minimálního řezu se rovná hodnotě průtoku f

3° V grafu není žádná doplňková cesta $G$

1° → 3°. Za předpokladu opaku dostaneme rozpor popsaný v informaci o komplementární cestě v transportním grafu .

3° → 2°. Je zřejmé, že hodnota průtoku f nepřesahuje kapacitu minimálního řezu . Nechte _ Pak zvažte řez, kde množina obsahuje všechny vrcholy kromě . Potom jeho průchodnost není menší než průchodnost minimálního řezu, která je zase větší než hodnota průtoku f. Existuje tedy směr od do , takže . Nyní si je vezměme všechny a přesuneme je do . Po zvážení výsledného řezu zjistíme, že jeho propustnost je také větší než hodnota průtoku. Množinu opět zvětšujeme a děláme tak, dokud v množině nezůstane pouze vrchol . Bude to také první vrchol na cestě, kterou vytváříme. Nyní se podíváme na to, který pár jsme zvolili jako poslední tah. Ať je to pár . Poté k cestě přidáme vrchol . Dále se podíváme do páru, se kterým vrcholem byl vrchol na prvním místě . Nech to . Dále k cestě přidáme vrchol . Děláme to, dokud nedosáhneme vrcholu . Konstrukčně je však tato cesta zbytková, což je v rozporu s předpokladem. $(SVATÝ)$ $c(S,T)>f$ $S$ $t$ $(u,t)$ $S$ $T$ $f(u,t)<c(u,t)$ $u$ $T$ $T$ $S$ $s$ $(s,u)$ $u$ $u$ $(u,v)$ $proti$ $t$

2° → 1°. Jak již bylo zmíněno, je zřejmé, že hodnota žádného průtoku nepřesahuje propustnost minimálního řezu a hodnota našeho průtoku se rovná. Hodnota toku pak není menší než hodnota jakéhokoli jiného toku v naší síti, to znamená, že tok je maximální. $F$ $F$ $F$

Tento důkaz je dobrý, protože nepoužívá složitý algoritmus pro nalezení maximálního toku v libovolné transportní síti.

Příklad

Vpravo je síť se 6 vrcholy a celkový průtok od zdroje k odtoku je 5. Tento průtok je pro tuto síť maximální. $V = \{s,o,p,q,r,t\}$ $s$ $t$

V této síti jsou možné 2 minimální řezy:

Řez	Tok
$S=\{s,o,p\},T=\{q,r,t\}$	$c(o,q)+c(p,r)=3+2=5$
$S=\{s,o,p,q,r\},T=\{t\}$	$c(q,t)+c(r,t)=2+3=5$

Literatura

Novikov F. A. Diskrétní matematika pro programátory . - 3. - Petrohrad. : Peter , 2009. - S. 277 -279. — 384 s. - ISBN 978-5-91180-759-7 .

Odkazy

Ford-Fulkersonův algoritmus na algolist.manual.ru.
Sítě, toky v sítích. Fordova-Fulkersonova věta na Mini-Soft.ru