Teorema Ford-Fulkerson

Teorema Ford - Fulkerson este o teoremă de curgere maximă a graficului strâns legată de teorema lui Menger .

Sună așa: valoarea debitului maxim din graficul traseului este egală cu valoarea debitului tăieturii sale minime .

Suficiență: orice flux între vârfurile t și s este mai mic sau egal cu valoarea oricărei tăieturi . Lăsați să curgă și o secțiune. Valoarea acestui flux este suma valorilor „marfurilor” transportate de-a lungul tuturor căilor posibile de la vârful t la s . Fiecare astfel de cale trebuie să aibă o margine comună cu secțiunea dată. Deoarece pentru fiecare margine a secțiunii este imposibil să transferați „sarcina” mai mult decât capacitatea de transport, prin urmare, suma tuturor sarcinilor este mai mică sau egală cu suma tuturor capacităților de transport ale marginilor acestei secțiuni. Afirmația a fost dovedită.

Rezultă că orice debit este mai mic sau egal cu valoarea secțiunii minime și, prin urmare, debitul maxim este mai mic sau egal cu valoarea secțiunii minime.

Algoritmul Ford-Fulkerson pentru găsirea debitului maxim într-un grafic se bazează pe această teoremă, este și o dovadă a necesității acestei teoreme, adică este constructivă.

O altă dovadă (prin amplificare)

Să întărim teorema Ford-Fulkerson după cum urmează. Pentru o rețea cu un flux f, vom demonstra simultan echivalența următoarelor trei fapte: $G(V,E)$

1° Debit f maxim

2° Capacitatea tăierii minime este egală cu valoarea debitului f

3° Nu există o cale complementară în grafic $G$

1° → 3°. Presupunând contrariul, obținem contradicția descrisă în informațiile despre calea complementară din graficul de transport .

3° → 2°. Este evident că valoarea debitului f nu depăşeşte capacitatea de tăiere minimă . Lasă . Apoi luați în considerare o tăietură în care mulțimea conține toate vârfurile, cu excepția . Atunci debitul său nu este mai mic decât debitul tăieturii minime, care, la rândul său, este mai mare decât valoarea debitului f. Prin urmare, există o direcție de la la , astfel încât . Acum să luăm toate acestea și să le mutăm în . Luând în considerare tăietura rezultată, observăm că debitul său este, de asemenea, mai mare decât valoarea debitului. Mărim din nou setul și facem asta până când doar vârful rămâne în mulțime . Va fi, de asemenea, primul vârf din calea pe care o creăm. Acum ne uităm la ce pereche am ales ultima mișcare. Să fie un cuplu . Apoi adăugăm un vârf la cale . În continuare, ne uităm într-o pereche cu care vârf a fost vârful pe primul loc . Lasă-l . Apoi mai departe de cale adăugăm vârful . Facem asta până ajungem în vârf . Cu toate acestea, prin construcție, această cale este reziduală, ceea ce contrazice presupunerea. $(SF)$ $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°. După cum sa menționat deja, este evident că valoarea oricărui debit nu depășește debitul tăieturii minime, iar valoarea debitului nostru este egală. Atunci valoarea debitului nu este mai mică decât valoarea oricărui alt flux din rețeaua noastră, adică debitul este maxim. $f$ $f$ $f$

Această dovadă este bună deoarece nu folosește un algoritm complex pentru găsirea debitului maxim într-o rețea de transport arbitrară.

Exemplu

În dreapta este o rețea cu 6 vârfuri , iar debitul total de la sursă la scurgere este de 5. Acest debit este maximul pentru această rețea. $V = \{s,o,p,q,r,t\}$ $s$ $t$

În această rețea, sunt posibile 2 reduceri minime:

Incizie	curgere
$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$

Literatură

Novikov F. A. Matematică discretă pentru programatori . - al 3-lea. - Sankt Petersburg. : Peter , 2009. - S. 277 -279. — 384 p. - ISBN 978-5-91180-759-7 .

Link -uri

Algoritmul Ford-Fulkerson la algolist.manual.ru.
Rețele, fluxuri în rețele. Teorema Ford-Fulkerson pe Mini-Soft.ru