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 &#8712; V avem f(u, v)<=c(u, v)
# **Antisimetrie:** pentru orice u, v &#8712; V avem f(u, v)=-f(v, u)
# **Conservarea fluxului:** pentru orice u &#8712; V - {S, D} avem &#8721; v &#8712; V din f(u, v) = 0

# **Restrictie de capacitate:** pentru orice $u, v &#8712; V$ avem $f(u, v)<=c(u, v)$
# **Antisimetrie:** pentru orice $u, v &#8712; V$ avem $f(u, v)=-f(v, u)$
# **Conservarea fluxului:** pentru orice $u &#8712; V - {S, D}$ avem $&#8721; v &#8712; 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.