Flusso massimo

P

In una rete N=(V,A)N=(V,A) ogni arco ha una capacità kij≥0k_{ij}\ge 0; ss è la sorgente e dd il pozzo. Un flusso ammissibile xx rispetta le capacità e, in ogni nodo diverso da ss e dd, fa uscire quanto entra. Si cerca il flusso ammissibile di valore φ0\varphi_0 massimo, cioè quello che spedisce più flusso da ss a dd.

max⁡ φ0=∑j∈FS(s)xsj−∑j∈BS(s)xjss.a. ∑j∈FS(i)xij−∑j∈BS(i)xji=0∀ i∈V∖{s,d}0≤xij≤kij∀ (i,j)∈A\begin{aligned} \max\ & \varphi_0=\sum_{j\in FS(s)}x_{sj}-\sum_{j\in BS(s)}x_{js}\\ \text{s.a.}\ & \sum_{j\in FS(i)}x_{ij}-\sum_{j\in BS(i)}x_{ji}=0 && \forall\, i\in V\setminus\{s,d\}\\ & 0\le x_{ij}\le k_{ij} && \forall\,(i,j)\in A \end{aligned}

Perché è facile

È una PL, quindi si risolve in tempo polinomiale. La matrice dei vincoli di conservazione ha in ogni colonna al più un +1+1 e un −1-1 ed è totalmente unimodulare: con capacità intere esiste un flusso massimo intero.

Da ricordare

  • Max-flow/min-cut (Teorema 4.7.3): il flusso massimo è uguale alla capacità minima di una sezione, e nella capacità K(S)K(S) contano solo gli archi uscenti da SS.
  • Alla fine di Ford-Fulkerson i nodi etichettati formano la sezione minima S∗S^*, con φ0=K(S∗)\varphi_0=K(S^*).
  • Più sorgenti o pozzi si riducono a uno con una sorgente s∗s^* e un pozzo d∗d^* fittizi, su archi di capacità +∞+\infty.

Algoritmi

Fonti: dispensa §4.7.1-4.7.4, Teoremi 4.7.1-4.7.3, appunti Lezione 11, §4-8.