infoarena

Fiind data o retea de transport, se pune problema gasirii fluxului maxim de la S la T, iar dintre toate variantele, aceea care foloseste un numar cat mai mic de muchii pentru transport. Ma gandeam de ceva timp daca algoritmul Edmonds-Karp, alegand de fiecare data drumul de ameliorare cu numarul minim de muchii, garanteaza in final o solutie corecta a problemei :?

Aduni la fiecare muchie valoarea |E| + 1, unde |E| e cardinalul multimii muchiilor. Taietura minima va contine un numar minim de muchii.

Taietura minima contine un numar minim de muchii si daca toate muchiile au capacitate 1 :) Problema e cum circula fluxul de la S pana la muchiile din taietura, si de la muchiile din taietura la T. Dintre toate taieturile minime, ar trebui aleasa aceea care optimizeaza "traficul" in sensul numarului de muchii folosite in afara ei.

Eu ma refeream la ideea prezentata aici  http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2 in al patrulea desen.

Defapt, desenul arata o contradictie. Textul de deasupra si de sub el trebuie citit.

 Din articolul de mai sus eu am inteles ca iei fiecare si inmultesti cu |E| si apoi aduni 1.

In plus el se refera ca vrea sa trimita fluxul in asa fel incat numarul de muchii x y, cu f[ x] [y]>0 sa fie minim. (unde f[ x ][y]  este fluxul trimis pe muchia x y).

Capacitatile sunt arbitrare sau doar 0/1?

Desenul mi se pare in concordanta cu ce scrie in articol: arata ca daca inmultesti toate capacitatile cu o valoare T si aduni 1, taietura minima din graful original nu este neaparat taietura minima in graful nou obtinut.

Eu am inteles articolul la fel ca Tiberiu, ar trebui sa inmultesti fiecare muchie cu |E| (de fapt e destul sa inmultesti cu numarul maxim de muchii ce pot aparea intr-o taietura minima a grafului original) si apoi sa aduni 1, ca sa te asiguri de minimalitatea numarului de muchii din taietura.

@Alina: Eu ma gandeam cu capacitati arbitrare, dar as fi curios si de o analiza pe cazul particular 0/1

@Lucian: Cred ca in cazul in care capacitatile sunt 0/1, numarul de muchii folosite e intotdeauna acelasi numarul de muchii folosit de algoritmul propus de tine (i.e., la fiecare pas gasesti un augmenting path folosind BFS) este egal cu numarul minim de muchii in orice flux maxim. Am crezut pentru un moment ca muchiile au capacitati 0 sau 1 pentru ca ai spus ca taietura minima are un numar minim de muchii. Mi-am dat seama apoi ce vroiai sa spui :)

@Marius: nu merge intotdeaua sa adaugi |E| + 1 (cel putin, nu-mi dau seama cum o sa construiesti un flux maxim in vechea retzea folosind un flux maxim in noua retzea)

Nu orice flux maxim intr-o retea de capacitati 0/1 foloseste acelasi numar de muchii (din nou, conteaza numarul de muchii saturate de pe taietura, in rest poti transporta oricum fluxul). Un exemplu ar fi reteaua V={1,2,3,4}, E={(1,2),(2,3),(3,4),(1,3)}, S=1, T=4. Fluxul maxim este 1 si poate fi trimis pe drumul P1={(1,2),(2,3),(3,4)} sau P2={(1,3),(3,4)}.

Ramane de vazut (de fapt asta era problema mea initiala) daca, in cazul in care fiecare cautare a drumului de ameliorare foloseste un BFS (deci drumul cu numar minim de muchii), atunci se garanteaza minimul global de muchii la incheierea algoritmului...

Scuze, ar fi trebuit sa postez mai explicit. Ma refeream la cazul in care la fiecare pas gasesti un augmenting path folosind BFS. Nu stiu daca merge in general, dar cred ca poti sa demonstrezi ca merge in cazul in care capacitatile sunt 0 sau 1.

Am gresit, imi cer scuze. Articolul a fost citit de mine acum ceva mai mult timp. Oricum, e o sursa buna, desi nu e chiar despre ce vroia Lucian sa afle.

Daca capacitatile sunt 0/1 atunci merge cu BFS din cauza ca ar fi un flux maxim de cost minim intrun graf care are pe toate muchiile cost 1.

O idee ptr problema generala ar fi sa pui initial toate muchiile cu cost 1, si sa gasesti drumul de ameliorare cu belman-ford, iar atunci cand ai bagat flux pe o muchie sa ii faci costul 0, desi nu sunt sigur ca merge aceasta abordare.

Tu prin cost intelegi capacitate?

Nu merge sa lasam capacitatile asa cum erau, dar costul fiecarei muchii sa fie 1, iar apoi sa scoatem flux maxim de cost minim ? (sper sa nu fi inteles gresit in ce sens sa se foloseasca nr minim de muchii  :?)

Nu. Prin cost inteleg cost. Capacitatile vor fi cele din input si mai asociez si cost muchiilor, si mai asociez si o functie de cost grafului astfel:

cost(x,y) = 1 , daca flux(x,y) == 0
                   0 , daca flux(x,y) != 0

Nu, in flux maxim de cost minim, costul asociat unei muchii e pe unitate de flux, nu pe muchie. Daca trece flux 4 printr-o muchie cu cost 1 atunci costul adunat o sa fie 4.

@devilkind: ma indoiesc ca merge ce ai zis ca nu prea iei in calcul ce faci daca vine flux din directia opusa :)

Da, ai dreptate, m-am grabit. Gandeam ca nu pui cost pe unitatea de flux, ci pe muchia parcursa, si in acest moment exact asta vrea problema.

Da ai dreptate nu merge.

Pe cazul 0/1 merge flux maxim de cost minim, cu toate costurile 1, dar drumurile de ameliorare trebuie sa le cauti cu Bellman-Ford, nu cu BFS (faci cost -1 pe muchiile pe care trimiti flux inapoi).