5.4 Il teorema flusso massimo-taglio minimo¶
Parte 3 · Flussi · Capitolo 5 · Capitolo 5: Flusso massimo · Dispensa, volume 3 (PDF) · Slide · Esercizi: Flusso massimo · App: Flusso massimo: Ford–Fulkerson ed Edmonds–Karp
Teorema 5.8: flusso massimo-taglio minimo
Sia \(\vet{x}\) un flusso ammissibile di valore \(v\). Le seguenti affermazioni sono equivalenti:
-
(a) \(\vet{x}\) è un flusso massimo;
-
(b) la rete residua \(G(\vet{x})\) non ha cammini aumentanti;
-
(c) \(v=u(S,N \setminus S)\) per qualche taglio \(s\)–\(t\) \((S,N \setminus S)\).
Inoltre, un flusso massimo esiste, e il valore massimo di un flusso è uguale alla capacità minima di un taglio \(s\)–\(t\):
Dimostrazione
(a) implica (b). Un cammino aumentante darebbe, per il Lemma 5.7, un flusso ammissibile di valore \(v+\delta>v\).
(b) implica (c). Sia \(S\) l'insieme dei nodi raggiungibili da \(s\) in \(G(\vet{x})\); allora \(s \in S\) e, per (b), \(t \notin S\).
-
Se un arco \((i,j) \in \delta^+(S)\) avesse \(x_{ij}<u_{ij}\), l'arco in avanti \((i,j)\) sarebbe in \(G(\vet{x})\), e \(j\) sarebbe raggiungibile: quindi \(x_{ij}=u_{ij}\).
-
Se un arco \((i,j) \in \delta^-(S)\) avesse \(x_{ij}>0\), l'arco all'indietro \((j,i)\), con \(j \in S\), sarebbe in \(G(\vet{x})\), e \(i\) sarebbe raggiungibile: quindi \(x_{ij}=0\).
-
Per il Corollario 5.4, \(v=u(S,N \setminus S)\).
(c) implica (a). Per il Corollario 5.4.
Esistenza e uguaglianza. La regione ammissibile del modello \(\mathrm{MF}\) è non vuota (\(\vet{x}=\vet{0}\), \(v=0\)) e limitata (\(0 \le x_{ij} \le u_{ij}\) e \(|v| \le \sum_{(i,j) \in A} u_{ij}\)), quindi il modello ha una soluzione ottima (Capitolo 15 «La geometria della programmazione lineare»). Per un flusso massimo, (a) implica (c): qualche taglio ha capacità \(\tilde{v}\), e per il Corollario 5.4 nessun taglio ha capacità minore. □
-
La dimostrazione di (b) implica (c) è costruttiva: in un flusso massimo, i nodi raggiungibili da \(s\) nella rete residua formano un taglio minimo.
-
Un flusso e un taglio con \(v=u(S,N \setminus S)\) si certificano a vicenda: il taglio dimostra che nessun flusso è migliore, e il flusso dimostra che nessun taglio è più piccolo.
Esempio 5.5: il flusso massimo della rete di riferimento
Sulla rete di riferimento dell'Esempio 5.1 il flusso
| arco | \((1,2)\) | \((1,3)\) | \((2,4)\) | \((3,2)\) | \((3,5)\) | \((4,3)\) | \((4,6)\) | \((5,4)\) | \((5,6)\) |
|---|---|---|---|---|---|---|---|---|---|
| \(\tilde{x}_{ij}\) | \(3\) | \(4\) | \(3\) | \(0\) | \(4\) | \(0\) | \(4\) | \(1\) | \(3\) |
| \(u_{ij}\) | \(5\) | \(4\) | \(3\) | \(2\) | \(4\) | \(2\) | \(4\) | \(2\) | \(3\) |
è ammissibile, con valore \(\tilde{x}_{12}+\tilde{x}_{13}=7\). Per \(S=\{1,2\}\) gli archi in avanti \((1,3)\), \((2,4)\) sono saturi e l'arco all'indietro \((3,2)\) è vuoto, quindi
Per il Teorema 5.8, \(\tilde{\vet{x}}\) è un flusso massimo, \(\tilde{v}=7\), e \((\{1,2\},\{3,4,5,6\})\) è un taglio minimo. In \(G(\tilde{\vet{x}})\) i nodi raggiungibili da \(1\) sono esattamente \(1\) e \(2\). Nella figura, \(S\) è ombreggiato e gli archi in avanti del taglio sono verdi.
-
Unicità. Per il Corollario 5.4, ogni flusso massimo satura gli archi in avanti e svuota gli archi all'indietro di ciascuno dei tre tagli minimi dell'Esempio 5.2:
\[ \begin{aligned} S=\{1,2\}: &\quad x_{13}=4,~ x_{24}=3,~ x_{32}=0,\\ S=\{1,2,3\}: &\quad x_{35}=4,~ x_{43}=0,\\ S=\{1,2,3,4,5\}: &\quad x_{46}=4,~ x_{56}=3. \end{aligned} \]La conservazione nei nodi \(1\) e \(4\) dà allora \(x_{12}=7-x_{13}=3\) e \(x_{54}=x_{43}+x_{46}-x_{24}=1\): \(\tilde{\vet{x}}\) è l'unico flusso massimo, mentre il taglio minimo non è unico.
Archi saturi e tagli
Gli archi saturi di un flusso massimo in generale non formano un taglio. Con \(\tilde{\vet{x}}\) gli archi saturi sono \((1,3)\), \((2,4)\), \((3,5)\), \((4,6)\), \((5,6)\), con capacità totale \(18\). Un taglio minimo si legge dai nodi raggiungibili da \(s\) nella rete residua.
Un flusso è massimo se e solo se la sua rete residua non ha cammini aumentanti, se e solo se il suo valore è uguale alla capacità di un taglio. Il valore massimo è uguale alla capacità minima di un taglio, e i nodi raggiungibili da \(s\) nella rete residua di un flusso massimo formano un taglio minimo.