Il teorema max-flow min-cut stabilisce che, in una rete orientata con capacità non negative sugli archi, il valore massimo di un flusso da sorgente a pozzo è uguale alla capacità minima di un taglio che separa la sorgente s dal pozzo t.
Enunciato
Sia G=(V,A) una rete con sorgente s, pozzo t e capacità u_{ij}\ge 0 sugli archi. Un taglio s-t è una partizione dei nodi in due insiemi S e T tali che s\in S e t\in T. La sua capacità è:
Il teorema afferma:
dove v è il valore del flusso ammissibile. La formula dice che il miglior flusso possibile è esattamente limitato dal taglio più stretto della rete.
Perché ogni taglio limita il flusso
Per qualunque flusso ammissibile e qualunque taglio S-T, il flusso netto che attraversa il taglio non può superare la capacità degli archi da S a T:
Questa è la parte intuitiva del teorema: una sezione della rete non può lasciar passare più flusso della capacità totale dei suoi archi in avanti.
| Oggetto | Formula | Ruolo |
|---|---|---|
| Flusso ammissibile | \displaystyle 0\le x_{ij}\le u_{ij} | Soluzione che rispetta capacità e conservazione. |
| Taglio \displaystyle s-\displaystyle t | \displaystyle s\in S,\ t\in T | Separazione tra origine e destinazione. |
| Capacità del taglio | \displaystyle u(S,T)=\sum_{i\in S,\ j\in T}u_{ij} | Limite superiore per ogni flusso. |
| Ottimalità | \displaystyle v^\star=u(S^\star,T^\star) | Flusso e taglio forniscono un certificato reciproco. |
Collegamento con la rete residua
Gli algoritmi di incremento costruiscono flussi sempre più grandi lungo cammini residui. Quando non esiste più un cammino residuo da s a t, i nodi ancora raggiungibili da s nella rete residua formano l’insieme S^\star di un taglio minimo.
In quel caso:
e quindi il flusso corrente è massimo. La rete residua non serve solo a trovare un algoritmo: produce anche il certificato strutturale del collo di bottiglia.
Interpretazione duale
Il problema di flusso massimo può essere formulato come programma lineare. Il problema duale corrisponde, in forma di rete, alla ricerca del taglio minimo. Il teorema max-flow min-cut è quindi una forma speciale di dualità forte, molto più leggibile perché il duale ha un significato grafico immediato.
| Lettura | Primale | Duale |
|---|---|---|
| Rete | \displaystyle \max v | \displaystyle \min u(S,T) |
| Decisione | inviare flusso sugli archi | scegliere una separazione sorgente-pozzo |
| Certificato | flusso ammissibile | taglio di uguale capacità |
Uso operativo
In un problema reale, il teorema permette di leggere due informazioni insieme:
- quanto flusso massimo può attraversare la rete;
- quali archi costituiscono il collo di bottiglia che impedisce di aumentarlo.
Questo è utile in logistica, reti di comunicazione, capacità produttiva, distribuzione di risorse e analisi di vulnerabilità: aumentare la capacità su archi non appartenenti a un taglio minimo può non migliorare affatto il flusso massimo.
Errori comuni
- Pensare che il taglio minimo sia sempre l’arco di capacità minima: un taglio è un insieme di archi.
- Confondere capacità del taglio e flusso effettivo sul taglio quando il flusso non è ottimo.
- Dimenticare gli archi orientati: contano nella capacità del taglio solo gli archi da S verso T.
- Usare il teorema senza verificare l’ammissibilità del flusso, cioè capacità e conservazione.
Vedi anche: Flusso massimo, Rete residua, Ottimizzazione su reti, Programmazione lineare, Formulario di ricerca operativa.