== include(page="template/taskheader" task_id="flux1") ==

Fie un graf orientat cu $N$ noduri si $M$ muchii. $V$ este multimea nodurilor din graf, iar $E$ multimea muchiilor. Asociem fiecarei muchii $(u,v)$ o capacitate nenegativa $cap(u,v)$. Consideram doua varfuri speciale: nodul $1$ care va fi denumit $sursa$ si nodul $N$, denumit $destinatie$. Orice nod $i$ ({$2 ≤ i ≤ N-1$}) se gaseste pe cel putin un drum de la $1$ la $N$. Definim *fluxul* in graf ca fiind o functie _f: E -> Z_, unde $E$ este multima muchiilor grafului $G$. Functia _f_ satisface urmatoarele conditii:

Fie un graf orientat cu $N$ noduri si $M$ muchii. $V$ este multimea nodurilor din graf, iar $E$ multimea muchiilor. Asociem fiecarei muchii $(u,v)$ o capacitate nenegativa $cap(u,v)$. Consideram doua varfuri speciale: nodul $1$ care va fi denumit $sursa$ si nodul $N$, denumit $destinatie$. Orice nod $i$ ({$2 ≤ i ≤ N-1$}) se gaseste pe cel putin un drum de la $1$ la $N$. Definim *fluxul* in graf ca fiind o functie _f: E -> Z_, unde $E$ este multimea muchiilor grafului $G$. Functia _f_ satisface urmatoarele conditii:

# este restrictionata de capacitate, adica ∀ ( $i$, $j$) ∈ E avem $f(i,j) ≤ cap(i,j)$
# fluxul se conserva, adica &forall; $i$ &isin; $V\{1,N}$ valoarea fluxului care intra in nodul respectiv este egala cu valoarea fluxlui care iese din nodul respectiv (&forall; $i$ &isin; $V$ avem <tex>\sum_{(j,i) \in E}^{} f(j,i) = \sum_{(i,k) \in E}^{} f(i,k)</tex>