Problemă de debit maxim - Maximum flow problem

Rețea de flux pentru problemă: Fiecare om (r i ) este dispus să adopte o pisică (w i 1) și / sau un câine (w i 2). Cu toate acestea, fiecare animal de companie (p i ) are o preferință doar pentru un subset de oameni. Găsiți orice potrivire a animalelor de companie cu oamenii, astfel încât numărul maxim de animale de companie să fie adoptat de unul dintre oamenii săi preferați.

În teoria optimizării , problemele de debit maxim implică găsirea unui flux fezabil printr-o rețea de flux care obține debitul maxim posibil.

Problema debitului maxim poate fi văzută ca un caz special al problemelor de flux de rețea mai complexe, cum ar fi problema circulației . Valoarea maximă a unui debit st (adică, debitul de la sursa s la scufundarea t) este egală cu capacitatea minimă a unei tăieturi de st (de exemplu, tăierea s de la t) în rețea, așa cum se menționează în debitul maxim min. teorema de tăiere .

Istorie

Problema debitului maxim a fost formulată pentru prima dată în 1954 de TE Harris și FS Ross ca un model simplificat al fluxului de trafic feroviar sovietic.

În 1955, Lester R. Ford, Jr. și Delbert R. Fulkerson au creat primul algoritm cunoscut, algoritmul Ford – Fulkerson . În lucrarea lor din 1955, Ford și Fulkerson au scris că problema lui Harris și Ross este formulată după cum urmează (vezi p. 5):

Luați în considerare o rețea feroviară care conectează două orașe prin intermediul unui număr de orașe intermediare, în care fiecare legătură a rețelei are un număr atribuit care reprezintă capacitatea sa. Presupunând o stare de echilibru, găsiți un flux maxim dintr-un oraș dat în celălalt.

În cartea lor Flows in Network , în 1962, Ford și Fulkerson au scris:

A fost pusă autorilor în primăvara anului 1955 de TE Harris, care, împreună cu generalul FS Ross (Ret.), A formulat un model simplificat al fluxului de trafic feroviar și a identificat această problemă specială ca fiind cea centrală sugerată de modelul [11].

unde [11] se referă la raportul secret din 1955 Fundamentele unei metode pentru evaluarea capacităților nete feroviare de Harris și Ross (vezi p. 5).

De-a lungul anilor, au fost descoperite diferite soluții îmbunătățite la problema debitului maxim, în special cel mai scurt algoritm de cale augmentantă a lui Edmonds și Karp și în mod independent Dinitz; algoritmul de blocare a fluxului din Dinitz; algoritmul push-reetichetat de Goldberg și Tarjan ; și algoritmul de flux de blocare binar al lui Goldberg și Rao. Algoritmii lui Sherman și Kelner, Lee, Orecchia și, respectiv, Sidford găsesc un debit maxim aproximativ optim, dar funcționează numai în grafice nedirecționate.

În 2013, James B. Orlin a publicat o lucrare care descrie un algoritm. ${\ displaystyle O (| V || E |)}$

Definiție

O rețea de flux, cu sursă s și chiuvetă t . Numerele de lângă margine sunt capacitățile.

Mai întâi stabilim o anumită notație:

• Fie o rețea cu sursa și respectiv chiuveta .${\ displaystyle N = (V, E)}$${\ displaystyle s, t \ in V}$${\ displaystyle N}$
• Dacă funcția este pe marginile, atunci valoarea sa este notată cu sau${\ displaystyle g}$${\ displaystyle N}$${\ displaystyle (u, v) \ în E}$${\ displaystyle g_ {uv}}$${\ displaystyle g (u, v).}$

Definiție. Capacitatea unei margini este cantitatea maximă de curgere care poate trece printr - o margine. În mod formal este o hartă${\ displaystyle c: E \ to \ mathbb {R} ^ {+}.}$

Definiție. Un flux este o hartă care satisface următoarele: ${\ displaystyle f: E \ to \ mathbb {R}}$

• Constrângerea capacității . Fluxul unei margini nu poate depăși capacitatea sa, cu alte cuvinte: pentru toți${\ displaystyle f_ {uv} \ leq c_ {uv}}$${\ displaystyle (u, v) \ în E.}$
• Conservarea fluxurilor. Suma fluxurilor care intră într-un nod trebuie să fie egală cu suma fluxurilor care ies din acel nod, cu excepția sursei și a chiuvetei. Sau:

${\ displaystyle \ forall v \ in V \ setminus \ {s, t \}: \ quad \ sum _ {u: (u, v) \ in E} f_ {uv} = \ sum _ {u: (v, u) \ în E} f_ {vu}.}$

Observație . Debitele sunt înclinate simetric: pentru toți${\ displaystyle f_ {uv} = - f_ {vu}}$${\ displaystyle (u, v) \ în E.}$

Definiție. Valoarea debitului este cantitatea de curgere care trece de la sursa la chiuveta. În mod formal pentru un flux este dat de: ${\ displaystyle f: E \ to \ mathbb {R} ^ {+}}$

${\ displaystyle | f | = \ sum _ {v: (s, v) \ în E} f_ {sv}.}$

Definiție. Problema debitului maxim este de a direcționa cât mai mult debit posibil de la sursă la chiuvetă, cu alte cuvinte găsiți debitul cu valoare maximă. ${\ displaystyle f _ {\ textrm {max}}}$

Rețineți că pot exista mai multe fluxuri maxime și dacă sunt permise valori arbitrare reale (sau chiar arbitrare raționale) ale fluxului (în locul doar întregi), există fie exact un flux maxim, fie infinit, deoarece există infinit de multe combinații liniare de debitele maxime de bază. Cu alte cuvinte, dacă trimitem unități de debit pe margine într-un debit maxim și unități de debit pe un alt debit maxim, atunci pentru fiecare putem trimite unități și putem direcționa debitul pe marginile rămase în consecință, pentru a obține un alt debit maxim. Dacă valorile fluxului pot fi orice numere reale sau raționale, atunci există infinit de multe astfel de valori pentru fiecare pereche . ${\ displaystyle x}$${\ displaystyle u}$${\ displaystyle y> x}$${\ displaystyle u}$${\ displaystyle \ Delta \ în [0, yx]}$${\ displaystyle x + \ Delta}$${\ displaystyle u}$${\ displaystyle \ Delta}$${\ displaystyle x, y}$

Algoritmi

Următorul tabel listează algoritmi pentru rezolvarea problemei debitului maxim.

Metodă	Complexitate	Descriere
Programare liniară		Constrângeri date de definiția unui flux legal . Vezi aici programul liniar .
Algoritmul Ford – Fulkerson	${\ displaystyle O (E \ vert f_ {max} \ vert)}$	Atâta timp cât există o cale deschisă prin graficul rezidual, trimiteți minimul capacităților reziduale pe cale. Se garantează că algoritmul se termină numai dacă toate greutățile sunt raționale , caz în care cantitatea adăugată fluxului în fiecare etapă este cel puțin cel mai mare divizor comun al greutăților. În caz contrar, este posibil ca algoritmul să nu convergă la valoarea maximă. Cu toate acestea, dacă algoritmul se termină, este garantat să găsească valoarea maximă.
Algoritm Edmonds – Karp	${\ displaystyle O (VE ^ {2})}$	O specializare în Ford – Fulkerson, găsirea căilor de creștere cu căutarea în primul rând .
Algoritmul lui Dinic	${\ displaystyle O (V ^ {2} E)}$	În fiecare fază, algoritmii construiesc un grafic stratificat cu o căutare pe lățime pe graficul rezidual . Debitul maxim într-un grafic stratificat poate fi calculat în timp, iar numărul maxim de faze este . În rețelele cu capacități unitare, algoritmul lui Dinic se termină în timp. ${\ displaystyle O (VE)}$${\ displaystyle V-1}$${\ displaystyle O (\ min \ {V ^ {2/3}, E ^ {1/2} \} E)}$
Algoritm MKM (Malhotra, Kumar, Maheshwari)	${\ displaystyle O (V ^ {3})}$	O modificare a algoritmului Dinic cu o abordare diferită a construirii fluxurilor de blocare. Consultați hârtia originală .
Algoritmul lui Dinic cu copaci dinamici	${\ displaystyle O (VE \ log V)}$	Structura de date a arborilor dinamici accelerează calculul fluxului maxim în graficul stratificat la . ${\ displaystyle O (VE \ log V)}$
Algoritm general push-relabel	${\ displaystyle O (V ^ {2} E)}$	Algoritmul push relabel menține o preflow, adică o funcție de flux cu posibilitatea de exces în vârfuri. Algoritmul rulează în timp ce există un vârf cu exces pozitiv, adică un vârf activ în grafic. Operația de împingere crește debitul pe o margine reziduală și o funcție de înălțime pe vârfurile de control prin care pot fi împinse marginile reziduale. Funcția de înălțime este modificată prin operația de reetichetare. Definițiile adecvate ale acestor operațiuni garantează că funcția de flux rezultată este un debit maxim.
Algoritm push-relabel cu regulă de selecție vârf FIFO	${\ displaystyle O (V ^ {3})}$	Varianta algoritmului Push-relabel care selectează întotdeauna cel mai recent vârf activ și efectuează operații de împingere în timp ce excesul este pozitiv și există margini reziduale admisibile din acest vârf.
Algoritm push-relabel cu regulă de selecție a vârfului la distanță maximă	${\ displaystyle O (V ^ {2} {\ sqrt {E}})}$	Varianta algoritmului Push-relabel care selectează întotdeauna cel mai îndepărtat vârf din sau (adică cel mai înalt vârf al etichetei), dar în caz contrar procedează ca algoritm FIFO. ${\ displaystyle s}$${\ displaystyle t}$
Algoritm push-relabel cu arbori dinamici	${\ displaystyle O \ left (VE \ log {\ frac {V ^ {2}} {E}} \ right)}$	Algoritmul construiește arbori de dimensiuni limitate pe graficul rezidual cu privire la funcția de înălțime. Acești copaci oferă operații de împingere pe mai multe niveluri, adică împingând de-a lungul unei căi de saturare întregi în loc de o singură margine.
Algoritmul lui KRT (King, Rao, Tarjan)	${\ displaystyle O \ left (VE \ log _ {\ frac {E} {V \ log V}} V \ right)}$
Algoritm de flux de blocare binară	${\ displaystyle O \ left (E \ cdot \ min \ {V ^ {2/3}, E ^ {1/2} \} \ cdot \ log {\ frac {V ^ {2}} {E}} \ cdot \ log U \ right)}$	Valoarea U corespunde capacității maxime a rețelei.
Algoritmul lui James B Orlin + KRT (King, Rao, Tarjan)	${\ displaystyle O (VE)}$	Algoritmul lui Orlin rezolvă fluxul maxim în timp, în timp ce KRT îl rezolvă pentru . ${\ displaystyle O (VE)}$${\ displaystyle E \ leq O (V ^ {{\ frac {16} {15}} - \ epsilon})}$${\ displaystyle O (VE)}$${\ displaystyle E> V ^ {1+ \ epsilon}}$
Algoritmul Kathuria-Liu-Sidford	${\ displaystyle E ^ {4/3 + o (1)} U ^ {1/3}}$	Metode de punct interior și creșterea marginilor folosind fluxurile -normale. Se bazează pe algoritmul anterior al lui Madry, care a realizat runtime . ${\ displaystyle \ ell _ {p}}$${\ displaystyle {\ tilde {O}} (E ^ {10/7} U ^ {1/7})}$
Algoritmul BLNPSSSW / BLLSSSW	${\ displaystyle {\ tilde {O}} ((E + V ^ {3/2}) \ log U)}$	Metode de punct interior și întreținerea dinamică a debitelor electrice cu descompuneri de expansiune.
Algoritm Gao-Liu-Peng	${\ displaystyle {\ tilde {O}} (E ^ {{\ frac {3} {2}} - {\ frac {1} {328}}} \ log U)}$	Algoritmul lui Gao, Liu și Peng se învârte în jurul valorii de menținere dinamică a fluxurilor electrice crescătoare la baza algoritmului bazat pe metoda punctului interior din [Mądry JACM '16]. Acest lucru presupune proiectarea structurilor de date care, în setări limitate, returnează muchiile cu energie electrică mare într-un grafic supus actualizărilor de rezistență.

Pentru algoritmi suplimentari, consultați Goldberg și Tarjan (1988) .

Teorema fluxului integral

Teorema fluxului integral afirmă că

Dacă fiecare margine dintr-o rețea de flux are capacitate integrală, atunci există un debit maxim integral.

Afirmația nu este doar că valoarea debitului este un număr întreg, care rezultă direct din teorema minimă a debitului maxim , dar că debitul pe fiecare margine este integral. Acest lucru este crucial pentru multe aplicații combinatorii (vezi mai jos), în care fluxul peste o margine poate codifica dacă elementul corespunzător acelei margini trebuie să fie inclus în setul căutat sau nu.

Cerere

Problemă de debit maxim multi-sursă multi-sursă

Fig. 4.1.1. Transformarea unei probleme de debit maxim cu mai multe surse multiple într-o problemă de debit maxim cu o singură sursă cu o singură chiuvetă

Având în vedere o rețea cu un set de surse și un set de chiuvete în loc de o singură sursă și o singură chiuvetă, trebuie să găsim debitul maxim . Putem transforma problema multi-sursă multi-chiuvetă într-o problemă de debit maxim adăugând o sursă consolidată care se conectează la fiecare vârf în și o chiuvetă consolidată conectată de fiecare vârf în (cunoscută și ca supersursă și supersink ) cu capacitate infinită pe fiecare margine ( Vezi Fig. 4.1.1.). ${\ displaystyle N = (V, E)}$${\ displaystyle S = \ {s_ {1}, \ ldots, s_ {n} \}}$${\ displaystyle T = \ {t_ {1}, \ ldots, t_ {m} \}}$${\ displaystyle N}$${\ displaystyle S}$${\ displaystyle T}$

Cardinalitate maximă potrivire bipartită

Fig. 4.3.1. Transformarea unei probleme maxime de potrivire bipartită într-o problemă de flux maxim

Având în vedere un grafic bipartit , trebuie să găsim o potrivire cardinală maximă în , adică o potrivire care conține cel mai mare număr posibil de margini. Această problemă poate fi transformată într-o problemă de flux maxim prin construirea unei rețele , unde ${\ displaystyle G = (X \ cup Y, E)}$${\ displaystyle G}$${\ displaystyle N = (X \ cup Y \ cup \ {s, t \}, E ')}$

1. ${\ displaystyle E '}$conține marginile în direcționate de la la .${\ displaystyle G}$${\ displaystyle X}$${\ displaystyle Y}$
2. ${\ displaystyle (s, x) \ în E '}$pentru fiecare și pentru fiecare .${\ displaystyle x \ în X}$${\ displaystyle (y, t) \ în E '}$${\ displaystyle y \ in Y}$
3. ${\ displaystyle c (e) = 1}$pentru fiecare (Vezi Fig. 4.3.1).${\ displaystyle e \ in E '}$

Apoi, valoarea debitului maxim în este egală cu dimensiunea potrivirii maxime în și o potrivire cardinală maximă poate fi găsită luând acele margini care au debit într-un debit maxim integral. ${\ displaystyle N}$${\ displaystyle G}$${\ displaystyle 1}$

Acoperirea minimă a traseului în graficul aciclic direcționat

Având în vedere un grafic aciclic direcționat , trebuie să găsim numărul minim de căi disjuncte de vârf pentru a acoperi fiecare vârf în . Putem construi un grafic bipartit din , unde ${\ displaystyle G = (V, E)}$${\ displaystyle V}$${\ displaystyle G '= (V _ {\ textrm {out}} \ cup V _ {\ textrm {in}}, E')}$${\ displaystyle G}$

1. ${\ displaystyle V _ {\ textrm {out}} = \ {v _ {\ textrm {out}} \ mid v \ in V \ land v {\ text {are margine de ieșire}} \}}$
2. ${\ displaystyle V _ {\ textrm {in}} = \ {v _ {\ textrm {in}} \ mid v \ in V \ land v {\ text {are margini de intrare}} \}}$
3. ${\ displaystyle E '= \ {(u _ {\ textrm {out}}, v _ {\ textrm {in}}) \ in V_ {out} \ times V_ {in} \ mid (u, v) \ in E \ }}$.

Apoi, se poate arăta că are o potrivire de dimensiune dacă și numai dacă are o acoperire de cale de vârf-disjuns de margini și căi care conțin , unde este numărul de vârfuri în . Prin urmare, problema poate fi rezolvată găsind în schimb cardinalitatea maximă potrivită . ${\ displaystyle G '}$${\ displaystyle M}$${\ displaystyle m}$${\ displaystyle G}$${\ displaystyle C}$${\ displaystyle m}$${\ displaystyle nm}$${\ displaystyle n}$${\ displaystyle G}$${\ displaystyle G '}$

Intuitiv, dacă două vârfuri sunt potrivite , atunci marginea este conținută în . În mod clar, numărul de margini este . Pentru a vedea că este vertex-disjunct, luați în considerare următoarele: ${\ displaystyle u _ {\ mathrm {out}}, v _ {\ mathrm {in}}}$${\ displaystyle M}$${\ displaystyle (u, v)}$${\ displaystyle C}$${\ displaystyle C}$${\ displaystyle m}$${\ displaystyle C}$

1. Fiecare nod in poate consta fie nepereche în , caz în care nu există margini care ies in ; sau poate fi compensată , în cazul în care există exact o margine lăsând în . În ambele cazuri, nu mai mult de o margine lasă niciun vârf înăuntru .${\ displaystyle v _ {\ textrm {out}}}$${\ displaystyle G '}$${\ displaystyle M}$${\ displaystyle v}$${\ displaystyle C}$${\ displaystyle v}$${\ displaystyle C}$${\ displaystyle v}$${\ displaystyle C}$
2. În mod similar pentru fiecare vârf din - dacă este potrivită, există o singură margine de intrare în ; altfel nu are margini de intrare în .${\ displaystyle v _ {\ textrm {in}}}$${\ displaystyle G '}$${\ displaystyle v}$${\ displaystyle C}$${\ displaystyle v}$${\ displaystyle C}$

Astfel, niciun vârf nu are două margini de intrare sau două ieșiri în interior , ceea ce înseamnă că toate căile sunt verticale-disjuncte. ${\ displaystyle C}$${\ displaystyle C}$

Pentru a arăta că capacul are dimensiune , începem cu un capac gol și îl construim incremental. Pentru a adăuga un vârf la capac, îl putem adăuga fie la o cale existentă, fie putem crea o nouă cale de lungime zero începând de la acel vârf. Primul caz se aplică ori de câte ori oricare dintre căile din capac începe sau când o cale se termină la . Ultimul caz este întotdeauna aplicabil. În primul caz, numărul total de margini din capac este mărit cu 1 și numărul de căi rămâne același; în acest din urmă caz ​​numărul de căi este mărit, iar numărul de muchii rămâne același. Acum este clar că după acoperirea tuturor vârfurilor, suma numărului de căi și margini din capac este . Prin urmare, dacă numărul de margini din capac este , numărul de căi este . ${\ displaystyle C}$${\ displaystyle nm}$${\ displaystyle u}$${\ displaystyle (u, v) \ în E}$${\ displaystyle v}$${\ displaystyle (v, u) \ în E}$${\ displaystyle v}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle nm}$

Debit maxim cu capacități de vârf

Fig. 4.4.1. Transformarea unei probleme de debit maxim cu constrângerea capacităților de vârf în problema debitului maxim original prin împărțirea nodului

Să fie o rețea. Să presupunem că există capacitate la fiecare nod în plus față de capacitatea de margine, adică o mapare astfel încât fluxul să satisfacă nu numai constrângerea capacității și conservarea fluxurilor, ci și constrângerea capacității vertexului ${\ displaystyle N = (V, E)}$${\ displaystyle c: V \ to \ mathbb {R} ^ {+},}$${\ displaystyle f}$

${\ displaystyle \ sum _ {i \ in V} f_ {iv} \ leq c (v) \ qquad \ forall v \ in V \ backslash \ {s, t \}.}$

Cu alte cuvinte, cantitatea de curgere care trece printr-un vârf nu poate depăși capacitatea acestuia. Pentru a găsi debitul maxim , putem transforma problema în problema debitului maxim în sensul inițial prin extindere . În primul rând, fiecare este înlocuită de și , unde este conectată de marginile care intră și sunt conectate la marginile care ies , apoi atribuiți capacitatea marginii de conectare și (a se vedea Fig. 4.4.1). În această rețea extinsă, constrângerea capacității vertexului este eliminată și, prin urmare, problema poate fi tratată ca problema originală a debitului maxim. ${\ displaystyle N}$${\ displaystyle N}$${\ displaystyle v \ in V}$${\ displaystyle v _ {\ text {in}}}$${\ displaystyle v _ {\ text {out}}}$${\ displaystyle v _ {\ text {in}}}$${\ displaystyle v}$${\ displaystyle v _ {\ text {out}}}$${\ displaystyle v}$${\ displaystyle c (v)}$${\ displaystyle v _ {\ text {in}}}$${\ displaystyle v _ {\ text {out}}}$

Numărul maxim de căi de la s la t

Având în vedere un grafic direcționat și două vârfuri și , trebuie să găsim numărul maxim de căi de la la . Această problemă are mai multe variante: ${\ displaystyle G = (V, E)}$${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle s}$${\ displaystyle t}$

1. Căile trebuie să fie separate de margine. Această problemă poate fi transformată într-o problemă de flux maxim prin construirea unei rețele din , cu și fiind sursa și respectiv chiuveta și atribuind fiecărei margini o capacitate de . În această rețea, debitul maxim este dacă există căi marginile-disjuncte. ${\ displaystyle N = (V, E)}$${\ displaystyle G}$${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle N}$${\ displaystyle 1}$${\ displaystyle k}$${\ displaystyle k}$

2. Căile trebuie să fie independente, adică vârf-disjunct (cu excepția și ). Putem construi o rețea de cu capacități Vertex, în cazul în care capacitățile tuturor nodurilor și toate marginile sunt . Atunci valoarea debitului maxim este egală cu numărul maxim de căi independente de la la . ${\ displaystyle s}$${\ displaystyle t}$${\ displaystyle N = (V, E)}$${\ displaystyle G}$${\ displaystyle 1}$${\ displaystyle s}$${\ displaystyle t}$

3. În afară de faptul că traseele sunt disjuntate la margini și / sau disjunctate la vârf, traseele au și o constrângere de lungime: numărăm numai căile a căror lungime este exactă sau cel mult . Cele mai multe variante ale acestei probleme sunt NP-complete, cu excepția valorilor mici ale . ${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle k}$

Problemă de închidere

O închidere a unui grafic direcționat este un set de noduri C , astfel încât să nu lase margini C . Problema închiderii este sarcina de a găsi închiderea cu greutate maximă sau cu greutate minimă într-un grafic direcționat pe vârf. Poate fi rezolvat în timp polinomial folosind o reducere la problema debitului maxim.

Aplicații din lumea reală

Eliminarea baseballului

Construirea fluxului de rețea pentru problema eliminării baseballului

În problema eliminării baseballului există n echipe care concurează într-o ligă. La o etapă specifică a sezonului ligii, w _i este numărul de victorii și r _i este numărul de jocuri rămase de jucat pentru echipa i iar r _ij este numărul de jocuri rămase împotriva echipei j . O echipă este eliminată dacă nu are nicio șansă să termine sezonul în primul rând. Sarcina problemei de eliminare a baseball-ului este de a determina ce echipe sunt eliminate la fiecare punct în timpul sezonului. Schwartz a propus o metodă care reduce această problemă la fluxul maxim de rețea. În această metodă se creează o rețea pentru a determina dacă echipa k este eliminată.

Fie G = ( V , E ) o rețea cu s , t ∈ V fiind sursa și respectiv chiuveta. Unul adaugă un nod de joc _ij - care reprezintă numărul de jocuri dintre aceste două echipe. De asemenea, adăugăm un nod de echipă pentru fiecare echipă și conectați fiecare nod joc { i , j } cu i < j la V , și se conectează fiecare dintre ele de la e de o margine cu o capacitate r _ij - care reprezintă numărul de piese între aceste două echipe. De asemenea, adăugăm un nod de echipă pentru fiecare echipă și conectăm fiecare nod de joc { i , j } cu două noduri de echipă i și j pentru a ne asigura că unul dintre ei câștigă. Nu trebuie să restricționați valoarea debitului pe aceste margini. În cele din urmă, marginile sunt realizate din echipa nodul i la nodul chiuveta t și capacitatea w _k + r _k - w _i este setat pentru a preveni echipa i să câștige mai mult decât w _k + r _k . Să fie S setul tuturor echipelor care participă la ligă și să

${\ displaystyle r (S - \ {k \}) = \ sum _ {i, j \ in \ {S - \ {k \} \} \ atop i <j} r_ {ij}}$.

În această metodă, se susține echipa k nu este eliminată dacă și numai dacă o valoare de curgere de dimensiuni r ( S - { k }) există în rețeaua G . În articolul menționat se demonstrează că această valoare a debitului este valoarea maximă a debitului de la s la t .

Programarea companiei aeriene

În industria companiilor aeriene, o problemă majoră o reprezintă programarea echipajelor de zbor. Problema de planificare a companiei aeriene poate fi considerată ca o aplicație a fluxului maxim extins de rețea. Introducerea acestei probleme este un set de zboruri F care conține informații despre unde și când fiecare zbor pleacă și ajunge. Într-o versiune a programării companiilor aeriene, scopul este de a produce un program fezabil cu cel mult k echipaje.

Pentru a rezolva această problemă, se folosește o variație a problemei de circulație numită circulație limitată, care este generalizarea problemelor de flux de rețea , cu constrângerea adăugată a unei limite inferioare pe fluxurile de margine.

Fie G = ( V , E ) o rețea cu s , t ∈ V ca sursă și nodurile chiuvetei. Pentru sursa și destinația fiecărui zbor i , se adaugă două noduri la V , nodul s _i ca sursă și nodul d _i ca nod de destinație al zborului i . Unul adaugă, de asemenea, următoarele margini la E :

1. O margine cu capacitatea [0, 1] între s și fiecare s _i .
2. O margine cu capacitatea [0, 1] între fiecare d _i și t .
3. O margine cu capacitatea [1, 1] între fiecare pereche de s _i și d _i .
4. O margine cu capacitate [0, 1] între fiecare d _i și s _j , dacă sursa s _j este accesibilă o cantitate rezonabilă de timp și costuri de destinația zborului i .
5. O margine cu capacitatea [0, ∞ ] între s și t .

În metoda menționată, se susține și se dovedește că găsirea unei valori a fluxului de k în G între s și t este egală cu găsirea unui program fezabil pentru setul de zbor F cu cel mult k echipaje.

O altă versiune a programării companiilor aeriene constă în găsirea echipajelor minime necesare pentru efectuarea tuturor zborurilor. În scopul de a găsi un răspuns la această problemă, un graf bipartit G“ = ( A ∪ B , E ) , se creează în cazul în care fiecare zbor are o copie în setul A și setul B . În cazul în care același plan se poate efectua de zbor j după zbor i , i ∈ A este conectat la j ∈ B . O potrivire în G ' induce un program pentru F și, evident, potrivirea maximă bipartită în acest grafic produce un program al companiei aeriene cu număr minim de echipaje. Așa cum este menționat în partea Aplicație a acestui articol, potrivirea bipartită a cardinalității maxime este o aplicație a problemei debitului maxim.

Problemă circulație-cerere

Există unele fabrici care produc mărfuri și unele sate în care mărfurile trebuie livrate. Acestea sunt conectate printr-o rețea de drumuri, fiecare drum având o capacitate c pentru mărfurile maxime care pot circula prin el. Problema este de a găsi dacă există o circulație care să satisfacă cererea. Această problemă poate fi transformată într-o problemă cu flux maxim.

1. Adăugați o sursă de nod s și adăugați - l la marginile de la fiecare nod din fabrică f _i cu capacitate p _i în cazul în care p _i este rata de producție a fabricii f _i .
2. Adăugați un nod chiuveta t și adăugați margini din toate satele v _i la t cu capacitatea d _i unde d _i este rata de cerere a satului v _i .

Fie G = ( V , E ) această nouă rețea. Există o circulație care satisface cererea dacă și numai dacă:

Valoarea maximă a debitului ( G ) .${\ displaystyle = \ sum _ {i \ in v} d_ {i}}$

Dacă există o circulație, examinarea soluției de debit maxim ar oferi răspunsul la cât de multe bunuri trebuie trimise pe un anumit drum pentru satisfacerea cererilor.

Problema poate fi extinsă prin adăugarea unei limite inferioare pe flux pe unele margini.

Segmentarea imaginii

Imagine sursă de dimensiune 8x8.

Rețea construită din bitmap. Sursa este în stânga, chiuveta în dreapta. Cu cât o margine este mai întunecată, cu atât este mai mare capacitatea sa. a _i este ridicat când pixelul este verde, b _i când pixelul nu este verde. Penalizarea p _ij sunt toate egale.

În cartea lor, Kleinberg și Tardos prezintă un algoritm pentru segmentarea unei imagini. Acestea prezintă un algoritm pentru a găsi fundalul și prim-planul într-o imagine. Mai precis, algoritmul ia o bitmap ca intrare modelată după cum urmează: a _i ≥ 0 este probabilitatea ca pixelul i să aparțină în prim plan, b _i ≥ 0 în probabilitatea ca pixelul i să aparțină în fundal, iar p _{ij să} fie penalizare dacă doi pixeli adiacenți i și j sunt plasați unul în prim-plan și celălalt în fundal. Scopul este de a găsi o partiție ( A , B ) a setului de pixeli care să maximizeze următoarea cantitate

${\ displaystyle q (A, B) = \ sum _ {i \ in A} a_ {i} + \ sum _ {i \ in B} b_ {i} - \ sum _ {\ begin {matrix} i, j {\ text {adjacent}} \\ | A \ cap \ {i, j \} | = 1 \ end {matrix}} p_ {ij}}$,

Într-adevăr, pentru pixelii din A (considerați ca prim-plan), obținem un _i ; pentru toți pixelii din B (considerați ca fundal), câștigăm b _i . Pe margine, între doi pixeli adiacenți i și j , pierdem p _ij . Este echivalent cu minimizarea cantității

${\ displaystyle q '(A, B) = \ sum _ {i \ in A} b_ {i} + \ sum _ {i \ in B} a_ {i} + \ sum _ {\ begin {matrix} i, j {\ text {adjacent}} \\ | A \ cap \ {i, j \} | = 1 \ end {matrix}} p_ {ij}}$

deoarece

${\ displaystyle q (A, B) = \ sum _ {i \ in A \ cup B} a_ {i} + \ sum _ {i \ in A \ cup B} b_ {i} -q '(A, B ).}$

Tăiere minimă afișată în rețea (triunghiuri VS cercuri).

Acum construim rețeaua ale cărei noduri sunt pixelul, plus o sursă și o chiuvetă, vezi Figura din dreapta. Conectăm sursa la pixelul i printr-o margine de greutate a _i . Conectăm pixelul i la chiuvetă printr-o margine de greutate b _i . Conectăm pixelul i la pixelul j cu greutatea p _ij . Acum, rămâne să calculăm o reducere minimă în acea rețea (sau echivalent un debit maxim). Ultima figură arată o reducere minimă.

Extensii

1. În problema debitului costului minim , fiecare margine ( u , v) are, de asemenea, un coeficient de cost a _uv în plus față de capacitatea sa. Dacă fluxul prin margine este f _uv , atunci costul total este un _uv f _uv . Este necesar să se găsească un flux de o dimensiune dată d , cu cel mai mic cost. În majoritatea variantelor, coeficienții de cost pot fi fie pozitivi, fie negativi. Există diferiți algoritmi de timp polinomial pentru această problemă.

2. Problema fluxului maxim poate fi mărită de constrângeri disjunctive : o constrângere disjunctivă negativă spune că o anumită pereche de muchii nu poate avea simultan un flux diferit de zero; o constrângere disjunctivă pozitivă spune că, într-o anumită pereche de margini, cel puțin una trebuie să aibă un flux diferit de zero. Cu constrângeri negative, problema devine puternic NP-hard chiar și pentru rețelele simple. Cu constrângeri pozitive, problema este polinomială dacă sunt permise fluxuri fracționate, dar poate fi puternic NP-hard atunci când fluxurile trebuie să fie integrale.

Referințe

Lecturi suplimentare

• Joseph Cheriyan și Kurt Mehlhorn (1999). „O analiză a regulii de selecție la cel mai înalt nivel în algoritmul de debit maxim preflow-push”. Scrisori de prelucrare a informațiilor . 69 (5): 239-242. CiteSeerX  10.1.1.42.8563 . doi : 10.1016 / S0020-0190 (99) 00019-8 .
• Daniel D. Sleator și Robert E. Tarjan (1983). „O structură de date pentru arborii dinamici” (PDF) . Journal of Computer and System Sciences . 26 (3): 362-391. doi : 10.1016 / 0022-0000 (83) 90006-5 . ISSN  0022-0000 .
• Eugene Lawler (2001). „4. Fluxuri de rețea”. Optimizare combinatorie: rețele și matroide . Dover. pp. 109–177. ISBN 978-0-486-41453-9.