Sia $G= (V,A)$ un grafo orientato su cui sia definito un vettore $\underline{u} =[u_{ij}]$ dalle capacità associate agli archi del grafo
Inoltre, siano $s$ e $t$ due nodi distinti, detto rispettivamente sorgente (o origine) e pozzo (o destinazione)
Il problema del flusso massimo consiste nel determinare la massima quantità di flusso che è possibile inviare da $s$ a $t$ attraverso $G$
Nodo sorgente fornisce flusso → $f$
Nodo destinazione assorbe flusso → $-f$
Tutti gli altri nodi sono nodi di transito
→ Voglio spedire dalla sorgente $s$ al pozzo $t$ la massima quantità di flusso $f$ senza violare i vincoli di capacità degli archi
$x_{ij} = \#\text{ flusso sull'arco } (i,j)$
$max \space f \\ \sum_{j \in FS(i)} x_{ij}- \sum_{k \in BS(i)} x_{ki} = \begin{cases} f \space\space\space\space \text{ se } i = s \\ -f \space\space\space\space \text{ se } i = t \\0 \space\space\space\space\text{ altrimenti} \end{cases} \\ x_{ij} \leq u_{ij} \space\space\space\space \forall (i,j) \in A \\ x_{ij} \geq 0 \space\space\space\space \forall (i,j) \in A$
Un vettore $\underline{x} \in \R^m$ è un flusso ammissibile per $G$ se soddisfa i vincoli del modello matematico
Un taglio $s$-$t$ è un partizionamento del vertici del grafo in due sottoinsiemi $V_1$ e $V_2$ tali che: