Cuplaj maxim in graf bipartit

Cuplaj maxim în graf bipartit

O scurtă lecţie de teorie găsiţi pe 'wikipedia':http://en.wikipedia.org/wiki/Maximum_matching şi în cartea '_Introducere in algoritmi_':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm, Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Alte articole excelente care tratează problema fluxului maxim pe larg se găsesc la adresele următoare: 'secţiunea $1$':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow, 'secţiunea $2$':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2.
O soluţie exponenţială cu metoda $backtracking$ poate fi găsită uşor.
O soluţie <tex> O(VE) </tex> cu 'algoritmul lui Edmonds Karp':http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm se găseşte 'aici':job_detail/225136?action=view-source.

O soluţie ce foloseşte $lanţuri altenante$ în complexitate <tex> O(VE) </tex> se găseşte 'aici':job_detail/225128?action=view-source. Menţionez că acest algoritm se comportă foarte bine în practică.

O soluţie ce foloseşte $lanţuri alternante$ în complexitate <tex> O(VE) </tex> se găseşte 'aici':job_detail/225128?action=view-source. Menţionez că acest algoritm se comportă foarte bine în practică.

Soluţia de $100p$ se obţine cu ajutorul 'algoritmului lui Hopcroft Karp':http://en.wikipedia.org/wiki/Hopcroft-Karp_algorithm de complexitate <tex> O(\sqrt{V}E) </tex> şi este o îmbunătăţire a soluţiei precedente: la fiecare pas al iteraţiei se găseşte un număr maximal de lanţuri alternante care acceptă o augmentare de o unitate de flux. Această soluţie se găseşte 'aici':job_detail/225121?action=view-source.
În grafuri bipartite, $cuplajul maxim$ este egal cu acoperirea minimă cu noduri (minimum 'vertex cover':http://en.wikipedia.org/wiki/Vertex_cover). Din acest rezultat deducem că acoperirea minimă cu noduri şi multimea maximă de puncte independente ('maximum independent set':http://en.wikipedia.org/wiki/Maximum_independent_set) se pot rezolva în 'timp polinomial':http://en.wikipedia.org/wiki/Polynomial_time în grafuri bipartite.

* 'Felinare':problema/felinare
* 'Gandaci Java':problema/java
* 'Paznici':problema/paznici

* 'Taramul Nicaieri':problema/harta

* 'Senat':problema/senat

* 'Knights':http://iskren.info/info-arh/BalticOI/2001/blue-a4.ps, _BalticOI 2001_
* 'Beloved Sons':http://acm.sgu.ru/problem.php?contest=0&problem=210
* 'Unstable Systems':http://acm.sgu.ru/problem.php?contest=0&problem=218