Pagini recente » Diferente pentru utilizator/y2k intre reviziile 14 si 11 | Diferente pentru heapuri intre reviziile 129 si 10 | Diferente pentru voronoi intre reviziile 60 si 13 | Diferente pentru utilizator/pavelrazvan intre reviziile 104 si 105 | Diferente pentru problema/cuplaj1 intre reviziile 14 si 13
Nu exista diferente intre titluri.
Diferente intre continut:
Se numeste *graf bipartit* un graf $G$ ale carui noduri pot fi partitionate in doua multimi disjuncte $A$ si $B$ astfel incat oricare muchie uneste un nod din $A$ si un nod din $B$. Cu alte cuvinte, nu exista doua nuduri $i$ si $j$ din aceeasi multime astfel incat sa existe muchie intre ele.
Fie $G$ un graf bipartit. Numim *cuplaj* o submultime de muchii <tex>M \subset E</tex> cu proprietatea ca ∀ $i$ ∈ $V$ exista cel mult o muchie in $M$ incidenta in $i$. Spunem ca $i$ este cuplat de cuplajul $M$ daca exista o muchie in $M$ incidenta in $i$. In caz contrar Numim *cuplaj maxim* o multime $M$ de cardinal maxim, adica nu exista nicio alta multime $M'$ cu $|M'| > |M|$ (unde cu $|M|$ am notat cardinalul multimii $M$).
Fie $G$ un graf bipartit. Numim *cuplaj* o submultime de noduri <tex>M \subset A</tex> cu proprietatea ca ∀ $i$ ∈ $M$ exista un unic $j$ ∈ $B$ astfel incat intre $i$ si $j$ sa fie muchie. Numim *cuplaj maxim* o multime $M$ de cardinal maxim, adica nu exista nicio alta multime $M'$ cu $|M'| > |M|$ (unde cu $|M|$ am notat cardinalul multimii $M$).
h2. Cerinta
Mai multe detalii despre *cuplajul in graf bipartit*, precum si probleme asemanatoare se pot gasi in acest "aritcol":http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2.
Bogdan: cosmine in primul rand nu terminasem problema. normal ca pun solutia smechera, doar am dat N < 2000 :). La flux1 si flux2 am vorbit si cu alti membri infoarena care mi-au sugerat sa fac in doua probleme. am inteles ca azi (03.03.2008) discutati arhiva educationala. daca se hotaraste ceva o sa schimb precum se decide.
Cosmin: bogdane nu imi place ca faci 3 probleme care ar fi putut fi bagate in aceiasi: flux. Daca tot ai facut problema de cuplaj zi solutia misto cu recursivitate care se scrie foarte scurt si algoritmul de cuplaj in O(sqrt(n) * m).
Eu as face din primele 2 probleme de flux una singura. Cu ford fulkerson sa se ia 50 de puncte si cu dinic 100.
Nu e bine sa bagi material mult daca nu e nou, asa numa spamezi arhiva educationala ... si ajunge la fel de greu de folosit ca si cea mare.
== include(page="template/taskfooter" task_id="cuplaj1") ==
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
