Luați în considerare sarcina de a determina fluxul maxim dintre nodurile dedicate ale unei rețele conectate. Fiecare arc al rețelei are debite în ambele direcții, care determină cantitatea maximă de curgere care trece prin acest arc. Un arc orientat (unilateral) corespunde unei transferări zero în direcția interzisă.
Lățimea de bandă a rețelei Cij poate fi reprezentată într-o formă de matrice.
Etapa 1:
Găsiți obiectivul care conectează sursa S și chiuveta t. pe care debitul are o valoare pozitivă. În direcția S → t. Dacă nu există acest lucru, treceți la pasul 3. În caz contrar, mergeți la pasul 2.
Fie () capacitatea arcurilor lanțului (S, t) în direcția S → t (t → S).
Matricea lățimii de bandă C = [Cij] se modifică după cum urmează:
a) scade # 1012; din toate;
b) adăugați # 1012; pentru toți.
Înlocuiți matricea curentă C cu cea nou obținută și treceți la pasul 1. Funcționarea (a) face posibilă utilizarea capacității rămase a arcurilor lanțului selectat în direcția S → t.
Operarea (b) restabilește lățimea de bandă inițială a rețelei, deoarece Reducerea debitului arcului într-o singură direcție poate fi considerată ca o creștere a debitului său în direcția opusă.
Găsiți debitul maxim în rețea.
Fie C = [Cij] matricea inițială a tranzitelor.
C * = [C * ij] este ultima matrice obținută ca urmare a modificării matricei inițiale (etapele 1 și 2).
Debitul optim X = [xij] în arce este dat de:
Debitul maxim de la S la t este:
Exemplu: determinați debitul maxim într-un grafic
Ca lanț inițial, alegem S → 1 → 4 → t. Apoi celulele (S, 1), (1,4), (4, t) sunt marcate cu semnul (-), iar celulele (1, S), (4,1), t, 4 sunt marcate cu semnul (+).
Debitul maxim pentru acest lanț este
Puteți selecta diferite circuite sursă. O alegere bună ar trebui să dea cea mai mare valoare # 1012; Dar există multe opțiuni pentru astfel de lanțuri. La programare, este convenabil să determinați lanțul direct de la matricea C, începând cu prima linie a șirului S și selectând nodul următor printre cele care sunt conectate la S prin fluxul pozitiv. Apoi, este considerat rândul corespunzător nodului selectat și este selectat următorul nod conectat la arcul pozitiv anterior. Procesul continuă până atunci. până când se ajunge la nodul t.
Corectăm matricea C, scăzând # 1012; = 5 dintre toate elementele marcate (-) și adăugarea tuturor elementelor care au semnul (+). Avem o nouă matrice.
Acțiuni similare se efectuează la iterații ulterioare.
Alegem un lanț (S → 3 → 2 → t)
# 1012; = min = 10 Corectăm matricea C
Alegem un lanț (S → 1 → 3 → 4 → t)
# 1012; = min = 5 Corectăm matricea C
Alegem un lanț (S → 4 → t)
# 1012; = min = 3 Corectăm matricea C
Alegem un lanț (S → 3 → t)
# 1012; = min = 2 Corectăm matricea C
Între S și t este imposibil să se construiască un lanț, deoarece toate elementele din coloana t sunt egale cu zero. Astfel, obținem matricea C *
Construim matricea X. Elementele negative din matrice sunt înlocuite cu zerouri.
Σ # 1012; = 5 + 10 + 5 + 3 + 2 = 25
Din punct de vedere grafic, soluția este reprezentată de un grafic:
Articole similare
Trimiteți-le prietenilor: