Algoritmul de determinare a debitului maxim

Algoritmul de determinare a debitului maxim

Vom presupune ca exista in retea numai linii semiduplex, astfel incat fiecare linie va capata, pentru scurt timp, un sens de circulatie a informatiei (cazul liniilor duplex solutionandu-se analog prin inlocuirea fiecarei linii cu sens dublu din graf cu doua linii ce au sensuri diferite ). Arcele vor fi etichetate cu debitul efectiv.

O repartitie de debite este realizabila daca indeplineste urmatoarele conditii:

- nodul sursa sa nu aiba convergente ( informatia emisa de sursa);

- nodul terminal sa nu aiba divergente ( sa nu emita informatie );

- prin nici un arc sa nu treaca un debit mai mare decat capacitatea sa ( un debit mai mic se accepta );

- exceptand nodurile sursa si terminal, in oricare alt nod debitul total de intrare este egal cu debitul total de iesire.

- debitul care iese din sursa sa fie egal cu debitul care intra in nodul terminal.

Dam in cele ce urmeaza o versiune simplificata a unui algoritm care determina, intr-un graf orientat si ponderat dat, repartitia unui debit maxim intre o sursa si un terminal date ( Malhotra 1978 ).

Pentru exemplificarea algoritmului, se va lua ca exemplu o retea de canale duplex avand configuratia ca in graful urmator. Se va conveni reprezentarea fiecarei legaturi cu cate un singur arc prevazut in ambele sensuri.

Pmin=1 nref=B sau K,C,I d(DE)=4+1=5 d(EF)=4+1=5 d(CD)=4+1=5 d(BC)=4+1=5 d(IB)=0+1=1 d(KI)=0+1=1 d(JK)=2+1=3 d(AJ)=2+1=3

Pmin=4 nref=B d(DE)=4+0=4 d(EF)=4+0=4 d(CD)=4+0=4 d(BC)=4+0=4 d(AB)=2+4=6

(e)

Prin arc util orientat de la nodul X la nodul Y se intelege ca arcului respectiv i s-a alocat un debit de la X la Y, mai mic decat capacitatea lui sau ca i s-a alocat un anume debit de la Y la X. In ambele cazuri, debitul efectiv poate fi marit:

- in primul caz, prin adaugarea unui debit ( discret ) de la X la Y

- in al doilea caz, prin reducerea ( in sens algebric ) a unei parti din debitul ( direct ) de la X la Y cu o parte din debitul ( invers ) de la Y la X - operatie posibila atunci cand in retea exista o singura pereche sursa - terminal intre care se vehiculeaza informatia.

Astfel, referindu-ne la graful anterior, daca debitul din arcul CD este de cinci unitati, iar debitul arcului DC este de trei unitati, arcul CD poate fi considerat util, deoarece cele doua debite de sensuri opuse se pot reduce ( cu trei unitati ), avand ca efect obtinerea unui arc nesaturat.

Prima retea stratificata ce se obtine pornind de la graful din figura (a) este reprezentata in figura (b). In fiecare etapa de constituire a retelei stratificate se vor lua in consideratie doar acele arce care pornesc din stratul i si se duc in stratul i+1.

Urmatorul pas il constituie eliminarea ramurilor "moarte", adica a acelor traiectorii ce nu sfarsesc in nodul terminal. Astfel, in reteaua din figura (b), traiectoriile ABCD, ABGH, IK si AJK sunt ramuri "moarte".

Dupa inlaturarea nodurilor si arcelor din ramurile "moarte", fiecare nod ramas in reteaua stratificata va avea unul sau mai multe arce de iesire catre nodul terminal si unul sau mai multe arce de intrare venind de la nodul sursa.

In exemplul dat, doar traiectoria AILF ramane dupa eliminarea ramurilor moarte.

Urmatorul pas il constituie eliminarea pe rand a tuturor nodurilor din reteaua stratificata ramasa, pentru a afla cresterea potentiala de debit pe care o poate suporta. Pentru fiecare arc divergent ( fie el de la X la Y ) aceasta crestere este egala cu capacitatea arcului (XY) minus debitul direct alocat ( de la X la Y ) si plus debitul invers alocat ( de la Y la X ) - tina cont mereu ca debitul de iesire poate fi marit prin reducere cu debitul invers.

Observatie:

Algoritmul debuteaza cu debite egale cu capacitatea arcului sursa - terminal.

Potentialul total ( de crestere a debitului ) la iesire se defineste ca suma cresterilor potentiale de debite pe toate arcele care fac legatura cu stratul urmator. Analog se defineste si potentialul total (de crestere a debitului) la intrare.

Potentialul unui nod se defineste ca fiind valoarea minima dintre potentialele totale la intrare si la iesire ale acelui nod. Astfel, de exemplu, daca un nod are un potential la intrare egal cu patru unitati , iar la iesire un potential de sapte unitati, el are un potential de min(4,7) = 4 unitati, adica debitul prin el poate fi marit cu patru unitati. Referitor la reteaua din figura (b), aceasta are un potential la iesire (dinspre nodul A) egal cu trei unitati si un potential egal la iesire ( catre nodul L doar, deoarece arcul IK a fost inlaturat ) tot cu trei unitati, deci are un potential de trei unitati, nodul L va avea un potential egal cu min(3,5) = 3 unitati.

Nodul din reteaua stratificata care are cel mai mic potential se numeste nod de referinta, iar potentialul sau reprezinta potentialul de referinta.

In reteaua din figura (b), ca nod de referinta poate fi ales oricare din nodurile I sau L, avand potentialul de referinta egal cu trei unitati.

Urmatorul pas al algoritmului consta in a porni de la nodul de referinta si a "impinge" un debit egal cu potentialul de referinta catre nodul terminal, folosind la nevoie mai multe arce in acest scop. Impingerea se face intr-o maniera recursiva, astfel ca atunci cand debitul este impins intr-un nod, el trebuie sa fie impins afara din nod, spre nodul terminal. Numai nodul terminal poate accepta un surplus de debit fara a se debarasa de el. Similar, putem porni din nodul de referinta si sa "tragem" ( sa imprumutam ) debit spre intrare. Intotdeauna este posibil sa se impinga un debit necesar prin nodul de referinta, caci oricare alt nod din reteaua stratificata are cel putin tot atat potential ( la intrare si la iesire ). Nu este posibil sa impingem intr-o ramura moarta un debit de care nu putem scapa.

Prin operatiile de la prezentul pas s-a reusit marirea debitului in arcele alese. Procedura se reia, pornind cu o noua retea stratificata. Pentru exemplul dat, urmatoarea retea stratificata arata ca in figura (c), arcul AI nu mai este util deoarece este saturat si nu are alocat un debit invers. Dupa eliminarea arcelor moarte raman traseele ABGHF si AJKLF. Nodul de referinta poate fi H ( la fel putea fi ales G sau L ) cu un potential de referinta egal cu doi. Prin operatii de "impingere" si "tragere" de debit, arcele traseului ABGHF isi vor mari debitul cu doua unitati.

Urmatoarea retea stratificata contine ( vezi figura (d) ), traiectoria AJKLF, cu nodul de referinta L si un potential egal cu doua unitati. Apoi se obtine reteaua stratificata din figura (e), cu nodul de referinta B si un potential de referinta egal cu patru unitati.

Ciclul pasilor algoritmului ( construirea unei retele stratificate, gasirea nodului de referinta si cresterea debitelor ) continua pana cand nu mai este posibila construirea unei retele stratificate, adica nu se mai gaseste nici o cale utila intre sursa si terminal. Atunci, debitul de informatie va fi maxim si multimea arcelor saturate constituie taietura minima.

Reteaua stratificata din figura (f), cu AJKIBCDEF cale utila, cu nodul de referinta D si avand potentialul minim egal cu unitate, este ultima care se poate construi. Incercand construirea altei retele stratificate, vom gasi stratul doi ca fiind vid, fara a fi ajuns la nodul terminal.