Nu aveti permisiuni pentru a descarca fisierul grader_test5.in
Diferente pentru flux-si-cuplaj intre reviziile #12 si #11
Nu exista diferente intre titluri.
Diferente intre continut:
h2. 1. Retele de transport
O **retea de transport**$G=(V, E)$este un graf orientat in care fiecarui arc$(u, v) ∈ E$ii este asociata o **capacitate** nenegativa$c(u,v) >=0$.
O **retea de transport** G=(V, E) este un graf orientat in care fiecarui arc (u, v) ∈ E ii este asociata o **capacitate** nenegativa c(u,v) >=0.
Vom distinge 2 varfuri importante in retea: varful **sursa S** si varful **destinatie D**. Un flux in reteaua de mai sus este o functie $f: V x V -> R$ care satisface urmatoarele conditii:
# **Restrictie de capacitate:** pentru orice$u, v ∈ V$avem$f(u, v)<=c(u, v)$# **Antisimetrie:** pentru orice$u, v ∈ V$avem$f(u, v)=-f(v, u)$# **Conservarea fluxului:** pentru orice$u ∈ V - {S, D}$avem$∑ v ∈ V$din$f(u, v) = 0$
# **Restrictie de capacitate:** pentru orice u, v ∈ V avem f(u, v)<=c(u, v)
# **Antisimetrie:** pentru orice u, v ∈ V avem f(u, v)=-f(v, u)
# **Conservarea fluxului:** pentru orice u ∈ V - {S, D} avem ∑ v ∈ V din f(u, v) = 0
Prima restrictie impune pur si simplu ca fluxul de la un varf la altul sa nu depaseasca valoarea capacitatii. Antisimetria impune ca fluxul de la un varf u la un varf v sa fie egal cu opusul fluxului de la varful v la u. Astfel, fluxul de la un varf la el insusi este 0.
