020 Cuplaj maxim in graf bipartit

[•filipb]

Aici puteti discuta despre problema Cuplaj maxim in graf bipartit.

[•domino]

Lipseste poza de la explicatia exemplului.

[•Marius]

Au fost câteva probleme cauzate (de mine). Am să pun poza imediat.

[•gabor_oliviu1991]

interesant e ca daca fac cu Edmonds Karp pe exemplul:

Cod:

3 3 6
1 4
1 5
2 4
3 4
3 5
3 6

imi da raspuns gresit. daca folosesc solutia cu "lanțuri altenante" care cred ca sunt alternante, imi da raspunsul corect. totusi cred ca ambele solutii ar trebui sa returneze un raspuns corect daca totusi sunt "solutii" cu implementare diferita.

raspuns corect furnizat de solutia cu lanturi alternante ( http://infoarena.ro/job_detail/225128?action=view-source ):

Cod:

3
1 5
2 4
3 6

iar cea gresita cu Edmonds Karp ( http://infoarena.ro/job_detail/225136?action=view-source ) :

Cod:

3
1 4
2 4
3 4

[•Marius]

Soluția cu Edmonds Karp nu cred că e greșită. Tu ai introdus datele greșit. Pe prima linie ai 3 3 6, adică ai o mulțime L cu 3 elemente {1, 2, 3} și o mulțime R tot cu 3 elemente {1, 2, 3} și între acestea se adaugă 6 muchii. Însă, pe coloana a doua din liniile următoare ai valorile 4, 5, 6 care nu sunt corecte. Ar trebui 1, 2, 3.

[•gabor_oliviu1991]

Ok, pana la urma am inteles ce era gresit. Dar totusi, cred ca ar trebui specificat alaturi de solutie ca datele de intrare au alt format fata de cel cu liste alternante.

[•Marius]

Ok, pana la urma am inteles ce era gresit. Dar totusi, cred ca ar trebui specificat alaturi de solutie ca datele de intrare au alt format fata de cel cu liste alternante.

Datele de intrare au acelaşi format pentru toate soluţiile.

[•adelinas]

Imi poate spune cineva va rog frumos care este ideea de rezolvare cu lanturi alternante?

[•sima_cotizo]

Daca te referi la ce cred eu:
- sa zicem ca ai in stanga un set de noduri i, in dreapta un set de noduri j. tii in L[ i ] nodul din dreapta cu care nodul i (din stanga) e cuplat, iar in R[ j ]  nodul din stanga cu care e cuplat nodul j(din dreapta). bineinteles, daca L[ i ] sau R[ j ] sunt 0, inseamna ca sunt necuplati (sau egali cu alta valoare "de referinta" gen -1, tu stii)
- pentru un nod din dreapta cuplat cu unul din stanga, stii ca el va ramane cuplat mereu (practic, nu vrei sa scazi cuplajul).
- iei un nod din stanga. daca gasesti sa-l cuplezi cu unul din dreapta liber, o faci. daca nu gasesti vreunu liber, ii iei pe cei ocupati si incerci sa-i recuplezi pe astia cu nodu curent, deci sa incerci pe R[j] (nodul corespunzator nodului din dreapta cu care vrei sa cuplezi) sa il cuplezi cu altcineva
Asta e ideea in mare. Imi dau seama ca nu  este foarte clar explicata, dar cred ca te-ar ajuta sa te uiti si pe o sursa in acelasi timp ( de exemplu: http://infoarena.ro/job_detail/234180?action=view-source ).

Daca are altcineva o explicatie mai clara, sau daca eu am explicat alta metoda decat cea ceruta, va rog sa ma corectati

[•wefgef]

Ce anume vrei sa iti explicam, algoritmul in sine sau modul de implementare?

[•emi.0105]

salut...ma poate ajuta cineva?..nu gasesc un turorial sau un articol care sa ma ajute sa inteleg ce sunt grafurile si cum le folosesc..nu am mai lucrat deloc cu grafuri..daca ma puteti ajuta cu un tutorial ceva ar fi perfect

[•CezarMocan]

Wikipedia. 1 si 2. Sper sa te ajute!

[•alexandru92]

Nu gasesc nici unde  explicata metoda lanturilor alternante, se poate detalia putin sau un link catre o explicatie ?

[•sima_cotizo]

Bineinteles, imediat. Uite aici:

http://infoarena.ro/forum/index.php?topic=3450.msg36209#msg36209

Pun pariu ca nu ai citit topicul...

[•livium]

Poate cineva sa comenteze codul (http://infoarena.ro/job_detail/225128?action=view-source) pentru ca nu pot sa-l inteleg. Eu stiu cum sa fac problema asta dar intr-un mod mult mai dificil de implementat, de aceea va rog daca poate cineva sa ma ajute sa inteleg codul lui Marius Stroe!

[•dornescuvlad]

http://en.wikipedia.org/wiki/Hopcroft-Karp_algorithm

[•livium]

Algoritmul lui Marius Stroe nu urmeaza pseudocodul Hopcroft-Karp de pe wikipedia. E cu totul altceva!

[•S7012MY]

Uite sursa mea:
http://infoarena.ro/job_detail/465422?action=view-source
nu sunt multe comentarii dar sper sa te ajute Daca nu intelegi ceva intreaba si incerc sa te ajut.

[•livium]

Merci!
Eu m-am gandit la un algoritm propriu inspirat de chestia asta cu vectorii L si R.
Incerc sa cuplez un nod din stanga cu unul din dreapta.
Daca nodul din dreapta nu e cuplat atunci fac cuplajul.
Altfel caut un alt nod din dreapta cu care nodul din stanga se poate cupla.
Daca toate nodurile din dreapta nodului din stanga sunt cuplate atunci decuplez un nod din dreapta, il cuplez cu nodul din stanga, iar nodul din stanga care a fost decuplat de nodul din dreapta caut sa-l cuplez cu un altul din dreapta necuplat.

Faza e ca algoritmul la care m-am gandit eu merge foarte bine pe foaie, intru-cat l-am testat multe grafuri bipartite?
Cumva algoritmul tau face acelasi lucru?

Apropo: algoritmul lui Stroe nu merge pentru un graf anume. E gresit.

[•DraStiK]

Apropo: algoritmul lui Stroe nu merge pentru un graf anume. E gresit.

Nu e algoritmul lui Stroe. E un algoritm greedy ce determina cuplajul maxim, si e demonstrat a fi corect.

Practic functia pair-up returneaza adevarat daca poate cupla nodul i din prima multime.
Cum face asta? Parcurge in primul rand toate nodurile vecine ale nodului i din cea dea doua multime,si daca gaseste unul liber, il cupleaza cu acesta.
Daca nu gaseste nici un nod liber (necuplat), atunci parcurge din nou vecinii nodului i, si incearca sa vada daca poate cupla perechea acestui nod cu altul, pentru a-l putea cupla pe i cu acesta.

Sper sa intelegi. E seara, si e probabil sa am greseli gramaticale, si pentru asta, imi cer scuze.

[•livium]

Asa m-am gandit si eu. Ciudat e ca merge si nu pot intelege de ce.
Nu pot sa inteleg care ar putea fi demonstratia matematica pentru algoritmul asta, asa cum exista una pentru algoritmul care rezolva acceasi problema, insa utilizand un graf auxiliar (http://www.youtube.com/watch?v=NlQqmEXuiC8).

[•Prostu]

Algoritmul lui Marius Stroe nu urmeaza pseudocodul Hopcroft-Karp de pe wikipedia. E cu totul altceva!

E acelasi lucru, doar ca este implementat la obiect, fara bla bla. Se demonstreaza folosind drumuri de augmentare, pana la urma este o optimizare la Edmond-Karp, care este o implementare a Ford–Fulkerson. Daca nu stii algoritmul de flux maxim intr-o retea de transport, atunci iti recomand sa incepi cu acesta din urma.

[•gorgovan]

Care este cel mai eficient algoritm pentru a afla cuplajul maxim intr-un graf multi partit( tripartit, 4 partit, 5 partit, 6 partit) ?
Dar cred ca pentru ce am eu nevoie va fi 7->9 partit.

Edmonds-Karp?

[•edward_alex]

Am implementat aceasta problema urmarind exact algoritmul de pe Wikipedia cu privire la algoritmul Hopcroft–Karp. Am retinut muchiile intr-o lista de adiacenta, vectorul pair e global la fel si dist. Am urmarit exact acel algoritm. Nu inteleg de ce imi da raspunsul gresit. Nu este de ajuns implementarea acelui algoritm sau mai trebuie modificat ceva?

Multumesc anticipat,
Alex

[•VisuianMihai]

Buna... imi puteti spune si mie de unde pot invata despre grafuri(de pe internet de preferat) sunt pe clasa a 9-a.