5.3.1. Stabilirea sarcinii de determinare a debitului maxim într-o rețea de comunicații
Să se proiecteze rețeaua de comunicații. La proiectare, sunt furnizate un set de surse de informație S și un set de destinatari de informație T. De obicei, aceste seturi se intersectează sau pot fi identice cu S = T. adică, nodul sursă poate fi, de asemenea, un nod de destinație. Fiecare nod al setului S generează un flux de informații care trebuie transmise către nodurile T. set Ramurile graficului poate avea o lățime de bandă predeterminată cu (u, v), între fiecare pereche de noduri u și v. sau poate fi necesar să se determine cantitatea de producție a fiecărei ramuri. Transmiterea unei ramuri (margine) poate fi considerată ca fiind rata maximă de transfer a informațiilor de-a lungul acestei ramuri.
Având în vedere topologie de rețea, adică set de potrivire de noduri și ramuri, ramurile date de ponderare matrice A [u, v], în care greutățile realizează lățimea de bandă a fiecărei ramuri.
Ce sarcini pot fi rezolvate cu aceste date inițiale? Evident, este posibil să identificăm un set de noduri conexe. Se pot găsi cele mai scurte căi între toate perechile de vârfuri. În cele din urmă, puteți găsi toate căile dintre vârfurile s și t. În acest caz, fiecare cale trebuie să fie diferită de cealaltă, cel puțin o ramură sau un nod. Cu toate acestea, decizia de oricare dintre aceste sarcini sălcii nu ne va permite să răspundă la întrebarea - care este cantitatea maximă de informații pe unitatea de timp poate fi transmis de la nodul s la nodul T. sau din grupul de noduri din setul S la grupul de noduri din set. T. rezolva problemele menționate mai sus nu ajuta și de a rezolva problema inversă - cât de mult și ce fel de largime necesare sucursale pentru a sări peste toate fluxurile de informații dintre set S de noduri și o multitudine de noduri de T. O astfel de problemă, modul de a rețelelor reale, și nu funcționează (nu permite dimensiunea sarcinile și incertitudinea datelor de intrare).
Pentru a formula problema, formalizăm câteva concepte. Se atribuie fiecărei ramuri (u, v) o anumită greutate f (u, v), numită fluxul de la u la v. Valoarea debitului în ramură (u, v) poate fi considerată ca fiind viteza la care se transmite informația în această ramură.
Apoi, o cantitate numită divergența fluxului f la punctul v
unde Σf (v, u) este fluxul care părăsește vârful v. Σf (u, v) - fluxul care intră în vârful v, determină cantitatea de flux care părăsește vârful u.
Această valoare poate fi negativă (atunci când v vine mai mult decât ieșim), pozitiv (când v ieșim mai mult decât intră) și este 0. Acest ultim caz ne va interesa mai mult. Acest lucru înseamnă că fluxul nu se acumulează și nu apare în niciunul dintre noduri, cu excepția s și t.
Printr-un flux de la s la t inseamna o functie pentru care conditii
Ce flux poate fi transferat de la s la t prin aceste ramuri? Evident, având în vedere că ramurile sunt orientate
adică va fi egal cu suma capacității ramurilor care intră în secțiune.
Sub secțiunea rețelei R (A), AV corespunzătoare (subsetul V), A ≠ V. A ≠ 0. adică mulțimea de arce (u, v) astfel încât (u, v) W. uA și vV \ A.
Pentru un flux arbitrar f în rețea, curgerea prin tăiere este determinată într-un mod evident
Apoi, dacă presupunem că sA. și tV \ A. atunci fluxul de la s la t este definit ca
Introducem noțiunea de reducere minimă. Sub separarea minimă s și t. ne referim la o tăietură arbitrară R (A), sA și tV \ A cu o capacitate minimă.
Un exemplu. Formăm teorema clasică a teoriei fluxurilor în rețele. Această teoremă privind fluxul maxim și tăierea minimă:
Valoarea fiecărui flux de la s la t. nu depășește cantitatea de tăiere minimă și există un debit care atinge această valoare.
Fluxul maxim de rețea
Toți algoritmii cunoscuți pentru construirea debitului maxim se bazează pe o creștere secvențială a debitului, iar modificarea debitului, mărind magnitudinea sa, se bazează adesea pe metoda de creștere a lanțurilor (sau a căilor de creștere).
Introducem o serie de concepte care vor fi necesare pentru prezentarea ulterioară a materialului.
Spunem că arcul m al rețelei G este un arc admisibil de la u la v în raport cu fluxul f. dacă
Articole similare
Trimiteți-le prietenilor: