Ford-Fulkerson teorem

Ford - Fulkerson -sætningen er en grafens maksimale flowsætning , der er tæt forbundet med Mengers sætning .

Det lyder sådan her: Værdien af det maksimale flow i kurvegrafen er lig med værdien af gennemløbet af dets minimumssnit .

Tilstrækkelighed: enhver strømning mellem spidserne t og s er mindre end eller lig med værdien af ethvert snit . Lad noget flyde og noget afsnit gives. Værdien af dette flow er summen af værdierne af "last" transporteret langs alle mulige veje fra toppunktet t til s . Hver sådan sti skal have en fælles kant med den givne sektion. Da det for hver kant af sektionen er umuligt at overføre "belastningen" mere end dens bæreevne, er summen af alle belastninger derfor mindre end eller lig med summen af alle bæreevnerne af kanterne af denne sektion. Påstanden er blevet bevist.

Det følger heraf, at ethvert flow er mindre end eller lig med værdien af minimumssektionen, og derfor er det maksimale flow mindre end eller lig med værdien af minimumssektionen.

Ford-Fulkerson algoritmen til at finde det maksimale flow i en graf er baseret på denne sætning, den er også et bevis på nødvendigheden af denne sætning, det vil sige, den er konstruktiv.

Endnu et bevis (via forstærkning)

Lad os styrke Ford-Fulkerson-sætningen som følger. For et netværk med et flow f, vil vi bevise ækvivalensen af følgende tre fakta på én gang: $G(V,E)$

1° Flow f maksimum

2° Kapaciteten af minimum cut er lig med værdien af flow f

3° Der er ingen komplementær sti i grafen $G$

1° → 3°. Hvis vi antager det modsatte, får vi modsigelsen beskrevet i informationen om den komplementære vej i transportgrafen .

3° → 2°. Det er indlysende, at værdien af flowet f ikke overstiger kapaciteten af minimumsskæringen . Lad . Overvej derefter et snit, hvor sættet indeholder alle hjørner, undtagen . Så er dens gennemløb ikke mindre end gennemløbet af minimumsskæringen, som igen er større end værdien af flowet f. Derfor er der en retning fra til , sådan at . Lad os nu tage alle disse og flytte dem til . Efter at have overvejet det resulterende snit, bemærker vi, at dets gennemløb også er større end flowværdien. Vi øger sættet igen og gør det indtil kun toppunktet er tilbage i sættet . Det vil også være den første top på den vej, vi skaber. Nu ser vi på hvilket par vi valgte sidste træk. Lad det være et par . Derefter tilføjer vi et toppunkt til stien . Dernæst ser vi i et par med hvilket toppunkt toppunktet var i første omgang . Lad det . Så videre til stien tilføjer vi toppunktet . Det gør vi indtil vi når toppen . Men ved konstruktion er denne vej residual, hvilket modsiger antagelsen. $(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 allerede nævnt er det indlysende, at værdien af ethvert flow ikke overstiger gennemløbet af minimumsskæringen, og værdien af vores flow er ens. Så er værdien af flowet ikke mindre end værdien af ethvert andet flow i vores netværk, det vil sige flowet er maksimalt. $f$ $f$ $f$

Dette bevis er godt, fordi det ikke bruger en kompleks algoritme til at finde det maksimale flow i et vilkårligt transportnetværk.

Eksempel

Til højre er et netværk med 6 toppunkter , og det samlede flow fra kilde til dræn er 5. Dette flow er maksimum for dette netværk. $V = \{s,o,p,q,r,t\}$ $s$ $t$

I dette netværk er 2 minimale nedskæringer mulige:

Indsnit	Flyde
$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 for programmører . - 3. - Sankt Petersborg. : Peter , 2009. - S. 277 -279. — 384 s. - ISBN 978-5-91180-759-7 .

Ford-Fulkerson teorem

Endnu et bevis (via forstærkning)

Eksempel

Litteratur

Links