Probleme DE Repartitie In Grafuri Bipartite
I.Elemente de teoria grafurilor
I.1. Grafuri neorientate……………………………………………………………..3
I.1.1. Noțiuni teoretice……………………………………………3
I.2. Grafuri orientate……………………………………………………………….15
I.2.1. Noțiuni teoretice………………………………………….15
II. Fluxuri în rețele de transport
II.1. Flux maxim/minim în rețele de transport……………………………23
II.2. Algoritmul Ford-Fulkerson……………………………………………….31
II.3. Algoritmul Edmonds-Karp……………………………………………….42
II.4. Algoritmul Dinic……………………………………………………………..47
III. Cuplaj maxim în grafuri bipartite…………………………………………………53
IV. Problema clasică de transport………………………………………………………64
Aplicație………………………………………………………………….80
Bibliografie…………………………………………………………………………………….83
=== PROBLEME DE REPARTITIE IN GRAFURI BIPARTITE ===
Cuprins
I.Elemente de teoria grafurilor
I.1. Grafuri neorientate……………………………………………………………..3
I.1.1. Noțiuni teoretice……………………………………………3
I.2. Grafuri orientate……………………………………………………………….15
I.2.1. Noțiuni teoretice………………………………………….15
II. Fluxuri în rețele de transport
II.1. Flux maxim/minim în rețele de transport……………………………23
II.2. Algoritmul Ford-Fulkerson……………………………………………….31
II.3. Algoritmul Edmonds-Karp……………………………………………….42
II.4. Algoritmul Dinic……………………………………………………………..47
III. Cuplaj maxim în grafuri bipartite…………………………………………………53
IV. Problema clasică de transport………………………………………………………64
Aplicație………………………………………………………………….80
Bibliografie…………………………………………………………………………………….83
I. ELEMENTE DE TEORIA GRAFURILOR
I.1. Grafuri neorientate
I.1.1. Noțiuni teoretice
Definiție I.1.1.1. Se numește graf neorientat o pereche ordonată de mulțimi (V,U), V fiind o mulțime finită și nevidă de elemente numite noduri sau vârfuri, iar U o mulțime de perechi neordonate (submulțimi de două elemente) din V numite muchii.
Definiție I.1.1.2. Numim muchii adiacente două muchii cu o extremitate comună.
Exemplul I.1.1.1.
V este mulțimea vârfurilor (avem 6 vârfuri) și U este mulțimea muchiilor (5 muchii).
Perechiile de muchii adiacente sunt: ([1,2],[2,4]), ([5,1],[1,2]), ([1,5],[5,4]), ([5,4],[4,2]).
Observăm că muchiile [1,5] și [5,4] sunt muchii adiacente pentru că au ca extremitate comună nodul 5.
Definiție I.1.1.3. Un graf parțial al grafului G=(V,U) este un graf G1=(V,U1) unde U1 U.
Cu alte cuvinte, G1 are aceeași mulțime de vârfuri ca G, iar muțimea de muchii U1 este chiar U sau o submulțime a acesteia (un graf parțial al unui graf se obține păstrând aceeași mulțime de noduri și eliminând o parte din muchii).
Prin urmare un graf parțial al lui G se obține prin eliminarea unui număr k de muchii , menținând aceeași mulțime de vârfuri. Spunem despre G1 că este indus de submulțimea de muchii U1.
Exemplul I.1.1.2.
Definiție I.1.1.4. Un subgraf al unui graf G=(V,U) este un graf H=(V1,U1) astfel încât V1 V iar U1 conține toate muchiile din U care au ambele extremități în V1.
Notație:
Prin urmare, un subgraf se obține eliminând un numar de vârfuri din V și muchiile incidente acestor vârfuri. Vom spune că subgraful H este indus sau generat de mulțimea de vârfuri V1.
Exemplul I.1.1.4.
Definiție I.1.1.5. Gradul unui vârf x este dat de cardinalul multimii muchiilor incidente lui x. Gradul vârfului x se notează d(x)=|{[x,y] V| yV\{x}|.
Definiție I.1.1.6. Un vârf care are gradul 0 se numește vârf izolat.
Definiție I.1.1.7. Un vârf care are gradul 1 se numește vârf terminal.
Exemplul I.I.1.5.
Pentru graful din fig. I.1.1.1.
d(1)=2 vârf interior; d(2)=2 vârf interior; d(3)=1 vârf terminal;
d(4)=2 vârf interior; d(5)=2 vârf interior; d(6)=1 vârf terminal;
Propoziția I.1.1.1. Dacă un graf G(V,U) are m muchii și n vârfuri, iar V={x1,x2,…,xn} atunci d(x1)+d(x2)+…+d(xn)=2*m.
Corolar I.1.1.1. În orice graf G există un număr par de vârfuri cu grad impar.
Definiție I.1.1.8. Se numește graf complet cu n vârfuri un graf care are proprietatea că orice două vârfuri distincte ale sale sunt adiacente.
Notație: Kn – graful complet cu n vârfuri
Propoziția I.1.1.2. Un graf complet Kn are n(n-1)/2 muchii.
Definiție I.1.1.9. Un graf G=(V,U) se numește bipartit dacă există două mulțimi nevide A, B astfel încât V=A U B, A∩B = și orice muchie a lui G are o extremitate în A iar cealaltă în B.
Definiție I.1.1.10. Un graf bipartit se numește complet dacă pentru orice x din A și y din B, există muchia [x,y].
Notație: Kp,q – un graf bipartit complet în care și
Un graf complet în care și are muchii.
Exemplul I.1.1.6.
Vom modifica graful din fig. I.1.1.4 astfel încât acesta să devină graf bipartit complet (fig. I.1.1.5).
Fie G=(V,U) un graf neorientat, V={x1,x2,..,xn}.
Definiție I.1.1.11. Se numește lanț în G succesiunea de vârfuri L=[xi1,xi2,…,xik] () cu proprietate că orice două noduri consecutive din lanț sunt adiacente, adică [xi1,xi2], [xi2,xi3], …, [xik-1,xik] U.
Vârfurile xi1 și xik se numesc extremitățile lanțului (xi1 – extremitatea inițială, xik – extremitatea finală). Numărul de muchii care compun lanțul L reprezintă lungimea lanțului.
Definiție I.1.12. Dacă vârfurile xi1, xi2, …, xik sunt diferite două câte două atunci lanțul se numește lanț elementar. În caz contrar, lanțul este lanț neelementar.
Cu alte cuvinte, un lanț elementar este un lanț care nu trece de două ori prin același vârf.
Definiție I.1.1.13. Se numește ciclu în G un lanț L pentru care capetele lantului coincid și toate muchiile adiacente sunt diferite.
Cu alte cuvinte, un ciclu este un lanț simplu închis.
Definiție I.1.1.14. Se numește ciclu elementar un ciclu care are proprietate că oricare două vârfuri ale sale, cu excepția primului și ultimului, sunt diferite două câte două. În caz contrar, ciclul este neelementar.
Prin urmare, un lanț elementar închis se numește ciclu elementar.
Exemplu I.1.1.7.
Pentru graful din fig. I.1.1.6 am dat câte un exemplu de lanț elementar, lanț neelementar și ciclu elementar.
Definiție I.1.1.14. Un graf G se numește conex dacă pentru orice două vârfuri x și y distincte ale sale există un lanț cu extremitatile x si y.
Definiție I.1.1.15. Se numește componentă conexă a grafului G=(V,U) un subgraf G1=(V1,U1), conex, al lui G care are proprietatea că nu există nici un lanț care să lege un vârf din V1 cu un vârf din V-V1.
Cu alte cuvinte, se numeste componenta conexa a unui graf neorientat, G=(V,U), un subgraf al lui G, G1=(V1,U1), conex si maximal.
Exemplu I.1.1.8.
În fig. I.1.1.6. avem două componente conexe :
1 : [2] 2 : [1,3,4,5,6]
Definiție I.1.1.16. Numarul (G) = m-n+p se numeste numar ciclomatic al grafului G=(V,U); am notat cu m=U, n=V , p – numarul componentelor conexe ale grafului.
Definiție I.1.1.17. Numarul (G) = n-p se numeste numar cociclomatic.
În ceea ce privește reprezentarea în memorie a grafurilor neorientate, putem folosi una din următoarele metode:
1. Punerea în evidență a vectorului de muchii.
Se citesc pe rând perechile de muchii. Pentru a se putea realiza acest lucru este necesar să știm câte perechi de muchii trebuie citite (în caz contrar trebuie citite perechi de muchii până la introducerea unei anumite perechi, de exemplu [0,0], în același timp numărându-se și muchiile introduse). Dacă nu știm numărul de vârfuri n, putem considera că numărul de vârfuri este numărul maxim citit din componența vârfurilor din muchii, dar acest lucru nu este foarte corect deoarece putem avea vârfuri izolate cu număr de ordine mai mare decat numărul de ordin cel mai mare cictit din componența muchiilor.
2. Lista de adiacență: pentru fiecare nod punem în evidență mulțimea nodurilor adiacente cu nodul respectiv.
3. Matricea de adiacență: un graf poate fi memorat printr-o matrice pătratică booleană, de dimensiune egală cu numărul de noduri, în care un element va fi 1 dacă există muchia [xi,xj] și 0 în caz contrar. Aceasta matrice se numeste matricea de adiacenta.
Observații:
Numărul de elemente din lista de adiacență corespunzătoare unui nod i este același cu gradul vârfului
Matricea de adiacență este o matrice simetrică față de diagonala principală
Suma elementelor dintr-o matrice de adiacență este 2m.
Pe linia i și pe coloana i avem un număr de elemente 1 egal cu d(i).
Pe diagonala principală a unei matrice de adiacență corespunzătoare unui graf neorientat fără bucle (o buclă este o muchie în care cele două extremități coincid), sunt numai elemente 0.
Exemplul I.1.1.9.
Pentru graful din fig. I.1.1.6.
1. Matricea muchiilor
V={1,2,3,4,5,6}, U={[1,5],[1,6],[3,6],[3,5],[3,4],[6,5]}
2. Lista de adiacență
3. Matricea de adiacență
Parcurgerea grafurilor neorientate
1. Parcurgerea în lățime (BF – Breadth First)
Principiul: se vizitează întâi vârful inițial, apoi vecinii acestuia, apoi vecinii nevizitați ai acestora… Parcurgerea este o parcurgere pe nivele ale nodurilor din graf.
Prin vizitarea unui vârf înțelegem, de fapt, o anumită prelucrare asupra vârfului respectiv.
Prin vecinul nodului x înțelegem un nod y care este adiacent cu x, adică există o muchie între x și y.
Algoritmul constă în alegerea, la un moment dat, dintre toți vecinii unui vârf, pe acela ce nu a fost încă vizitat. Acest lucru este posibil prin folosirea unui vector V cu n componente care se definește astfel:
Se folosește o structură de tip coada (simulată în alocarea statică printr-un vector C) în care prelucrarea unui vârf k aflat la un capăt al cozii (vârful cozii), consta în introducerea la celălalt capăt al ei, a tuturor vârfurilor j vecine cu k, nevizitate încă. Pentru început, k este vârful indicat inițial – p și toate componentele lui C sunt 0.
Exemplul I.1.1.10.
Presupunând că plecăm cu parcurgerea începând cu nodul 1.
Introducem pe 1 în coadă. Vecinii lui 1 nevizitați sunt 2și 5. Îi introducem și pe aceștia în coadă. Până în acest moment coada arată astfel: C=[1,2,5]. 1 nu mai are vecini nevizitați și începem să căutăm vecinii nevizitați ai lui 2. Îl găsim pe 3 și-l introducem în coadă C=[1,2,5,3]. Nu mai avem vecini nevizitați ai lui 2, căutăm vecinii lui 5 (nu găsim). Căutăm vecinii nevizitați ai lui 3. Găsim nodul 4 și-l introducem în coadă: C=[1,2,5,3,4]. Căutăm apoi vecinii nevizitați ai lui 4 (nu găsim). Scriem conținutul cozii: 1,2,3,5,4
Descrierea algoritmului BF
Utilizăm două variabile de tip intreg p (care reține poziția primului element din C) si q (care retine poziția ultimului element din c).
C // inițial coada C este vidă
For k=1,n
VIZ[k]=0; // inițial toate varfurile se consideră nevizitate
C[1]=s; // in coada C se memoreaza varful inițial s
p=1;
q=1;
VIZ[s]=1; // se viziteaza varful s, fără a fi prelucrat
while (pq) {
// se executa un ciclu while cât timp coada C este nevidă
// se va scoate vârful care urmează din C, indicat prin p
j=C[p]; // la inceput se va scoate s, vizitându-se vecinii săi
// se prelucrează toți vecinii k ai lui j, nevizitati incă, identificându-i prin parcurgerea liniei j din matricea A
for k=1,n
if (a[j,k]==1 and VIZ[k]==0) {
// varful k, va deveni noul ultim element din C
q=q+1;
// se va reține actualul ultim element in C
C[q]=k;
// se viziteaza varful k
VIZ[k]=1; }
p=p+1; // se va trece la urmatorul vârf care va fi scos din C
}
Se poate verifica corectitudinea algoritmului, in sensul că a fost prelucrat, o singură dată, fiecare varf.
Primul ciclu for (inițializarea) necesită un timp O(n) (n asignări).
Ciclul while se execută de cel mult n-1 ori (s este vizitat anterior).
In corpul ciclului while există un nou ciclu for ce conține selecția simpla if care se va executa de câte n ori la fiecare reluare a lui while. Prin acest for se parcurge linia corespunzătoare vârfului analizat din matricea de adiacentă.
Celălalte instrucțiuni prezente in algoritm (de asignare, incrementare) nu afectează ordinul de complexitate al algoritmului.
Asadar, complexitatea algoritmului BF, in cazul reprezentării grafului prin matricea sa de adiacentă, este O(n(n-1)+n) = O(n2)=Θ(n2).
Dacă graful G este reprezentat prin liste de adiacentă, ciclul inițial se execută tot in O(n) timpi.
Lista Lj, adica lista vecinilor vârfului j, va conține dj (valenta vârfului j) elemente.
Prin urmare, la fiecare execuție a lui while, ciclul for din corpul său, se va executa intr-un timp cdj, unde c este o constantă, iar j reprezinta vârful care urmează a fi prelucrat si scos din C.
Se stie ca dk = 2m.
Deci timpul total este O(n+m)=Θ(n+m).
2. Algoritmul de parcurgere in adancime (DF – Depth First)
În cazul algoritmului de parcurgere în adâncime DF se va folosi o stivă în care adăugarea și eliminarea elementelor se face la același capăt, numit capul stivei. Eliminarea elementelor se va face în ordinea inversa introducerii lor, la orice moment putând fi eliminat ultimul element introdus.
Metoda consta în:
– alegem un vârf de pornire, pentru acesta se alege primul vecin al său nevizitat încă, pentru acest vecin căutăm primul vecin al său nevizitat și ș.a.m.d. În cazul în care un vârf nu mai are vecini nevizitați atunci ne întoarcem la nodul anterior, iar pentru acel nod căutăm următorul vecin nevizitat al său.
Folosim un vector V cu n elemente, cu ajutorul căruia se marchează nodurile deja vizitate pentru a evita trecerea de mai multe ori prin același nod. Cu alte cuvinte V [j] = 1 daca nodul j a fost deja vizitat și V[j] = 0 în caz contrar, la fel ca la parcurgerea BF. Vom spune despre un nod i că a fost explorat dacă are toate nodurile adiacente vizitate.
Ieșirea din recursivitate se produce în momentul în care nu se mai găsesc vârfuri neparcurse adiacente cu vârfurile parcurse deja. Este posibil ca după un apel al procedurii începând cu un anumit vârf i să rămână în graf vârfuri neparcurse. În această situație apelul procedurii se repetă pentru un alt vârf inițial (dintre vârfurile neparcurse) până la parcurgerea tuturor nodurilor grafului.
Exemplul I.1.1.11.
Dacă dorim să parcurgem graful în adâncime plecând din nodul 1. Vizităm pe 1 și găsim nodul 2 ca vecin nevizitat al lui. Îl vizităm pe 2. 3 este unul din vecinii nevizitați ai lui 2. Îl vizităm pe 3. 4 este unul din vecinii nevizitați ai lui 3 și atunci îl vizităm pe 4. 5 este vecinul nevizitat al lui 4, îl vizităm și pe 5 și terminăm parcurgerea pentru că nu mai avem noduri nevizitate în această componentă conexă.
Descrierea algoritmului DF
Vom folosi un vector urm[], in care componenta urm[k] reprezintă vârful vecin lui k care urmează a fi vizitat (dacă exista). Determinarea acestei componente se va face parcurgând linia k din matricea de adiacența A incepând cu coloana k+1, până cand se intalnește un vecin al lui k nevizitat incă. Un astfel de vecin, dacă se gasește, se va pune in vârful stivei, mărindu-se corespunzator si pointerul de stiva ps. Daca nu se gasește, pointerul de stiva ps se va micșora cu o unitate cu scopul de a continua cu următorul vârf.
S // inițial stiva este vidă
for k=1,n
{VIZ[k]=0; // inițial toate vârfurile se consideră nevizitate
urm[k]=0;}
ps=1; // se inițializează pointerul de stiva ps
VIZ[s]=1; // se vizitează vârful inițial s
S[ps]=s; // se pune s in stivă
while (ps1) {
// ciclul while se execută cat timp stiva nu este vidă
k=S[ps]; // se scoate elementul din vârful stivei
r=urm[k]+1;
// se parcurge linia k din matricea A, incepând cu urmatorul element dupa k
while (rn)
// se caută primul vârf adiacent lui k care nu a fost vizitat
if ((a[k,r]==0) or ((a[k,r]==1) and (VIZ[r]==1)) r=r+1 ;
else { urm[k]=r;
exit; // se iese din acest ciclu while
}
if (r==n+1) ps=ps-1;
// nu există vecin r al lui k, nevizitat
else {
VIZ[r]=1; // se vizitează vârful r
ps++ ; // se incrementează pointerul de stivă
S[ps]=r; // se retine vârful r in stivă
}}
Primul ciclu for (inițializarea) necesită un timp O(n) (2n asignări).
Primul ciclu while se va executa de cel mult n-1 ori.
Al doilea ciclu while se execută de n ori.
Așadar f(n)=n+n(n-1)=O(n2).
Este evident ca f(n)=Θ(n2).
Dacă graful neorientat este reprezentat prin liste de adiacentă, atunci există 2m=d(i) testari (se testeaza pentru fiecare vârf lista sa de adacentă).
Algoritmul respectiv va avea o complexitate Θ(max(m,n))=Θ(m+n).
I.2. Grafuri orientate
I.2.1. Noțiuni teoretice
Definiție I.2.1.1. Numim graf orientat, o pereche ordonată de mulțimi G=(V,U), unde V este o mulțime finită și nevidă numită mulțimea nodurilor (vârfurilor) și U este o mulțime formată din perechi ordonate de elemente ale lui X, numită mulțimea arcelor.
Observații:
– Prin noțiunea de perechi ordonate nu trebuie să înțelegem că un arc este mai mare decât altul, ci că trebuie să facem deosebire între un arc de forma (x,y) și un arc de forma (y,x).
– Un graf neorientat poate fi transformat într-un graf orientat înlocuind muchiile cu 2 arce cu sens contrar adică muchia [x,y] se înlocuiește cu arcele (x,y) și (y,x)
– Într-un graf putem avea două sau mai multe arce identice.
Definiție I.2.1.2. Se numește p-graf, un graf orientat în care numărul arcelor identice este mai mic sau egal cu o valoare dată p.
Definiție I.2.1.3. Într-un arc u=(x,y), x se numește extremitate inițială, iar y se numește extremitate finală a arcului. Cu alte cuvinte, “arcul iese din nodul x și intră în nodul y”. La fel ca la grafurile neorientate, vom spune că nodurile x și y sunt adiacente, iar arcul u și nodul x sunt incidente (la fel arcul x și nodul y). Nodul y se numește succesor al lui x, iar nodul x se numește predecesor al lui y.
Definiție I.2.1.4. Un arc de forma (x,x), care iese din nodul x și intră tot în x, se numește buclă.
Definiție I.2.1.5. Gradul exterior al unui vârf x, notat d+(x), reprezintă numărul arcelor care ies din nodul x, adică numărul arcelor de forma (x,z)U.
Analog, se definește gradul interior al unui vârf x, notat d-(x), ca fiind numărul arcelor care intră în nodul x, adică de forma (y,x)U.
Definiție I.2.1.6. reprezintă mulțimea succesorilor lui x, adică mulțimea nodurilor ce constituie extremități finale ale arcelor care pleacă din nodul x.
reprezintă mulțimea predecesorilor lui x, adică mulțimea nodurilor ce constituie extremități inițiale ale arcelor care pleacă din nodul x.
Definiție I.2.1.7.
ω+(x) = {u = (x,y)| u ε U} reprezintă mulțimea arcelor care ies din nodul x;
ω-(x) = {u = (y,x)| u ε U} reprezintă mulțimea arcelor care intră în nodul x;
Exemplul: I.2.1.1.
Fie graful din fig. I.2.1.1. Vom pune în evidență mulțimea nodurilor, mulțimea arcelor, gradul interior și gradul exterior pentru fiecare nod, mulțimea predecesorilor și mulțimea predecesorilor pentru fiecare vârf, mulțimea arcelor care ies și mulțimea arcelor care intră în fiecare vârf.
V={1,2,3,4,5,6,7}
U={(1,2), (1,4), (2,1), (1,3), (3,3), (3,6), (6,7), (5,3), (5,4)}
d+(1)=3; d+(2)=1; d+(3)=2; d+(4)=0; d+(5)=2; d+(6)=1; d+(7)=0;
d-(1)=1; d-(2)=1; d-(3)=3; d-(4)=2; d-(5)=0; d-(6)=1; d-(7)=1.
+(1)={2,3,4}; -(1)={2};
+(2)={1}; -(2)={1};
+(3)={3,7}; -(3)={1,3,5};
+(4)=Ø; -(4)={5,1};
+(5)={ 3,4}; -(5)=Ø;
+(6)={7}; -(6)={3};
+(7)={6}; -(7)=Ø;
ω+(1) ={(1,2), (1,3), (1,4)}; ω-(1) ={(2,1)}
ω+(2) ={(2,1)}; ω-(1) ={(1,2))}
ω+(3) ={(3,3), (3,7)}; ω-(3) ={(1,3), (3,3), (3,5)}
ω+(4) =Ø; ω-(4) ={(5,4), (1,4)}
ω+(5) ={(5,3), (5,4)}; ω-(5) =Ø
ω+(6) ={(6,7)}; ω-(6) ={(3,6)}
ω+(7) =Ø; ω-(7) ={(6,7)}
În cele ce urmează, ne vom referi numai la 1-grafuri
Definiție I.2.1.8. Un subgraf al unui graf G=(V,U) este un graf H=(V1,U1) astfel încât V1 V iar U1 conține toate muchiile din U care au ambele extremități în V1.
Notație:
Prin urmare, un subgraf se obține eliminând un număr de vârfuri din V și muchiile incidente acestor vârfuri. Vom spune că subgraful H este indus sau generat de mulțimea de vârfuri V1.
Exemplul I.2.1.2.
Fie graful din fig. I.2.1.1. Graful din fig. I.2.1.2. este un subgraf al grafului din fig. I.2.1.1.
Definiție I.2.1.9. Un graf parțial al grafului G=(V,U) este un graf G1=(V,U1) unde U1 U.
Cu alte cuvinte, G1 are aceeași mulțime de vârfuri ca G, iar muțimea de muchii U1 este chiar U sau o submulțime a acesteia (un graf parțial al unui graf se obține păstrând aceeași mulțime de noduri și eliminând o parte din muchii).
Prin urmare, un graf parțial al lui G se obține prin eliminarea unui număr k de muchii , menținând aceeași mulțime de vârfuri. Spunem despre G1 că este indus de submulțimea de muchii U1.
Exemplul I.2.1.3.
Vom da un exemplu de graf parțial al grafului din fig. I.2.1.1.
Definiție I.2.1.10. Se numește lanț într-un graf orientat, un șir de arce cu proprietatea că oricare două arce vecine au o extremitate comună (indiferent de sensul de orientare al arcelor).
Noțiunile de lanț elementar și lanț neelementar sunt identice cu cele de la grafuri neorientate.
Definiție I.2.1.11. Numim drum într-un graf orientat G=(V,U), , un șir de arce , , cu proprietatea că extremitatea finală a arcului coincide cu extremitatea inițială a arcului .
Lungimea drumului e dată de numărul arcelor care-l compun. Dacă vârfurile sunt distincte două câte două atunci drumul este elementar.
Prin urmare, un drum este elementar dacă el nu trece de două ori prin același vârf. În caz contrar se numește drum neelementar.
Definiție I.2.1.12. Un drum D dintr-un graf orientat se numește drum simplu dacă arcele sale sunt distincte două câte două.
Definiție I.2.1.13. Un drum L pentru care primul și ultimul element coincid se numește circuit.
Cu alte cuvinte, un circuit este un drum simplu închis.
Dacă toate vârfurile circuitului, cu excepția primului și ultimului, sunt distincte (drum elementar închis), circuitul se numește elementar. În caz contrar circuitul se numește neelementar.
Exemplul I.2.1.4.
Considerăm graful din fig. I.2.1.1. Putem da următoarerele exemple pentru noțiunile prezentate:
Lanț elementar: L1=[7,6,3,5]; |L1|=3
Lanț neelementar: L2=[5,4,1,2,1,3]; |L2|=5
Drum elementar D1=(1,3,6,7); |D1|=3
Drum neelementar D2=(1,2,1,3,6,7); |D2|=5
Circuit elementar C1=(1,2,1); |C2|=2
Definiție I.2.1.14. Un graf ponderat “weighted graph” este un graf în cadrul căruia fiecarui arc îi este asociată o valoare. Valoarea asociată arcului are semnificația de “cost” a legăturii între cele 2 noduri sau de “distanța” între noduri.
Reprezentarea grafurilor orientate
Pentru fiecare metodă de reprezentare a grafurilor orientate prezentată în continuare, vom exemplifica pe graful din fig. 1.2.1.4.
Punerea în evidență a vectorului de arce. Se realizează la fel ca în cazul grafurilor neorientate.
Exemplul 1.2.1.5.
|V|=6 și
U={(2,1), (1,3), (3,2), (4,3), (3,5), (5,6)}
Liste de adiacență: pentru fiecare vîrf se consideră lista de adiacență L=+ sau L=-. De asemenea, pot fi reprezentate ambele tipuri de liste ca în exemplul următor.
Exemplul 1.2.1.6.
Matricea de adiacență. Definirea acesteia este asemănătoare cu cea de la grafuri neorientate
Exemplul 1.2.1.7.
4. Matricea de drumuri
Exemplul 1.2.1.8.
5. Matricea vârfuri-arce (matricea de incidență vârfuri-arce). Se folosește la grafuri orientate fără bucle, altfel reprezentarea matricei în memorie (în special la citirea datelor) ar fi greoaie sau imposibilă.
Observații:
Numărul elementelor egale cu 1 de pe linia k reprezintă .
Numărul elementelor egale cu -1 de pe linia k reprezintă .
O linie care are toate elementele egale cu 0 corespude unui vârf izolat.
Exemplul 1.2.1.9.
II. FLUXURI ÎN REȚELE DE TRANSPORT
II.1. Flux maxim/minim în rețele de transport
Întâlnite în viața de zi cu zi sub diferite forme, rețelele de transport își au întrebuințarea în toate domeniile de activitate: industrie, agricultură, telecomunicații… în care se pune problema transportării unor unități de produs (energie, materie, informație…) de la anumite surse (puncte de plecare, puncte inițiale) către anumite destinații (puncte de sosire, puncte finale). Aceasta, poate fi reprezentată intuitiv sub formă grafică de persoane care să nu aibă cunoștințe despre teoria grafurilor și a rețelelor de transport.
De exemplu:
Din trei depozite de materiale de construcții D1, D2, D3 pot trimite zilnic u1, u2, și u3 unități de materiale de construcții care vor fi transportate la două firme de construcții F1 și F2 . Firmele au nevoie zilnic de c1 respectiv c2 unități. Transportul se poate realiza prin intermediul a unor rute de transport pe care sunt impuse anumite restricții asupra limitelor de capacități ce pot fi transportate. Cum trebuie organizat transportul zilnic astfel încât stocul în cele trei depozite să fie cât mai mic (acesta este un exemplu clasic de problemă pentru găsirea fluxului minim)
Din exemplu observăm că:
depozitele sunt sursele
firmele de construcții sunt destinațiile
rutele de transport le putem numii trasee
se transportă unități indivizibile de produs
Această problemă poate fi mult mai complicată dacă fiecare sursă poate aproviziona mai multe destinații și fiecare destinație poate fi aprovizionată de mai multe surse. De asemenea, gradul ei de complexitate crește și dacă aprovizionarea destinațiilor se face prin intermediul altor puncte intermediare.
Un exemplu de problemă în care se cere să se determine fluxul maxim ar fi următoarea:
Considerăm că între două localități (1 – localitatea sursă, 2- localitatea destinație) trebuie transportată o anumită cantitate de tehnică de luptă. Întru-cât pe fiecare drum datorită costurilor ridicate sau faptului că nu putem transporta decât o anumită cantitate de produs (ne sunt impuse limite pe care nu le putem depăși) trebuie să aflăm care este cantitatea maximă de tehnică de luptă care poate pleca simultan din localitatea 1.
Având în vedere situațiile din practică pe care le vom transpune în teoria rețelelor de transport, vom folosi următorii termeni: unitățile indivizibile ale cantității transportate, care se deplaseaza de-a lungul traseelor între surse și destinații, le vom numi unităti de flux. Ansamblul format din aceste trasee, surse, destinații și, eventual, alte puncte intermediare, formeaza o rețea de transport. Acestea pot fi reprezentată printr-un graf orientat, conex (loop-free).
Definiție II.1.1. Un 1-graf G=(V,U) cu n+1 vârfuri se numește rețea de transport, dacă el verifică următoarele condiții:
există un vârf unic x0 (nod inițial, intrarea rețelei sau sursă) în care nu intră nici un arc
există un vârf unic xn (nod final, ieșirea rețelei sau destinație) din care nu iese nici un arc
G este un graf conex
S-a definit o funcție pe mulțimea arcelor U cu valori numere reale nenegative . Numărul c(u) se numește capacitatea arcului u.
Vom nota o rețea de transport RG=(V,U,c) iar pentru această rețea de transport graful G=(V,U) se numește graf subadiacent rețelei.
Definiție II.1.2. O funcție φ definită pe mulțimea arcelor cu valori numere nenegative se numește flux pentru rețeaua de transport RG=(V,U,c) dacă sunt îndeplinite următoarele condiții:
a) condiția de conservare a fluxului: pentru orice vârf xi, care nu este intrarea sau ieșirea rețelei, suma fluxurilor asociate arcelor care intră în xi este egală cu suma fluxurilor asociate arcelor care ies din xi.
b) condiția de mărginire a fluxului: Fluxul asociat oricărui arc nu trebuie să depășească capacitatea arcului respectiv .
Pentru simplificare vom nota:
; .
Definiție II.1.3. Fie φ este un flux în rețeaua G=(V,U,c). Numim valoarea fluxului φ numărul .
Observații:
1. v(φ) se poate interpreta ca fiind fluxul net care ajunge în ieșirea rețelei sau fluxul net care iese din intrarea rețelei.
2. În orice rețea RG=(V,U,c) există un flux, fluxul nul φ(u)=0 .
Conform condiției de conservare a fluxului rezultă că fluxul care iese din sursă notat cu φ0 este egal cu fluxul care intră în destinație, flux notat cu φn.
unde și
3. Un flux poate fi interpretat ca o cantitate de materie care traversează o rețea de transport prin arcele acesteia, ieșind din nodul sursă și intrând în nodul destinație.
4. Rețeaua de transport poate fi transformată într-o rețea numită rețea de circulație prin adăugarea unui nou arc (xn,x0) de capacitate egală cu ∞ (ceea ce va însemna că nu există restricții de capacitate pe acest arc). Dacă definim fluxul pe acest arc egal cu φ0, flux care este egal cu φn, condiția de conservare a fluxului va fi verificată în toate nodurile rețelei.
Definiție II.1.4. Fie RG=(V,U,c) și φ un flux în RG. Numim c-drum (în RG relative la fluxul φ) un drum μ în G’ (multigraful suport al digrafului G=(V,U)) cu proprietatea că , U(μ) = mulțimea arcelor corespunzătoare drumului μ:
Definiție II.1.5. Dacă μ este un c-drum și , numim capacitate reziduală a lui (xi,xj) (relativ la c-drumul μ) numărul
notăm . Capacitatea reziduală a drumului este
Exemplul II.1.1.:
Considerăm rețeaua de transport de mai jos, în care pe fiecare arc este scrisă mai întâi capacitatea și apoi fluxul.
Nodurile grafului sunt V={1,2,3,4,5}. este un lanț de la nodul inițial 0 la nodul 5.
Arcele directe sunt:
iar arcele inverse
.
Prin urmare, capacitatea reziduală a lui este
Definiție II.1.6. Se numește drum de creștere (drum augmentat) al fluxului φ în rețeaua RG=(V,U,c) un c-drum de la sursă la destinație.
Lema II.1.1. Dacă este un drum de creștere al fluxului în rețeaua RG=(V,U,c), definim
atunci este flux în RG și
Exemplul II.1.2.
Fluxul pentru rețeaua din fig. II.1.1. este precizat pe arce, după modificările de flux realizate:
Observații:
Această lemă justifică denumirea de drum de creștere precum și cea de capacitate reziduală
Din definiție, dacă este un drum de creștere , avem , rezultă că dacă admite un drum de creștere, nu este flux de valoare maximă.
Definiție II.1.7. Pentru o rețea de transport RG=(V,U,c) vom considera o submulțime de vârfuri cu proprietatea că sursa nu e din A dar destinația aparține mulțimii A. Mulțimea ω-(A), adică mulțimea arcelor grafului pentru care extremitatea inițială nu aparține lui A iar extremitatea finală aparține lui A, se numește tăietură (secțiune) a rețelei.
Capacitatea tăieturii ω-(A) este egală, prin definiție, cu suma capacităților arcelor tăieturii.
.
Exemplul II.1.3.:
Vom exemplifica aceste noțiuni prin rețeaua din fig. II.1.3.:
Lemă II.1.2. Într-o rețea de transport RG=(V,U,c), între o secțiune ω-(A) determinată de mulțimea și un flux φn, există relația:
Lema II.1.3. Dacă într-o rețea de transport RG=(V,U,c), pentru un flux și o secțiune ω-(A0) determinată de o mulțime și atunci este un flux maximal și secțiunea determinată de A0 are capacitate minimă.
Lemă II.1.4. Dacă φ este un flux în RG=(V,U,c) și ω-(A) e o secțiune a rețelei, atunci , adică, valoarea fluxului este egală cu fluxul net ce trece prin orice secțiune.
Teoremă II.1.1. Un flux φ este de valoare maximă într-o rețea RG dacă și numai dacă nu există drumuri de creștere ale fluxului φ în rețeaua RG.
Teoremă II.1.2. Dacă toate capacitățile sunt întregi, atunci există un flux de valoare maximă cu toate componentele întregi.
Demonstrație:
Se consideră următorul algoritm:
φ0=0; i=0;
2. cât timp există μi – drum de creștere relativ la φi
2.1.
2.2. i=i+1
3. stop
Se observă că “φi are componente întregi ” este un drum invariant al algoritmului (din definiția lui , dacă toate capacitățile sunt întregi, rezultă că este întreg în ipoteza că φi este întreg) și că la fiecare iterație a pasului 2 valoarea fluxului curent crește cu cel puțin o unitate, deci pasul 2 se repetă de cel mult ori. Deci, fluxul obținut este, conform teoremei precedente, de valoare maximă.
Observație: Algoritmul descris mai sus, este finit și în cazul capacităților relaționale.
Definiție II.1.8. Un arc , arc direct, se numeștre saturat dacă , adică fluxul și capacitatea corespunzătoare arcului u sunt egale.
II.2. Algoritmul lui Ford-Fulkerson
Definiție II.2.1. Printr-o rețea de transport se înțelege un graf orientat care conține două vârfuri speciale (numite sursă și respectiv destinație) și care are proprietatea că orice nod al său face parte dintr-un drum de la sursă la destinație.
Problema fuxului maxim este problema determinării unui flux φ definit pe mulțimea U a arcelor din rețeaua de transport RG=(V,U,c) astfel încât fluxul φn ce intră în destinația rețelei să fie de valoare maximă.
Problema determinării fluxului maxim cu componente numerice raționale într-o rețea cu capacități numere raționale, se reduce la cazul când componentele fluxului cât și capacitățile arcelor sunt numere întregi pozitive.
Pentru această problemă vom prezenta algoritmul lui Ford-Fulkerson, algoritm care se bazează pe următoarele două proprietăți:
Proprietate II.2.1. Fie μ un drum de la sursă la destinație într-o rețea de transport. Dacă toate arcele acestui drum sunt nesaturate, se poate mări fluxul φn în destinație, având în vedere condțiile a) și b) de la definirea rețelei de transport.
Proprietate II.2.2. Fie v un lanț care unește sursa cu destinația. Vom nota cu
v+- mulțimea arcelor lui v orientate în sensul de la x0 –sursă către xn –destinație.
v– mulțimea arcelor lui v orientate în sensul de la destinație către sursă.
Fie
dacă , putem mări fluxul astfel: vom mări cu fluxul pe fiecare arc și îl vom diminua cu pe fiecare arc .
Procedând astfel vom obține tot un flux cu componente pozitive care verifică condițiile a) și b) din definiția II.1.1. (definiția rețelei de transport), astfel încât fluxul ce intră în xn va fi: .
Definiție II.2.2. Un lanț pentru care se numește lanț saturat.
Se observă că proprietatea II.2.2. se reduce la proprietatea II.2.1. când lanțul v de la sursă la destinație este chiar un drum ().
Definiție II.2.3. Un flux dintr-o rețea de transport se numește flux complet dacă orice drum de la intrarea x0 la ieșirea xn conține cel puțin un arc saturat.
Un flux complet nu este neapărat maxim, deoarece el poate fi eventual mărit considerând și lanțuri nesaturate de la x0 la ieșirea xn, care nu sunt drumuri.
Propoziția II.2.1. Dacă pentru o rețea de transport RG=(V,U,c) care are definit un flux φ pe arcele sale nu există nici un lanț nesaturat de la intrarea x0 la ieșirea xn (pentru care ) fluxul este un flux maximal în xn.
Demonstrație:
Să considerăm toate c-drumurile de la x0 la xn și să suprimăm toate arcele u pentru care există un lanț elementar v astfel încât și sau și , u fiind primul arc întâlnit cu aceste proprietăți când ne deplasăm pe c-drumul v de la sursă la destinație.
Graful parțial astfel obținut are cel puțin două componente conexe.
Una dintre aceste componente este formată dintr-o submulțime de vârfuri A care conține destinația și nu conține sursa.
Observăm că submulțimea de vârfuri A definește o tăietură și există egalitatea:
deoarece fluxul în xn este egal cu diferența dintre fluxul care intră în mulțimea de vârfuri A și fluxul care părăsește mulțimea A, care conține ieșirea xn.
Pe de altă parte, toate arcele din au aceeași orientare cu lanțurile de la sursă la destinație astfel încât pentru orice . La fel toate arcele au orientare opusă orientării lanțurilor respective de la intrarea x0 la ieșirea xn care folosesc aceste arce, astfel încât pentru orice . Arcele din și respectiv din au fost suprimate anterior, deoarece în caz contrar componenta conexă A nu va fi maximală în raport cu incluziunea, ceea ce contrazice definiția unei componente conexe.
Am observat însă că pentru orice flux φ și pentru orice tăietură există inegalitatea
Deoarece am găsit un flux φ și o tăietură care fac ca această inegalitate să devină egalitate, fluxul φ este maxim iar tăietura are capacitatea minimă. Cu alte cuvinte, inexistența lanțurilor nesaturate de la sursă la destinație în rețeaua de transport are drept cosecință maximizarea fluxului φ în xn ceea ce demonstrează propoziția.
Teorema II.2.1. (Ford-Fulkerson)
Într-o rețea de transport valoarea maximă a fluxului la ieșire este egală cu capacitatea minimă a unei tăieturi:
Pe baza caracterizării unui flux maxim la ieșire prin inexistența lanțurilor nesaturate de la intrarea la ieșirea rețelei, vom enunța în continuare algoritmul lui Ford-Fulkerson de găsire a unui flux maxim cu componente numere întregi pozitive într-o rețea de transport cu capacitățile arcelor numere întregi nenegative.
Acest algoritm are următoarele etape:
Etapa 1: Obținerea unui flux φ compatibil cu capacitățile rețelei
Acest flux inițial poate avea componente nule pe fiecare arc sau poate fi ales în mod arbitrar, însă el trebuie să verifice condiția de conservare a fluxului în fiecare nod diferit de la intrare la ieșire, precum și condiția de mărginire pe fiecare arc al rețelei.
Etapa 2: Obținerea unui flux complet
Pentru a obține un flux complet este suficient să considerăm rețeaua de transport parțială care conține numai arce nesaturate. Dacă fluxul nu este complet, va exista în acest graf parțial un drum de la sursă la destinație. Se mărește fluxul pe arcele acestui drum până la saturarea cel puțin a unui arc.
Se repetă operația până când toate drumurile de la x0 la xn vor fi saturate (vor conține cel puțin un arc saturat).
Etapa 3: Obținerea unui flux maximal la ieșirea rețelei
Pentru aceasta se vor determina lanțurile nesaturate de-a lungul cărora fluxul de la sursă la destinație poate fi mărit.
Vom folosi următorul procedeu de etichetare:
se marchează intrarea cu [+]
un vârf xi marcat, se va marca:
– cu [+xi] orice vârf xj nemarcat cu proprietatea că arcul (xi, xj) este nesaturat
– cu [-xi] orice vârf xj nemarcat cu proprietatea că arcul (xj, xi) este traversat de un flux nenul
Dacă prin acest procedeu de marcare s-a marcat ieșirea rețelei, atunci fluxul nu este maxim. Se va considera un lanț format din vârfuri etichetate (ale căror etichete au respectiv semnele + sau -), care unește sursa de destinație.
Dacă vom nota acest lanț cu v, pentru arcele , vom determina diferența , iar pentru arcele vom considera valoarea
Cu ajutorul acestor valori , apoi vom mări cu fluxul pe fiecare arc și vom micșora cu fluxul pe fiecare arc , ceea ce are ca efect mărirea fluxului în xn cu .
Se repetă aplicarea acestui procedeu de etichetare până când nu va mai fi posibil să se marcheze ieșirea rețelei, adică până când nu vor mai exista lanțuri nesaturate care să permită mărirea fluxului în ieșire.
În acest moment ne oprim, deoarece fluxul obținut este maxim iar mulțimea arcelor care unesc vârfurile marcate cu vârfurile nemarcate constituie o tăietură de capacitate .
Algoritmul are un număr finit de pași deoarece atât capacitățile arcelor cât și valorile fluxurilor sunt numere întregi pozitive, la fiecare mărire a fluxului valoarea crescând cu cel puțin o unitate; fluxul este mărginit, el neputând depăși capacitatea minimă a unei tăieturi.
Faptul că arcele care unesc vârfurile etichetate cu vârfurile neetichetate la ultimul pas al aplicării algoritmului constituie o tăietură de capacitate minimă, rezultă din demonstrația proprietății II.2.1. luând în rolul mulțimii A mulțimea vârfurilor neetichetate ale rețelei. Evident, sursa nu aparține lui A dar destinația aparține mulțimii A!
Obținerea unei tăieturi de capacitate minimă este utilă pentru verificarea maximilității fluxului la ieșire, dar prezintă interes în sine într-o serie de probleme.
Descrierea algoritmului Ford-Fulkerson
Se alege , un flux inițial (posibil un flux nul); se etichetează x0 cu [+]
cât timp mai există vârfuri etichetate necercetate
“alege” un vârf etichetat și necercetat xi
etichetăm corespunzător pe xi
dacă xn a primit etichetă atunci
modifică fluxul pe drumul dat de etichete
șterge toate etichetele
etichetează pe x0 cu [+]
3.
φ – flux de valoare maximă; – tăietură de capacitate minimă.
Complexitatea algoritmului Ford-Fulkerson
Pentru fiecare creștere a fluxului sunt necesare cel mul 2m (m- numărul de muchii din graf) căutări de arce în vederea etichetării. Dacă toate capacitățile sunt numere întregi atunci vor fi necesare cel mult v (v=valoarea fluxului maxim) creșteri succesive. Prin urmare, avem cel mult 2mv operații; rezultă că avem o coplexitate a algoritmului O(mv).
Exemplul II.2.1.
Să se aplice algoritmul Ford-Fulkrson pentru rețeaua de transport din fig. II.2.1. Obținem mai întâi un flux complet, plecând de la fluxul cu componente nule pe fieare arc, saturând toate drumurile de la intrare la ieșire. Dacă saturăm drumurile în odinea (1,2,6,8), (1,2,5,8), (1,4,7,8), (1,3,6,8), (1,3,6,7,8) se obține un flux complet.
Pe primele poziții am trecut capacitățile iar pe următoarele valoarea fluxului.
Vom eticheta vârfurile, începând cu intrarea 1 pe care o vom eticheta cu [+]. În fiecare căsuță asociată unui nod a fost trecut nodul de la care s-a făcut etichetarea cu semnul [+] sau [-], după cum arcul pe care se face etichetarea este îndreptat către nodul nou etichetat.
Deoarece ieșirea 8 a fost etichetată, fluxul nu este maxim.
Pentru a găsi lanțul pe care poate fi mărginit fluxul cercetând etichetele plecând din 8: ieșirea are marcajul [+5] deci există vârful 5 care are eticheta [+2], vârful 2 care are eticheta [-6], vârful 6 care are eticheta [+3], vârful 3 are eticheta [+1], deci pentru mărirea fluxului vom utiliza lanțul nesaturat [1,3,6,2,5,8].
Pentru acesta găsim . Prin urmare vom mări fluxul cu câte o unitate pe arcele (1,3),(3,6),(2,5) și (5,8) și vom micșora cu o unitate fluxul pe arcul (2,6).
Se obține fluxul din fig.II.2.1. pentru care nu mai putem eticheta iesirea, prin urmare acest flux este de valoare maximă.
Pentru a putea obține o tăietură minimă vom considera mulțimea vârfurilor nemarcate (în momentul în care nu mai putem eticheta ieșirea) din fig. II.2.2., adică . a cărei capacitate este Fluxul . Observăm că se verifică pentru această rețea teoria Ford-Fulkerson.
Dacă M este o margine superioară a capacității arcelor atunci ((n-1) M este o margine superioară a capacității secțiunii , rezultă că algoritmul are complexitatea O(nmM).
Observație:
Prezentăm în continuare un exemplu datorat lui Lovasz (1970) care arată că în cazul datelor iraționale (pentru comoditate vom considera capacitățile raționale, dar fluxul inițial cu componente iraționale) un algoritm de tipul celui descris mai sus în demonstrarea teoremei II.2.1., nu numai că nu se va opri (se va repeta la infinit pasul 2) ci va produce și un șir de fluxuri , n- număr natural cu proprietatea că nu converge la valoarea fluxului maxim.
Fie rețeaua desenată mai jos în care fiecare arc are capacitatea 1 și are precizat pe el fluxul inițial ( – unica rădăcină a ecuației)
Evident, . Considerăm:
Oricare ar fi , fluxul curent va fi transformat în , folosind creșteri succesive ale drumurilor valoarea sa crescând cu .
Valorile fluxului pe arcele (x0,x1), (x0,x3) se calculează în mod similar. Valoarea fluxului este 4, considerând câte o unitate de flux pe fiecare arc (x0,xi), (xi,x5) , acesta este un flux maxim pentru că
Avem . Prin urmare
Observație:
Dezavantajele algoritmului sunt legate de neconvergența în cazul capacităților iraționale (deși, practic, în implementări nu este cazul) și de faptul că mărimile capacităților influențează comportarea sa, acestea constituind o măsură a volumului datelor de intrare.
De exemplu:
Dacă „alegerea” din pasul 2 al algoritmului face ca drumurile de creștere succesive, când se pornește de la fluxul nul, să fie unde atunci la fiecare creștere a fluxului mărește cu o unitate valoarea fluxului curent, deci vor fi necesare 2M creșteri, ceea ce este imposibil pentru foarte mari.
Teorema II.2.2. Fie o rețea de transport G(V,U,c) și v valoarea fluxului maxim din rețea. Atunci următoarele afirmații sunt echivalente:
1) v este flux maxim în rețea
2) Rețeaua de transport nu conține nici un drum de creștere
3) Există o tăietură pentru care v =
Observații:
1. Teorema indică și algoritmul de determinare a tăieturii de capacitate minimă într-o rețea de transport: se aplică algoritmul Ford-Fulkerson și se rețin nodurile la care putem ajunge din sursă în momentul în care nu mai avem drumuri de creștere. Aceste noduri vor forma mulțimea care caracterizează tăietura de capacitate minimă. Așa cum am demonstrat în teorema de mai sus, valoarea tăieturii de capacitate minimă este egală cu valoarea fluxului maxim.
2. În momentul în care într-o rețea de transport avem asociat pentru fiecare arc, pe lângă capacitate și un cost unitar, atunci se pune problema aflării unui flux maxim de cost minim. Această problemă se poate rezolva tot cu ajutorul algoritmului Ford-Fulkerson, cu condiția ca la fiecare pas să se determine un drum de creștere de cost minim. Aflarea unui astfel de drum este posibilă folosind algoritmul Bellman-Ford. Algoritmul Dijkstra nu se poate aplica în acest caz, deoarece – așa cum am arătat într-un articol precedent – acest algoritm nu funcționează în cazul existenței muchiilor negative, iar în acest caz costul arcelor introduse de algoritm va putea fi negativ.
3. Alte situații speciale care pot apărea sunt:
– rețea de transport cu mai multe surse și mai multe destinații: în acest caz introducem o supersursă ss și o superdestinație st. Ducem de la ss la toate sursele arce de capacitate și de asemenea, de la toate destinațiile la st arce de capacitate. În acest fel am redus problema la determinarea fluxului într-o rețea de transport cu o singură sursă ss și o singură destinație st;
– rețea de transport cu capacități și în noduri, adică într-un nod poate intra o cantitate de apă cel mult egală cu capacitatea nodului respectiv. În acest caz, desfacem fiecare nod n în două noduri n1 și n2, între care punem un arc de capacitate egală cu capacitatea nodului n. Toate arcele care intrau în nodul inițial n vor intra acum în nodul n1, iar toate arcele care ieșeau din nodul inițial n vor ieși acum din nodul n2. Astfel, am redus problema la determinarea fluxului maxim într-o rețea de transport cu capacități doar pe arce;
– problema cuplajului maxim într-un graf bipartit este un caz particular de flux maxim într-o rețea de transport. Să presupunem că avem o listă de n elevi și n licee și o listă de preferințe de forma (e, l) având semnificația că elevul e dorește să studieze la liceul l. Fiecare elev poate să dorească în egală măsură să studieze la mai multe licee. Problema cere ca – dacă este posibil – să se atașeze fiecărui elev un liceu unic, astfel încât fiecare elev să fie repartizat într-un liceu în care dorește să studieze.
Problema se modelează printr-un graf bipartit, având pe de o parte mulțimea elevilor, iar pe de cealaltă parte mulțimea liceelor. Între un elev și un liceu există arc doar dacă elevul dorește să studieze la liceul respectiv. Problema cere selectarea unui număr maxim de arce ale grafului bipartit, astfel încât fiecărui elev să-i fie asociat un liceu unic și invers. În cazul în care numărul maxim de perechi valide este n, problema are soluție. Pentru rezolvare, introducem o sursă virtuală s și o destinație virtuală t. Ducem arc între nodul sursă și fiecare elev, și între fiecare liceu și nodul destinație. Toate arcele din problemă vor avea capacitatea 1. Astfel, ne asigurăm că fiecărui elev îi este asociat un singur liceu și invers. Am redus și de această dată problema la determinarea unui flux maxim într-o rețea de transport.
II.3. Algoritmul Edmonds-Karp
Algoritmul Edmonds-Karp, publicat de Jack Edmonds și Richard Karp reprezintă o implementare eficientă a algoritmului Ford Fulkerson.
Ideea care stă la baza algoritmului este de a identifica la fiecare pas un drum de creștere care conține un număr minim de arce.
Definiție II.3.1. Numim drum minim de creștere a fluxului în rețeaua de transport RG=(V,U, c) un drum de creștere de lungime minimă în raport cu toate drumurile de creștere din rețea.
Fie un flux oarecare în rețeaua RG=(V,U,c). Definim șirul de fluxuri din RG astfel:
este un drum minim de creștere relativ la
Notăm pentru
lungimea minimă a unui c-drum de la la în RG relativ la .
lungimea minimă a unui c-drum de la la în RG relativ la .
Lema II.3.1. Pentru și k=0,1,2,… avem și .
Teoremă II.3.1. Dacă este un flux oarecare în rețeaua RG=(V,U,c) atunci șirul de fluxuri obținut din prin creșteri succesive pe drumuri minime de creștere are cel mult elemente (în cel mult creșteri succesive, se obține un flux care nu admite drumuri de creștere).
Cosecință II.3.1. Dacă RG=(V,U,c) este o rețea de transport atunci există un flux care nu admite drumuri de creștere.
Teoremă II.3.2. Dacă la pasul 2 al algoritmului Ford-Fulkerson alegerea vârfurilor etichetate în vederea cercetării se face după regula „primul etichetat-primul cercetat” atunci drumurile de creștere care se depistează sunt cu număr minim de arce.
Demonstrație:
Fie un drum de creștere găsit și fie un drum minim de creștere.
Presupunem că .
Considerăm arcele lor:
Conform regulii de etichetare primește etichetă înaintea lui dar primește etichetă înaintea lui ; primește etichetă înainte lui și așa mai departe, obținându-se inductiv că primește etichetă înaintea lui , deci primește etichetă pe drumul înainte de a primi etichetă pe drumul , ceea ce este absurd.
Observație: Regula „primului etichetat-primul intrat” corespunde unei explorări BFS a vârfurilor etichetate, ceea ce se poate realiza utilizând o coadă pentru memorarea vârfurilor etichetate. Aceasta nu afectează complexitatea algoritmului care va necesita O(m) operații pentru fiecare creștere a fluxului.
Teorema II.3.4. (Edmonds-Karp 1972)
Dacă se modifică algoritmul Ford-Fulkerson cu precizarea BFS a vârfurilor etichetelor în vederea cercetării, atunci fluxul maxim se obține în O(m2n) operații.
Programul de determinare a fluxului maxim într-o rețea de transport cu algoritmul Ford-Fulkerson și îmbunătățirea adusă de Edmonds și Karp
Program Flux_maxim_Ford_Fulkerson;
type coada=record {Coada in care se tine pentru fiecare element}
x,num:integer; {x numarul de pasi din care s-a ajuns la el}
v:array[1..50] of integer; {si drumul (v) de la nodul sursa la el}
end;
var f,g:text;
a,cap,flux:array[1..50,1..50] of integer;
cd:array[1..50] of coada;
fost:array[1..50] of boolean;
fost2:array[1..50] of integer;
flux_max,nrv,start,finish,sfarsit,inceput:integer;
procedure citire; {Se citeste reteaua din fisier}
var x,y,cp,fl:integer;
begin
assign(f,'flux.in'); reset(f);
readln(f,nrv,start,finish); {Se citesc numarul de noduri, nodul sursa si nodul}
{destinatie}
while not eof(f) do begin
readln(f,x,y,cp); {Se citeste legatura dintre x si y}
{si capacitatea cp}
a[x,y]:=1; a[y,x]:=2; {x->y este arc direct, iar y->x este arc invers}
cap[x,y]:=cp; flux[x,y]:=0; {Initial fluxul este 0}
cap[y,x]:=cp; flux[y,x]:=0;
end;
close(f);
end;
procedure update(t:coada); {Procedura de actualizare a retelei principale}
var i,min:integer; {Parametrul de tip coada primit de procedura are rolul}
begin {de a indica drumul in crestere pe care se aplica actualizarea}
{acesta fiind t.v}
min:=maxint;
{Se calculeaza minimul valorii reziduale de pe drumul in crestere}
for i:=1 to t.num-1 do begin
if a[t.v[i],t.v[i+1]]=1 then begin
if cap[t.v[i],t.v[i+1]]-flux[t.v[i],t.v[i+1]]<min then
min:=cap[t.v[i],t.v[i+1]]-flux[t.v[i],t.v[i+1]];
end else begin
if flux[t.v[i],t.v[i+1]]<min then
min:=flux[t.v[i],t.v[i+1]];
end;
end;
{Se actualizeaza reteaua principala: pe arcele directe se aduna la}
{fluxul existent minimul obtinut la pasul anterior si pe arcele inverse}
{se scade din fluxul existent minimul obtinut anteior}
for i:=1 to t.num-1 do begin
if a[t.v[i],t.v[i+1]]=1 then begin
flux[t.v[i],t.v[i+1]]:=flux[t.v[i],t.v[i+1]]+min;
flux[t.v[i+1],t.v[i]]:=flux[t.v[i],t.v[i+1]];
end else begin
flux[t.v[i],t.v[i+1]]:=flux[t.v[i],t.v[i+1]]-min;
flux[t.v[i+1],t.v[i]]:=flux[t.v[i],t.v[i+1]];
end;
end;
end;
procedure adauga(x:integer); {Procedura de adaugare in coada}
begin
inc(sfarsit);
cd[sfarsit].x:=x;
fost[x]:=true;
if sfarsit=1 then begin
cd[sfarsit].num:=1;
cd[sfarsit].v[1]:=x;
fost2[x]:=1;
end else begin
cd[sfarsit].v:=cd[inceput].v;
cd[sfarsit].num:=cd[inceput].num+1;
cd[sfarsit].v[cd[sfarsit].num]:=x;
fost2[x]:=cd[sfarsit].num;
end;
end;
procedure prog;
var bun:boolean;
i:integer;
t:coada;
begin
bun:=false;
fillchar(flux,sizeof(flux),0);
while bun=false do begin
bun:=true;
fillchar(cd,sizeof(cd),0);
fillchar(fost,sizeof(fost),false);
fillchar(fost2,sizeof(fost2),0);
inceput:=1;
sfarsit:=0;
adauga(start);
while inceput<=sfarsit do begin
for i:=1 to nrv do
if (a[cd[inceput].x,i]>0)and
(((a[cd[inceput].x,i]=1)and(cap[cd[inceput].x,i]>flux[cd[inceput].x,i]))
or((a[cd[inceput].x,i]=2)and(flux[cd[inceput].x,i]>0)))and
((fost[i]=false)or((fost[i]=true)and(cd[inceput].num+1<fost2[i])))
then adauga(i);
inc(inceput);
if cd[inceput].x=finish then begin
bun:=false;
t:=cd[inceput];
update(t);
end;
if bun=false then break;
end;
end;
flux_max:=0;
for i:=1 to nrv do
flux_max:=flux_max+flux[i,finish];
end;
Begin
citire;
assign(g,'flux.out'); rewrite(g);
prog;
write(g,flux_max);
close(g);
End.
II.4. Algoritmul Dinic
O altă modalitate de a rezolva problema fluxului maxim este și algoritmul Dinic.
Descrierea algoritmului:
1. Se construiește o rețea stratificată ce folosește muchiile utile (cu capacitate reziduală nenulă) dintre sursă și destinație.
2. Dacă rețeaua nu poate fi construită (nu putem ajunge de la sursă la destinație construind rețeua) înseamnă că s-a atins fluxul maxim => stop
3. Valorile fluxului muchiilor sunt modificate astfel încât să se obțină un flux maxim în rețeaua stratificată.
4. Valorile determinate în rețeaua stratificată sunt folosite pentru modificarea valorilor din rețeaua principală.
5. Se reia de la punctul 1.
Construcția rețelei stratificate:
În v(i) reținem toate nodurile stratului i care sunt legate direct de nodurile stratului i+1.
1. Inițial v(0) va conține doar nodul sursă, i=0. Se marchează sursa ca fiind vizitat, iar celelalte noduri ca fiind nevizitate.
2. Vom lua rând pe rând nodurile x din v(i) și pentru toate muchiile utile (x,y), unde y este un nod nevizitat, vom adăuga pe y în v(i+1), marcându-l ca fiind vizitat.
Pentru fiecare muchie utilă e, muchia directă (x,y) adăugată în rețeaua stratificată, se asociază o capacitate c1(e)=r(x,y) și un flux φ1(e)=0. Pentru muchia (x,y) avem un pointer C ce indică spre e și un câmp boolean R care ne indică direcția lui e.
3. Incrementăm i.
4. Dacă v(i) e gol atunci fluxul e maxim => stop
5. Dacă v(i) conține nodul destinație atunci am terminat de construit rețeaua stratificată => stop
6. Reluăm de la puncutul 2.
Căutarea drumurilor în creștere:
În descrierea de mai jos: d1(e)=c1(e)-φ1(e), St=stiva
1. Inițial toate muchiile sunt notate ca fiind neblocate, iar stiva St
este goală.
2. x=sursa;
3. Parcurgem muchiile neblocate cu originea în x
4. Dacă nu există muchii neblocate atunci
4.1 Dacă St este goală atunci avem flux maxim = >stop
4.2 Extragem muchia e=(k,p) din St și marcăm e ca blocată
4.3 Continuăm cu pasul 3 pentru x=k
5. Else
5.1 Pune muchia neblocată e=(x,y) în St și x=y
5.2 Dacă x e diferit de v atunci continuăm cu pasul 3
6. Pentru x=v avem un drum de creștere în stivă și fluxul trebuie
crescut:
6.1 p=min(d1(e1), …, d1(ek)) unde e1, …, ek sunt muchiile
drumului.
6.2 Pentru fiecare muchie e din drum φ1(e)=φ1(e)+p și dacă
φ1(e)=c1(e) atunci marcăm pe e ca fiind blocat
6.3 Salt la pasul 2.
Actualizarea rețelei principale:
Odată determinat fluxul maxim în rețeaua stratificată va trebui să modificăm fluxul pe fiecare muchie a rețelei principale după cum urmează:
Pentru fiecare muchie e a rețelei stratificate
Dacă e->R este true atunci
φ(e^.C)= φ (e^.C)- φ 1(e)
altfel φ (e^.C)= φ (e^.C)+ φ1(e)
Observație:
Avantajul acestui algoritm este complexitatea mai mică decât a algoritmului Ford-Fulkerson: O(K*N^2) față de O(N*K^2) unde N este numărul de noduri și K este numărul de legături.
Programul de determinare a fluxului maxim într-o rețea de transport folosind algoritmul Dinic
Program flux_maxim_Dinic;
const n1=20;
nc=500;
type coada=record
h:boolean;
nr:integer;
end;
coada2=record
ind,nrp:integer;
end;
stiva=record
x,y:integer;
end;
var a,a1:array[1..n1,1..n1] of integer;
cap,flux,cap2,flux2:array[1..n1,1..n1] of integer;
aux:array[1..n1] of coada;
v:array[1..nc] of coada2;
st:array[1..nc] of stiva;
bloc:array[1..n1,1..n1] of boolean;
Flux_Maxim,nrst,i,j,n,nre,s,t:integer;
strat:boolean;
f,g:text;
procedure citire; {Se citeste reteaua din fisier}
var x,y,cp,fl:integer;
begin
assign(f,'flux.in'); reset(f);
readln(f,n,s,t); {Se citesc numarul de noduri, nodul sursa si nodul destinatie}
while not eof(f) do begin
readln(f,x,y,cp); {Se citeste legatura dintre x si y}
{si capacitatea cp}
a[x,y]:=1; a[y,x]:=2; {x->y este arc direct, iar y->x este arc invers}
cap[x,y]:=cp; flux[x,y]:=0; {Initial fluxul este 0}
cap[y,x]:=cp; flux[y,x]:=0;
end;
close(f); end;
procedure adaugare(x,k,cp:integer); {Procedure de adaugare in coada}
{Se adauga nodul x si, numarul de pasi}
{din care s-a ajuns in nodul x si se}
{pune (in reteaua stratificata) capacitatea}
{legaturii dintre primul nod din coada si x
{pe valoarea cp}
begin
inc(nre);
if x=t then strat:=true;
v[nre].ind:=x; v[nre].nrp:=k;
aux[x].h:=true; aux[x].nr:=k;
if x<>s then begin
cap2[v[1].ind,x]:=cp; flux2[v[1].ind,x]:=0;
a1[v[1].ind,x]:=1; a1[x,v[1].ind]:=2; {Se marcheaza in matricea a1}
{tipul de arc dintre cele doua noduri:}
{1=arc direct; 2=arc invers}
end;
end;
procedure sterge; {Procedura de stergere a primului nod din coada}
var i:integer;
begin
for i:=1 to nre-1 do v[i]:=v[i+1];
dec(nre);
end;
procedure retea_stratificata; {Procedura de formare a retelei stratificate}
var i:integer;
begin
nre:=0; adaugare(s,0,0); {Se adauga nodul sursa in coada}
while nre>0 do begin {Cat timp mai sunt elemente in coada}
for i:=1 to n do
if (a[v[1].ind,i]>0)
and(((cap[v[1].ind,i]>flux[v[1].ind,i])and(a[v[1].ind,i]=1))
or((a[v[1].ind,i]=2)and(flux[v[1].ind,i]>0)))
and((aux[i].h=false)
or(aux[i].nr>=aux[v[1].ind].nr+1)) then
begin
{Daca intre primul element din coada si nodul i este arc direc}
{si :capacitatea este mai mare decat fluxul, sau daca este arc}
{invers si fluxul pe el este mai mare decat 0, si daca nodul}
{i nu a fost introdus in coada sau daca a fost introdus dar numarul}
{de pasi este mai mic decat cel obtinut la introducerea anterioara atunci}
if a[v[1].ind,i]=1 then adaugare(i,aux[v[1].ind].nr+1,cap[v[1].ind,i]-flux[v[1].ind,i])
else adaugare(i,aux[v[1].ind].nr+1,flux[v[1].ind,i])
{Daca este arc direct se adauga in coada nodul i si capacitatea=capacitatea-fluxul in momentul}
{respectiv; daca este arc invers se adauga in coada nodul i si capacitatea=fluxul in momentul}
{respectiv}
end;
sterge; {Se sterge primul nod din coada}
end; end;
procedure drum; {Procedure de determinare a fluxului pe un drum in crestere}
{dintr-o retea stratificata si de blocare a legaturilor care}
{nu mai pot fi folosite (au valoarea reziduala egala cu 0);}
{valoare reziduala=diferenta dintre capacitatea si fluxul unei}
{legaturi}
var min:integer;
begin
min:=cap2[st[1].x,st[1].y]-flux2[st[1].x,st[1].y];
for i:=2 to nrst do
if cap2[st[i].x,st[i].y]-flux2[st[i].x,st[i].y]<min then
min:=cap2[st[i].x,st[i].y]-flux2[st[i].x,st[i].y];
{Se gaseste minimul valorii reziduale din drumul in crestere}
for i:=1 to nrst do begin
flux2[st[i].x,st[i].y]:=flux2[st[i].x,st[i].y]+min;
if flux2[st[i].x,st[i].y]=cap2[st[i].x,st[i].y] then
bloc[st[i].x,st[i].y]:=true;
{Se aduna minimul valorii reziduale la fluxul fiecarei}
{legaturi si in cazul in care noul flux este egal cu capacitatea}
{respectivei muchii se blocheaza muchia}
end;
end;
procedure drumuri_de_crestere(i:integer); {Procedure recursiva de determinare a drumurilor in crestere}
var j:integer;
r:boolean;
begin
for j:=1 to n do {Se iau pe rand toate nodurile}
if (cap2[i,j]>0)and(bloc[i,j]=false) then begin
{In cazul in care capacitatea legaturii i-j este mai mare decat 0}
{si muchia nu este blocata}
inc(nrst); {Creste numarul legaturilor din stiva}
st[nrst].x:=i; st[nrst].y:=j; {Se pun in stiva nodurile i si j (care sun legate intre ele)}
if j=t then begin {Daca s-a ajuns la destinatie inseamna ca s-a obtinut un drum in crestere}
drum; {deci se apeleaza procedura drum care determina fluxul pe un drum in crestere}
nrst:=0; {Se goleste stiva}
fillchar(st,sizeof(st),0);
drumuri_de_crestere(s); {Se apeleaza procedura de detrminare a drumurilor in crestere din nodul sursa}
end else begin {Daca nu s-a ajuns la destinatie}
drumuri_de_crestere(j); {Se apeleaza procedura de detrminare a drumurilor in crestere din nodul j}
bloc[st[nrst].x,st[nrst].y]:=true; {La revenire se blocheaza prima legatura din stiva (care sigur nu}
{va intra in componenta unui drum in crestere)}
st[nrst].x:=0; st[nrst].y:=0; {Se sterge din stiva legatura respectiva}
dec(nrst);
end;
end;
end;
procedure update_retea_principala; {Procedure de actualizare a retelei principale}
var i,j:integer;
begin
for i:=1 to n do
for j:=1 to n do
if cap2[i,j]>0 then begin {In cazul in care capacitatea pe arcul i-j}
{in reteaua stratificata este mai mare decat 0 atunci}
if a[i,j]=a1[i,j] then begin {Daca arcul din reteaua principala coincide }
{cu arcul din reteaua stratificata (amandoua sunt}
{fie arce directe fie inverse) atunci}
flux[i,j]:=flux[i,j]+flux2[i,j]; {fluxul pe arcul i-j creste cu fluxul din}
flux[j,i]:=flux[i,j]; {reteaua stratificata}
end
else begin
flux[i,j]:=flux[i,j]-flux2[i,j]; {altfel fluxul pe arcul i-j scade cu fluxul din}
flux[j,i]:=flux[i,j]; {reteaua stratificata}
end;
end;
end;
procedure init;
var i:integer;
begin
for i:=1 to n1 do begin
aux[i].h:=false; aux[i].nr:=0; end;
fillchar(cap2,sizeof(cap2),0); fillchar(flux2,sizeof(flux2),0);
fillchar(v,sizeof(v),0); fillchar(a1,sizeof(a1),0);
end;
Begin
citire;
assign(g,'flux.out'); rewrite(g);
fillchar(bloc,sizeof(bloc),false);
repeat
strat:=false; {Variabila care daca este true inseamna ca s-a reusit formarea unei retele stratificate}
init; retea_stratificata; {Se apeleaza procedura de formare a retelei stratificate}
fillchar(st,sizeof(st),0);
nrst:=0; fillchar(bloc,sizeof(bloc),false);
if strat=true then begin {Daca s-a reusit formarea acesteia}
drumuri_de_crestere(s); {atunci se gasesc drumurile in crestere din nodul sursa}
update_retea_principala; {si se actualizeaza reteaua principala}
end;
until strat=false; {pana cand nu se mai poate forma o retea stratificata care sa contine}
{nodul sursa si nodul destinatie}
Flux_Maxim:=0;
{Se calculeaza fluxul maxim ca fiind suma fluxurilor ce ies din nodul sursa}
{Fluxul intre un nod sursa si unul destinatie are sens doar daca nodul sursa}
{nu are decat arce care ies din el, iar cel destinatie doar arce care intre}
{in el}
for i:=1 to n do
if a[s,i]>0 then
if a[s,i]=1 then Flux_Maxim:=Flux_Maxim+flux[s,i];
writeln(g,'Fluxul maxim este: ', Flux_Maxim);
close(g);
End.
III. CUPLAJ MAXIM ÎN GRAFURI BIPARTITE
În cele ce urmează vom trata problema numai pentru grafurile neorientate (în cazul grafurilor orientate problema este tratată în mod analog).
Definiție III.1. Fie G=(V,U) un 1-graf neorientat. Numim cuplaj al lui G o submulțime de muchii care au proprietatea că nu au extremități comune două câte două.
Cu alte cuvinte, putem defini un cuplaj dintr-un graf ca fiind o submulțime a mulțimii muchiilor astfel încât aceasta să nu conțină muchii adiacente.
Practic, vom lega nodurile două câte două, fiecare nod fiind legat cel mult o dată de alt nod.
De exemplu, în fig. III.1. muchiile [1,2], [4,5], [6,7] fac parte dintr-un cuplaj.
Observații
1. Pentru un graf neorientat cu n noduri un cuplaj va avea cel mult [n/2] noduri.
2. Într-un graf neorientat un cuplaj nu este unic.
Definiție III.2. Numim cuplaj maxim un cuplaj cu proprietatea că orice muchie care nu face parte din cuplaj este incidentă cu o muchie din cuplaj.
În mod evident, un cuplaj maxim reprezintă cuplajul pentru care cardinalul mulțimii muchiilor alese este cel mai mare posibil.
Cuplajul din Fig. III.1. este maxim deoarece graful conține 7 noduri iar cuplajul 3 muchii (numărul maxim posibil) și orice altă muchie am alege observăm că ea nu mai poate face parte din cuplaj.
Observație
Nu în orice graf putem găsi un cuplaj maxim cu [n/2] muchii.
De exemplu, în graful din fig.III.2. cuplajul maxim poate avea doar 2 muchii, spre exemplu muchiile [1,2] și [3,4] iar numărul de muchii este 7.
Definiție III.3. Prin dimensiunea unui cuplaj M, notată vom înțelege numărul de muchii din M.
Definiție III.4. Un vârf se numește vârf saturat într-un cuplaj dacă el este o extremitate a unei muchii din cuplaj. În caz contrar se numește vârf nesaturat.
Definiție III.5. O muchie care face parte dintr-un cuplaj M se numește muchie cuplată. Dacă muchia se află în U-M se numește muchie liberă sau muchie necuplată.
Pentru exemplul din Fig. III.2. muchiile [1,2] și [3,4] sunt muchii cuplate iar celelalte muchii sunt muchii libere și toate nodurile sunt noduri saturate. Însă, în Fig.III.1. muchiile [1,2], [4,5], [6,7] sunt muchii cuplate, nodurile 1,2,4,5,6,7 sunt noduri saturate iar nodul 3 este nesaturat.
Definiție III.6. Numim lanț alternat relativ la un cuplaj M un lanț elementar cu proprietatea că muchiile lui aparțin alternativ lui M și lui U-M.
De exemplu în Fig. III.2 lanțul [2,1,4,3,5] este un lanț alternat.
Reamintim definția unui graf bipartit și a unui graf bipartit complet.
Definiție III.7. Un graf G=(V,U) se numește bipartit dacă există două mulțimi nevide A, B astfel încât V=A U B, A∩B = și orice muchie a lui G are o extremitate în A iar cealaltă în B.
Definiție III.8. Un graf bipartit se numește complet dacă pentru orice x din A și y din B, există muchia (x,y).
Este evident faptul că pentru grafurile bipartite cuplajul va consta din stabilirea unei „corespondențe” între nodurile dintre cele două mulțimi, fiecărui nod din prima mulțime corespunzându-i cel mult un nod din cea de-a doua mulțime, prin urmare corespondența este dată de definirea unei funcții injective. Astfel, numărul muchiilor care fac parte din cuplajul maxim va fi limitat de cardinalul mulțimii cu cele mai puține noduri. De exemplu, în Fig. III.1. cuplajul este maxim deoarece avem 3 muchii și fiecare dintre cele două mulțimi conține câte 3 elemente.
În practică întâlnim multe cazuri în care este nevoie să asociem într-un mod optim elementele a două mulțimi în condițiile unor restricții cunoscute cu privire la posibilitățile de asociere.
În general, fiecare asociere a două noduri și conduce la un profit care poate fi calculat. Restricțiile cu privire la asociere constau în aceea că unui element din mulțimea A i se poate asocia doar anumite elemente din B și invers.
Criteriul de optimalitate în procesul de asociere constă în realizarea a două obiective:
realizarea unui număr maxim de asocieri
profitul (costul) total să fie maxim (minim) în funcție de scopul propus.
Această activitate paote fi modelată din punct de vedere al teoriei grafurilor, folosind un graf bipartit în care muchiile/arcele au o anumită semnificație.
Definiție III.8. Un cuplaj într-un graf bipartit constă într-o submulțime de muchii cu proprietatea că pentru orice nod există cel mult o astfel de muchie incidentă lui.
Definiție III.9. Numim cuplaj perfect un cuplaj M al lui G=(V,U) în care fiecare nod este saturat.
Definiție III.10. Un lanț alternat, relativ la un cuplaj M, se numește lanț augmentat dacă extremitățile lanțului sunt vârfuri distincte și libere.
Dacă M este un cuplaj și L este un lanț augmentat relativ la M, atunci mulțimea reprezintă un cuplaj de dimensiune . Se observă că acest cuplaj coincide cu M pe muchiile din complementarul lui L, fiecare muchie din L care este cuplată relativ la M este liberă în raport cu și invers.
Teoremă III.1. (Berge-Norman-Rabin)
Un cuplaj M al unui graf G=(V,U) este maxim nu există lanțuri augmentate în raport cu cuplajul M.
Definiție III.11. Se numește suport sau mulțime transversală a muchiilor unui graf G=(V,U), o mulțime de vârfuri T cu proprietatea că orice muchie din U are cel puțin o extremitate în T.
Definiție III.12. Numim număr de transversalitate al lui G numărul când T parcurge mulțimea suporturilor grafului G.
Observații:
Numărul când M parcurge mulțimea cuplajelor unui graf verifică inegalitatea .
Inegalitatea devine egalitate în cazul grafurilor bipartite.
Transformarea problemei
Pentru a determina cuplajul maxim într-un graf bipartit va trebui să alegem cât mai multe muchii fără ca printre muchiile alese să avem muchii adiacente.
Vom arăta în continuare cum putem rezolva problema transformând graful bipartit într-o rețea de transport.
Pentru început, dacă graful este neorientat vom stabili o orientare a muchiilor (care vor deveni arce) astfel încât ele să plece de la noduri aflate într-una dintre cele două submuțimi și să ajungă la noduri aflate în cealaltă submulțime. De asemenea, vom atribui fiecărui arc câte o capacitate egală cu 1.
Pentru a obține însă o rețea de transport avem nevoie de o sursă și o destinație. Vom introduce în mod artificial cele două noduri s (sursa) și respectiv t (destinația).
Din sursă vor pleca noduri către nodurile din prima submulțime (cea care conține noduri din care pleacă arce în graful bipartit) iar la destinație vor ajunge arce din toate nodurile celei de-a doua submulțimi.
Sursa introdusă astfel se mai numște și sursă virtuală iar destinația se mai numește destinație virtuală.
Toate arcele care pleacă din sursă și toate arcele care ajung în destinație au capacitățile egale cu 1.
Prin urmare după găsirea fluxului maxim putem afla și cuplajul maxim ca fiind format din muchii pe care există fluxuri nenule.
Descrierea algoritmului pentru găsirea unui cuplaj maxim într-un graf bipartit
Determinarea unui cuplaj complet
Se vor selecta, într-un mod oarecare, muchii din mulțimea U care să nu aibă, două câte două, extremități comune. Când acest proces de selectare nu mai poate fi continuat înseamnă că am obținut un cuplaj complet ( are o extremitate comună cu o muchie din M). De fapt, găsirea unui cuplaj complet corespunde determinării unui flux complet în rețeaua de transport asociată.
Dacă în graful G există cel mult un nod nesaturat relativ la cuplajul M, atunci cuplajul este maxim și algoritmul se încheie. De asemenea, algoritmul se încheie și dacă toate vârfurile nesaturate se află în A sau în B pentru că nu există lanțuri alternate care să aibă extremități vârfuri libere.
Dacă există două vârfuri nesaturate și atunci vom căuta un lanț alternat care să aibă extremități aceste vârfuri și care să permită obținerea unui cuplaj cu o dimensiune mai mare.
În acest scop este nevoie să utilizăm un algoritm de etichetare a vârfurilor.
Determinarea cuplajului maxim
Se etichetează cu [+] toate vârfurile nesaturate din A. Dacă vârful este etichetat atucni se etichetează cu orice vârf neetichetat care este o extremitate a muchiei .
Dacă vârful este etichetat atunci se etichetează cu orice vârf neetichetat care este o extremitate a unei muchi cuplate .
După acest proces de etichetare, dacă mai există un vârf nesaturat atunci există un lanț alternat de la un nod nesaturat din A la vârful , lanț ce se poate identifica cu ajutorul etichetelor asociate vârfurilor din graful G.
În general cuplajul obținut nu este maxim, dimensiunea lui putându-se mări prin schimbarea, în mod corespunzător, a muchiilor din M cu cele din U-M. Se vor șterge etichetele vârfurilor și se va relua pasul 2 pentru noul cuplaj găsit.
Atunci când nu se va mai putea eticheta nici un vârf nesaturat din B, cuplajul este maxim și algoritmul se încheie.
Algoritm pentru determinarea unui suport minim într-un graf bipartit
Fie G=(V,U), V=A U B, un graf bipartit.
Se determină un cuplaj maxim M0
Fie mulțimile extremităților muchiilor din M0.
Determinăm un suport T al grafului bipartit G astfel:
unde și
Deoarece și rezultă că .
Prin urmare, T este un suport minim al grafului G și, în plus, pentru orice astfel de graf are loc egalitatea . Adică, numărul maxim de muchii ale unui cuplaj este egal cu numărul minim de vârfuri ale unui suport.
Teoremă III.2. (König)
Într-un graf bipartit G=(A,B,U) AUB=V, numărul maxim al arcelor unui cuplaj este , unde U(A’) reprezintă mulțimea vârfurilor adiacente cu A’.
Teoremă III.3. (König-Hall)
Într-un graf bipartit G=(A,B,U) se poate cupla A în B dacă și numai dacă
Demonstrație
Din teorema lui König știm că A se poate cupla în B dacă și numai dacă are loc
ceea ce este echivalent cu
de unde rezultă că
Atunci , deci
Observație
Aplicând teorema (König-Hall) putem găsi întotdeauna un cuplaj dacă din orice submulțime A’ a lui a ce conține p vârfuri pleacă cel puțin p arce.
Exemplul III.1.:
5 muncitori trebuie repartizați la 5 mașini . Știm că fiecare muncitor este calificat numai pentru anumite mașini (ca în fig. III.3.). Este posibil să fie repartizat fiecare muncitor pentru un post pe care este calificat?
Rezolvare
Pentru a găsi un cuplaj maxim se construiește o rețea de transport adăugând o intrare s și o ieșire t și se inversează sensul arcelor în A și B.
Unim intrarea s cu nodurile din B prin arce de capacitate 1, nodurile din A cu s prin arce de capacitate 1 și nodurile cu arce de capacitate tot 1; atunci când muncitorul i poate lucra pe mașina j obținem rețeaua de transport din Fig. III.4.
Ne aflăm în cazul unei rețele de transport pentru care se va căuta fluxul maxim cu ajutorul algoritmului lui Ford-Fulkerson. În Fig. III.5. este indus un flux complet (arcele sunt îngroșate pe arcele coresunzătoare unei valori nenule).
Se observă că toate drumurile de la s la t sunt saturate. În schimb, cu algoritmul Ford-Fulkerson găsim că lanțul [s,6,2,7,1,t] fluxul poate fi ameliorat și conduce la cuplajul maximal din Fig. III.6.
Exemplul III.2.
Să presupunem că avem o listă cu n elevi și n licee precum și o listă de preferințe de forma (e,l) (e-elev, l-liceu) cu semnificația elevul e optează pentru liceul l. Evident, fiecare elev poate opta pentru mai multe licee. Dorim să determină, dacă este posibil, câte o corespondență astfel încât fiecărui elev să-i fie asociat un liceu unic din lista de licee pentru care a optat.
Problema se modelează printr-un graf bipartit în care cele două mulțimi sunt reprezentate de mulțimea elevilor și respectiv de mulțimea liceelor. Între mulțimea elevilor și mulțimea liceelor va exista un arc doar dacă elevul dorește să studieze la liceul respectiv.
Problema se reduce la selectarea unui număr maxim de arce ale grafului bipartit format astfel încât fiecărui elev să-i corespundă un liceu unic și invers. În cazul în care numărul de perechi valide este n am obținut o soluție.
Așa cum am arătat anterior pentru rezolvare introducem o sursă virtuală, o destinație virtuală, câte un arc de la sursă către fiecare elev și câte un arc de la fiecare liceu la destinație. Toate arcele au capacitatea 1 pentru a ne asigura că fiecărui elev îi va asocia un singur liceu și invers, cu alte cuvinte, reducem această problemă la rezolvarea unei probleme de flux maxim într-o rețea de transport.
Analiza complexității algoritmului
În funcție de reprezentarea grafului în memorie, operația de transformare a acestuia va avea ordinul O(n) sau O(m). După efectuarea transformării se va aplica algoritmul de determinare a fluxului maxim care are complexitatea cel puțin O(n·m·(n+m)). Tragem concluzia că ordinul de complexitate al algoritmului este același cu ordinul de complexitate al algoritului ales pentru determinarea fluxului maxim într-o rețea de transport.
IV. PROBLEMA CLASICĂ DE TRANSPORT
Problema clasică de transport face parte din clasa mult mai largă a problemelor modelate prin rețele de transport. O rețea de transport modelează o situație economică în care, dintr-un anumit număr de puncte, numite surse, trebuie transportată o cantitate dintr-o anumită substanță, într-un alt număr de puncte, numite destinații. Situația extrem de generală de mai sus poate fi apoi concretizată într-un număr deosebit de mare de moduri, specificând dacă există sau nu puncte intermediare între surse și destinații, modul în care se face transportul (care sunt rutele posibile, costul transportului, limite minime și/sau maxime pentru cantitatea transportată pe fiecare rută, timpul necesar transportului), scopurile urmărite etc. Din această cauză există o multitudine de probleme care implică rețele de transport, dintre acestea putând aminti:
Problema clasică de transport
Problema transferului
Problema drumului de cost minim
Problema fluxului maxim
Problema fluxului maxim de cost minim
Probleme de flux dinamic
Problema cuplajului maxim
Problema de afectare
Problema de ordonanțare
Problema comis voiajorului
Problema arborelui de cost minim
În continuare o vom detalia pe prima dintre acestea.
Caracteristicile unei probleme de transport clasice sunt:
fiecare sursă aprovizionează cel puțin o destinație și fiecare destinație este aprovizionată de la cel puțin o sursă;
pot exista perechi sursă-destinație între care nu se poate face transfer (rute blocate);
nu există limitări în ceea ce privește cantitatea transportată pe fiecare rută;
se cunosc cantitățile disponibile în fiecare sursă și cantitățile necesare în fiecare destinație;
fiecărei rute i s-a asociat un cost care nu depinde de sensul de parcurgere.
Scopul problemei este găsirea acelor cantități care trebuie transportate pe fiecare rută astfel încât să se asigure necesarul fiecărei destinații, în limitele cantităților aflate la surse, cu costul minim posibil.
Datele problemei sunt:
m = numărul de surse (furnizori);
n = numărul de destinatari (consumatori);
{Ai, i = 1,…,m} = cantitățile disponibile în fiecare sursă;
{Bj, j = 1,…,n} = cantitățile necesare la fiecare sursă;
{cij, i = 1,…,m; j = 1,…,n} = costurile unitare pe fiecare rută (costul transportării unei unități de măsură de la sursa i la destinația j).
Acestea au fost organizate într-un tabel ca cel de mai jos:
Dacă notăm cu xij cantitatea care va fi transportată de la sursa i la destinația j atunci avem de rezolvat problema:
care este un caz particular de problemă de programare liniară.
Într-o primă analiză, se observă imediat că problema nu are soluții admisibile dacă disponibilul total este mai mic decât cererea totală. Matematic, afirmația de mai sus este justificată prin relațiile obținute prin adunarea primelor m restricții și apoi a ultimelor n:
disponibil total = = cerere totală
De asemenea, condiția ca este și suficientă, deoarece, în acest caz, se verifică ușor că soluția este soluție admisibilă.
În altă ordine de idei, chiar dacă disponibilul total este mai mare decât cererea totală, este clar că se va transporta doar necesarul, deoarece transportarea unei cantități mai mari decât necesarul va duce la un cost suplimentar, în contrast cu scopul urmărit. Matematic, unei soluții în care una din ultimele n restricții ar fi verificată strict, îi corespunde o soluție în care am scăzut cantitatea suplimentară din valorile variabilelor implicate în restricție, care este de asemenea admisibilă (aceste variabile nu apar în alte restricții dintre ultimele n, iar primele m vor fi cu atât mai mult verificate dacă xij scad) și care este evident mai bună, dând un cost mai mic.
În concluzie, dacă există soluție optimă, se va transportă exact cantitatea cerută.
Totuși, în practică se poate întâlni oricare din cele trei cazuri:
În primul caz, problema are soluție optimă, iar cantitatea în exces față de cerere va rămâne la furnizori, fiind reprezentată de variabilele de abatere din primele m restricții. Aceste cantități pot fi privite ca niște cereri ale unui consumator fictiv și ținând cont că, de fapt, aceste cantități nu sunt transportate nicăieri, costurile unitare pe rutele care ar lega furnizorii de acest consumator sunt 0. Adăugând acest consumator la tabel, cu cererea egală cu , vom obține o problemă de tipul (3).
Analog, în al treilea caz, chiar dacă disponibilul este mai mic decât necesarul, nu înseamnă că nu se va mai transporta nimic, ci doar că unora dintre consumatori nu li se va satisface toată cererea. Această cerere nesatisfăcută poate fi privită ca disponibilul unui furnizor fictiv și ținând cont că, de fapt, această cantitate nu există, costurile unitare pe rutele care ar lega consumatorii de acest furnizor sunt 0. Adăugând acest furnizor la tabel, cu disponibilul egal cu , vom obține o problemă de tipul (3).
În concluzie, orice problemă poate fi transformată într-o problemă de tipul (3). Deși acest caz este foarte rar în practică, el este cel mai simplu din punct de vedere matematic și va fi ales pentru formalizarea problemei. O astfel de problemă se numește problemă de transport echilibrată.
De asemenea, este ușor de văzut că, pentru o problemă de transport echilibrată, toate soluțiile admisibile verifică toate restricțiile cu egal. Astfel, dacă măcar una din primele m restricții ar fi verificată cu "<" atunci am avea prin însumare:
, în contradicție cu
iar dacă măcar una din ultimele n restricții ar fi verificată cu ">" atunci am avea prin însumare:
, în contradicție cu
În concluzie, orice problemă de transport este echivalentă cu o problemă de forma:
unde
care este forma standard a problemei de transport.
Rezolvarea problemei de transport
Este evident că problema de transport la forma standard este o problemă de programare liniară la forma standard, dar, la fel de evident este și faptul că este o problemă de programare care devine foarte repede uriașă (un exemplu practic obișnuit cu, de exemplu, 50 de furnizori și 50 consumatori, va duce la un tabel simplex de 100 2500, și sunt cazuri și cu mii de furnizori și consumatori), motiv pentru care algoritmul simplex sub forma clasică nu este aplicabil. Cum s-a văzut însă, există și metode prin care se poate reduce mult volumul de calcule (vezi algoritmul simplex revizuit). În plus, datele problemei de transport au o structură cu totul deosebită, în matricea A a sistemului, toate componentele fiind 1 sau 0, din care 0 sunt mult mai mulți. Din acest motiv este natural să căutăm un algoritm special pentru problema de transport care să se folosească la maximum caracteristicile acesteia.
Pentru ilustrarea celor de mai vom scrie matricea A desfășurat:
Această matrice are m + n linii, mn coloane și deci (m + n)mn componente din care doar 2mn sunt 1, restul fiind 0. O problema cu 50 furnizori și 50 consumatori va avea doar un procent de:
= 2% componente egale cu 1
Observând că suma primelor m linii minus suma ultimelor n este 0, rezultă că liniile matricii sunt liniar dependente, deci rangul lui A este mai mic decât m + n. Se poate găsi însă un minor de dimensiune m + n – 1 cu determinantul diferit de 0, deci o bază a unei probleme de transport are dimensiunea m+n–1 și o soluție de bază are cel mult m+n–1 componente diferite de 0 (o soluție nedegenerată are deci m+n–1 componente diferite de 0). Preferarea soluțiilor nedegenerate se face din același motiv ca și la algoritmul simplex și anume evitarea ciclării (la problema de transport este mult mai important acest aspect deoarece soluțiile de bază ale acesteia sunt, în general, puternic degenerate). Înainte de a da algoritmul pentru rezolvarea problemei de transport, trebuie remarcat că într-o problemă de transport nu poate apărea decât varianta de optim finit, existând întotdeauna soluții admisibile (așa cum s-a demonstrat mai sus) iar minimul – nu este posibil, ținând cont că avem de minimizat o funcție liniară cu toți coeficienții pozitivi pe o mulțime de soluții cu toate componentele pozitive.
Ca și în algoritmul simplex, rezolvarea problemei de transport se face în două etape:
Etapa 1. Găsirea unei soluții inițiale de bază
Deoarece fiecare variabilă corespunde unei rute (este cantitatea transportată pe această rută) iar fiecare rută corespunde unei perechi furnizor-consumator, vom identifica fiecare variabilă xij cu ruta (i,j). A găsi o soluție de bază nedegenerată este echivalent cu a găsi cel mult m+n–1 rute, din cele m·n posibile, pe care să transportăm toată cantitatea disponibilă. Rutele vor fi organizate într-un tabel asemănător celui în care sunt organizate datele problemei, fiecărei rute corespunzându-i o căsuță (i,j):
Spre deosebire de algoritmul simplex, găsirea unei soluții inițiale de bază nu este dificilă. De fapt, este atât de ușor de găsit o astfel de soluție, încât există o multitudine de metode în acest scop, care încearcă nu numai găsirea acesteia, ci chiar găsirea uneia cât mai bună. Vom expune dintre acestea:
Metoda nord – vest;
Metoda minimului pe linii;
Metoda minimului pe coloane;
Metoda costului minim;
Metoda diferențelor maxime;
Cu toate că sunt foarte multe, toate metodele urmează o schemă comună:
I. Se alege o rută inițială după o anumită regulă. Această regulă diferă în funcție de metoda folosită, fiind:
II. Se transportă pe această rută maximul posibil. Acest maxim este egal cu minimul dintre cantitatea care mai e disponibilă la furnizorul corespunzător acestei rute și cantitatea care mai e necesară la consumatorul corespunzător rutei, în momentul alegerii acestei rute. Se transportă în acest fel pentru ca să se folosească cât mai puține rute și deci să se obțină o soluție de bază.
III. După folosirea unei rute este clar că fie se epuizează disponibilul furnizorului corespunzător, fie se asigură întregul necesar al consumatorului corespunzător, fie ambele. Dacă se epuizează disponibilul furnizorului este clar că nici o rută care pleacă de la acesta nu va mai fi folosită și analog, dacă se asigură întregul necesar al consumatorului, nici o rută spre acesta nu va mai fi folosită. Rutele care nu vor mai fi folosite se numesc rute blocate, sunt cele nefolosite încă de pe linia sau /și coloana ultimei rute folosite și se evidențiază în tabel prin hașurarea acestora.
IV. Se alege următoarea rută, folosind regula:
V. Se reia algoritmul de la pasul 2 până când nu mai rămâne nici o rută nefolosită sau neblocată.
Se observă că, dacă prima metodă este pur geometrică, neținând cont de costurile rutelor, toate celelalte încearcă să micșoreze cât mai mult costul întregului transport. Cu toate că, statistic vorbind, ultima metodă este cea mai bună, ea dând de foarte multe ori chiar soluția optimă, totuși și existența celorlalte metode este justificată de faptul că sunt mai simplu de aplicat și există cazuri în care fiecare dă soluția cea mai bună.
Etapa 2. Găsirea soluției optime
Algoritmul care urmează reprezintă algoritmul simplex pentru o problemă de minim, aplicat în cazul particular al problemei de transport.
I. Se asociază fiecărui furnizor Fi o variabilă ui și fiecărui consumator Cj o variabilă vj;
II. Fiecărei rute (i,j) folosită în soluția actuală i se asociază ecuația ui + vj = cij, rezultând un sistem cu m + n necunoscute (m de ui și n de vj) și m + n – 1 ecuații (egal cu rangul matricii A);
III. Se găsește o soluție particulară a acestui sistem, egalând una din necunoscute cu 0 (pe cea care apare de cele mai multe ori);
IV. Se calculează toți ij = ui + vj – cij pentru toate rutele care nu fac parte din soluție (ceilalți sunt 0, ținând cont de felul cum au fost găsiți ui, i = 1,…,m și vj, j = 1,…,n)
V. Se analizează ij găsiți.
– dacă toți sunt mai mici sau egali cu 0 soluția găsită este optimă STOP
– dacă există ij strict pozitivi atunci soluția actuală nu este optimă și ruta corespunzătoare lui ij maxim va fi cea care intră în bază (dacă maximul este multiplu se ia una la întâmplare)
V. Se construiește un circuit, pornind din această rută, trecând doar prin rutele soluției, mergând doar pe verticală sau orizontală și fiecare trecere de la o rută la alta făcându-se doar perpendicular pe trecerea anterioară. S-a demonstrat că există un singur circuit cu aceste proprietăți și se poate demonstra ușor că trece printr-un număr par de rute.
VI. Începând cu + din ruta care va intra în bază se notează alternativ cu "+" și "–" rutele circuitului;
VII. Se notează cu minimul dintre cantitățile transportate pe rutele notate cu "–" și ruta pentru care s-a obținut acest minim este cea care va ieși din bază (cazul minimului multiplu va fi analizat după expunerea algoritmului);
VIII. Se scade din cantitățile transportate pe rutele notate cu "–" și se adaugă la cele notate cu "+", rutele care nu sunt pe circuit păstrându-și valoarea;
IX. Se reia algoritmul de la pasul 2
Așa cum s-a văzut mai sus, se poate ca la pasul 8 minimul să fie multiplu. Atunci, pe toate rutele pe care se transporta nu se va mai transporta nimic, adică vor dispărea din soluție. Cum în soluție a intrat doar o singură rută rezultă că noua soluție este degenerată. Cum existența acestui tip de soluții poate duce la ciclarea algoritmului, au fost imaginate mai multe metode de evitare, toate bazându-se pe modificarea datelor inițiale, în așa fel încât, pe parcursul algoritmului, să nu mai avem nici o soluție degenerată. Această modificare (perturbare) poate fi făcută chiar de la începutul rezolvării, încât problema să nu mai aibă nici o soluție degenerată, fie doar atunci când apare o soluție degenerată, eliminând perturbația imediat ce nu mai e necesară. Pentru a vedea cum trebuie să arate o astfel de modificare, dăm următoarea teoremă care caracterizează existența soluțiilor degenerate:
Teoremă IIII.1. O problemă de transport are soluții degenerate dacă și numai dacă există o submulțime strictă și nevidă a furnizorilor și o submulțime strictă și nevidă a consumatorilor astfel încât suma disponibilurilor furnizorilor din prima submulțime este egală cu suma cererilor consumatorilor din a doua.
Lemă IIII.1.. Soluția este degenerată de k ori dacă și numai dacă mulțimea furnizorilor și a consumatorilor se pot partiționa în k submulțimi 1, 2, …, k și 1, 2 ,…, k astfel încât consumatorii din fiecare clasă i se aprovizionează numai de la furnizorii din clasa i.
În concluzie, dacă vrem să dispară toate soluțiile degenerate, trebuie modificate disponibilurile și cererile în așa fel încât să nu mai poată exista varianta din teoremă. Una din metodele posibile este să adăugăm la fiecare furnizor Fi cantitatea i și să introducem un consumator fictiv cu cererea egală cu + 2 + … + m, unde este o valoare foarte mică (oricât de mică este necesar). O altă variantă este să adăugăm la fiecare furnizor Fi cantitatea i și să introducem un consumator fictiv cu cererea egală cu + 2 + … + m, unde este de asemenea o valoare foarte mică (oricât de mică este necesar). Se pot găsi, evident, și altele variante.
Această metodă este foarte bună în cazul rulării problemei pe calculator, dar, în cazul rezolvării cu creionul pe hârtie, este, evident, greoaie.
În acest caz vom folosi varianta în care introducem perturbația doar când este nevoie (adică când apare o soluție degenerată). Această situație poate apărea fie chiar la soluția inițială, în urma aplicării uneia din metodele de găsire ale unei soluții inițiale, fie la pasul 8 din a doua etapă dacă se obține pentru mai multe rute. Rămâne de văzut doar cum trebuie făcută această perturbare.
Conform teoremei de mai sus rezultă că mulțimea furnizorilor și a consumatorilor se pot partiționa în k submulțimi 1, 2, …, k și 1, 2 ,…, k astfel încât consumatorii unei clase i se aprovizionează numai de la furnizorii din clasa i și reciproc. Pentru fiecare indice i k–1 vom alege o rută care corespunde unui furnizor din i și unui consumator din i+1 și vom adăuga la furnizorul și consumatorul corespunzători acesteia cantitatea i (sau valoarea i într-o ordine dată a valorilor). Dacă, la un moment dat, prin anularea unui parametru introdus, soluția rămâne nedegenerată, acesta va fi anulat.
Variante ale problemei de transport
Există o gamă foarte largă de fenomene economice care pot fi reprezentate prin modele de programare liniară de tip transport sau foarte asemănătoare cu acestea. Prezentăm în continuare câteva dintre acestea
1. Cu rute blocate
În anumite cazuri pot exista situații în care anumite rute între furnizori și consumatori nu pot fi folosite, cel puțin temporar. Rezolvarea acestor probleme se face cu un model de transport obișnuit, în care rutelor interzise li se asociază costuri unitare de transport foarte mari în raport cu costurile rutelor utilizabile. Prin aceste costuri de penalizare foarte mari, algoritmul de optimizare este "constrâns" să ocolească rutele interzise.
2. Cu puncte intermediare
Există situații în care aprovizionarea consumatorilor nu se face direct de la furnizori ci prin intermediul unor centre intermediare. De exemplu, cea mai mare parte a bunurilor produse pentru consumul populației sunt mai întâi colectate în mari depozite și apoi distribuite centrelor de desfacere. Problema de optimizare costă în minimizarea cheltuielilor de transport de la furnizori la centrele intermediare la care se adaugă costul transportului de la aceste centre la consumatorii finali.
În anumite condiții această problemă este echivalentă cu două probleme de transport obișnuite.
3. Problema încărcării utilajelor
Făcând parte din același cadru al programării operative a producției, problema încărcării utilajelor (punctelor de lucru) ocupă a poziție centrală. Această problemă poate fi formulată astfel:
"Într-o secție a unei unități economice se produc reperele (bunurile) P1, P2, …, Pn care pot fi realizate pe oricare din utilajele (grupele de utilaje) Ul,U2,…,Um. Se cunosc următoarele date:
cantitățile N1, N2,…,Nn din reperele date, care trebuie produse într-o anumită perioadă;
fondurile de timp disponibil F1, F2,…,Fm ale utilajelor, în perioada respectivă;
cantitatea Pij din reperul Pj ce poate fi produsă pe utilajul Ui într-o anumită perioadă de timp;
costul cij al realizării unei unități specifice din reperul Pj pe utilajul Ui.
Se dorește găsirea acelui mod de repartizare a sarcinilor de producție pe utilaje astfel încât costul realizării cantităților planificate să fie minim."
Modelul matematic asociat acestei probleme este:
unde xij reprezintă cantitatea de repere Pj ce urmează a fi realizată pe utilajul Ui. Modelul este asemănător modelului problemei de transport, pentru rezolvare putându-se folosi algoritmul de la problema clasică de transport, cu unele modificări dictate de prezența "ponderilor" Pij.
4. Problema afectării
Există probleme de programare operativă care pot fi reprezentate prin modele liniare de tipul problemei de transport. Un exemplu des întâlnit este următoarea problemă concretă de programare operativă a producției:
"Un număr de lucrări Ll, L2,…, Ln trebuiesc executate cât mai repede. Acestea sunt efectuate de persoanele (muncitorii) Ml, M2,…, Mn, fiecare putând executa oricare din lucrările date. Cunoscând timpul tij de execuție al lucrării Li de către muncitorul Mj, scopul optimizării este găsirea acelui mod de repartizare a lucrărilor pe muncitori astfel încât timpul total de execuție al lucrărilor să fie minim".
5. Problema de transport a lui Koopmans
Această problemă este, istoricește vorbind, anterioară problemei clasice de transport și de ea s-a ocupat pentru prima oară T. C. Koopmans.
Matematic, această problemă se poate formula astfel:
"Fie n porturi din care se expediază și în care sosesc încărcături. Notăm cu wi un volum dat de mărfuri expediate (exprimate, de pildă, în tone), iar cu pi – un volum dat de mărfuri care se aduc în decursul unei anumite perioade în portul i (i = 1, 2,…, n). Se cunosc distanțele sij dintre porturi (exprimate, de pildă, în kilometri), acestea fiind date în matricea:
S =
Dacă xij reprezintă volumul efectiv de mărfuri care urmează să fie transportate din portul i în portul j, iar yij – capacitatea de încărcare a vaselor care circulă din portul i in portul j date, de asemenea, sub forma unor matrici:
X = Y =
atunci necunoscutele problemei sunt mărimile yij (i,j = 1, 2,…, n), adică capacitățile de încărcare a navelor ce vor fi trimise din portul i în portul j.
Funcția obiectiv f va stabili mărimea "transporturilor goale", adică mărimea tonajului neutilizat al navelor. Mărimea tonajului neutilizat pe traseul dintre portul i și portul j va fi (yij – xij), deci mărimea capacității de transport neutilizate pe toate traseele (în tone kilometri) va reprezenta:
f =
Problema examinată constă în a găsi minimul acestei funcții
Condițiile auxiliare pe care trebuie să le satisfacă necunoscutele yij pot fi notate sub forma următoarelor ecuații:
Primele n ecuații arată că tonajul total al navelor trimise dintr-un port oarecare i în toate celelalte porturi trebuie să fie egal cu wi iar ultimele n că tonajul total al navelor sosite într-un port oarecare j din toate celelalte porturi trebuie să fie egală cu pj.
Trebuie menționat că – întocmai ca în problema de transport – dintre cele n + n ecuații de echilibru, numai (2n – 1) ecuații sunt independente. Aceasta se explică prin faptul că , adică tonajul total al navelor care pleacă din toate porturile este egal cu tonajul total al navelor care sosesc în toate porturile. Întrucât problema are (n2 – n) necunoscute yjj (i,j = l, 2,…,n), dar există 2n – 1 ecuații de echilibru independente, numărul gradelor de libertate (numărul variabilelor secundare) va fi (n2 – n) – (2n – 1) = n2 – 3n + 1.
În afară de relațiile de echilibru există și condițiile de nenegativitate:
yij xij 0
condiția yij xij înseamnă că tonajul vaselor care pleacă din portul i spre portul j trebuie să fie mai mare sau egal cu cantitatea de mărfuri care urmează a fi transportată pe acest traseu."
Din această formulare se vede că modelul lui Koopmans este o problemă de programare liniară, deoarece atât funcția obiectiv, cât și ecuațiile de echilibru sunt relații liniare în raport cu necunoscutele yij. Problema poate fi ușor transformată într-un model de programare neliniară dacă, de pildă, în locul distanței sij între porturi, introducem cheltuielile de transport cu mențiunea că aceste cheltuieli nu cresc direct proporțional, ci mai lent decât distanțele. Aceasta problemă poate fi ușor înlocuită printr-o problemă duală, luând ca funcție obiectiv rentabilitatea totală a tuturor transporturilor pe plan mondial. În acest caz, problema de minimizare a tonajului neutilizat al navelor ar fi înlocuită printr-o problemă de maximizare a rentabilității totale a transporturilor.
Aplicatie
Se dă un graf. Să se determine arborele partial de cost minim.
Algoritmul Kruskal.
#include<fstream.h>
#include<conio.h>
typedef struct {
int x, y, cst;
} Muchie;
Muchie V[200];
int T[200], S[200];
int m, n, i, Cost, sel;
void CitesteFisier(){
ifstream f("Kruskall.in");
f>>m>>n;
for(i=1; i<=m; i++)
f>>V[i].x>>V[i].y>>V[i].cst;
f.close();
}
void SortareMuchii(){
// Se sorteaza crescator vectorul V in functie de cost.
int ok=0;
Muchie tmp;
while (!ok){
ok=1;
for(i=1; i<m; i++)
if(V[i].cst>V[i+1].cst){
tmp=V[i]; V[i]=V[i+1]; V[i+1]=tmp; ok=0;
}
}
cout<<endl<<endl<<"Muchiile sunt:"<<endl;
for(i=1; i<=m; i++)
cout<<V[i].x<<" – "<<V[i].y<<" "<<V[i].cst<<endl;
cout<<endl;
}
void Kruskal(int &sel, int S[]){
int Xtmp, j;
for(i=1; i<=n; i++) T[i]=i;
Cost=0; sel=0; i=1;
while((sel<n-1)&&(i<=n)){
if(T[V[i].x]!=T[V[i].y]){ // comp. conexe diferite
sel++; S[i]=1;
Cost+=V[i].cst;
Xtmp=T[V[i].x];
for(j=1; j<=n; j++)
if(T[j]==Xtmp) T[j]=T[V[i].y];
}
i++;
}
}
void main(void){
CitesteFisier();
SortareMuchii();
Kruskal(sel,S);
cout<<endl;
// for(i=1; i<=n; i++)
// cout<<T[i]<<" ";
cout<<endl;
if(sel<n-1)
cout<<"Graf neconex.";
else{
cout<<"Graf conex.";
cout<<endl<<"Arborele partial de cost minim este:";
for(i=1; i<=m; i++)
if(S[i]==1)
cout<<endl<<V[i].x<<" – "<<V[i].y<<" Cost= "<<V[i].cst;
}
getch();
}
Bibliografie
C. Bereanu, Algoritmi și complexitate, Reprografia Universității din Craiova, 1998
C. Bereanu, Algoritmi. Grafuri. Complexitate., Editura SITECH, Craiova, 2005
C. Bereanu, Algoritmica grafurilor, editura Sitech, Craiova, 2006
C. Bereanu, Complexitatea calculului, Editura SITECH, Craiova, 2000
C. Ivașc, M. Prună, Bazele informaticii, Editura Petrion, București, 2000
E. Mateescu, I. Maxim I., Arbori, Editura Țara Fagilor, 1996
H. S. Wilf, Algorithmes et complexite, Prentice-Hall, london, 1989
I. Tomescu, Bazele informaticii,Editura Didactică și Pedagogică, București, 1997
N. Rădescu, Cercetări operaționale. Elemente de teoria grafurilor, Reprografia Universității din Craiova, 1981
O. Pătrășcoiu, G. Marian, N. Mitroi, Elemente de grafuri și combinatorică. Metode, algoritmi și programare, editura ALL, București, 1994
T. Cormen, C. Leiserson, R. Rivest, Introduction to Algorithms, The MIT Press, 1990
T. Cormen, G. Leiserson, R. Rive, Introducere in algoritmi, Comp. Libris Agora, Cluj, 2000.
T. Sorin, Tehnici de programare, editura L&S, București, 1996
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Probleme DE Repartitie In Grafuri Bipartite (ID: 149235)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.