Ford-Fulkerson teorem

Ford - Fulkerson - satsen är en grafens maximala flödessats nära besläktad med Mengers sats .

Det låter så här: värdet på det maximala flödet i kurvdiagrammet är lika med värdet på genomströmningen av dess minimisnitt .

Tillräcklighet: varje flöde mellan hörn t och s är mindre än eller lika med värdet för varje skärning . Låt lite flyta och något avsnitt ges. Värdet på detta flöde är summan av värdena för "last" som transporteras längs alla möjliga vägar från vertex t till s . Varje sådan väg måste ha en gemensam kant med den givna sektionen. Eftersom det för varje kant av sektionen är omöjligt att överföra "lasten" mer än dess bärförmåga, är därför summan av alla laster mindre än eller lika med summan av alla bärförmåga för kanterna på denna sektion. Påståendet har bevisats.

Det följer att vilket flöde som helst är mindre än eller lika med värdet av minsektionen, och följaktligen är det maximala flödet mindre än eller lika med värdet av minsektionen.

Ford-Fulkerson-algoritmen för att hitta det maximala flödet i en graf är baserad på denna sats, den är också ett bevis på nödvändigheten av denna sats, det vill säga den är konstruktiv.

Ett annat bevis (via förstärkning)

Låt oss stärka Ford-Fulkerson-satsen enligt följande. För ett nätverk med ett flöde f kommer vi att bevisa likvärdigheten av följande tre fakta på en gång: $G(V,E)$

1° Flöde maximalt

2° Kapaciteten för det minsta skäret är lika med värdet på flödet f

3° Det finns ingen komplementär väg i grafen $G$

1° → 3°. Om vi antar motsatsen får vi den motsägelse som beskrivs i informationen om den komplementära vägen i transportgrafen .

3° → 2°. Det är uppenbart att värdet på flödet f inte överstiger kapaciteten för minimisnittet . Låt . Överväg sedan ett snitt där uppsättningen innehåller alla hörn, utom . Då är dess genomströmning inte mindre än genomströmningen av minimisnittet, som i sin tur är större än värdet på flödet f. Därför finns det en riktning från till , sådan att . Låt oss nu ta alla dessa och flytta dem till . Efter att ha övervägt det resulterande snittet, noterar vi att dess genomströmning också är större än flödesvärdet. Vi ökar mängden igen och gör så tills endast vertexen finns kvar i setet . Det kommer också att vara den första toppen på vägen som vi skapar. Nu tittar vi på vilket par vi valde förra draget. Låt det vara ett par . Sedan lägger vi till en vertex till banan . Därefter tittar vi i ett par med vilken vertex vertexet var från början . Låt det . Sedan vidare till banan lägger vi till vertexet . Vi gör detta tills vi når toppen . Men genom konstruktion är denna väg rest, vilket motsäger antagandet. $(S,T)$ $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)$ $v$ $t$

2° → 1°. Som redan nämnts är det uppenbart att värdet av något flöde inte överstiger genomströmningen av minimisnittet, och värdet på vårt flöde är lika. Då är flödets värde inte mindre än värdet av något annat flöde i vårt nätverk, det vill säga flödet är maximalt. $f$ $f$ $f$

Detta bevis är bra eftersom det inte använder en komplex algoritm för att hitta det maximala flödet i ett godtyckligt transportnätverk.

Exempel

Till höger finns ett nätverk med 6 hörn och det totala flödet från källa till avlopp är 5. Detta flöde är det maximala för detta nätverk. $V = \{s,o,p,q,r,t\}$ $s$ $t$

I detta nätverk är 2 minimala nedskärningar möjliga:

Snitt	Flöde
$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$

Litteratur

Novikov F. A. Diskret matematik för programmerare . - 3:a. - St Petersburg. : Peter , 2009. - S. 277 -279. — 384 sid. - ISBN 978-5-91180-759-7 .

Länkar

Ford-Fulkerson algoritm på algolist.manual.ru.
Nätverk, flöden i nätverk. Ford-Fulkerson teorem på Mini-Soft.ru