La rete residua è la rete ausiliaria usata negli algoritmi per il flusso massimo. Dato un flusso corrente x su una rete con capacità u, la rete residua indica dove è ancora possibile aumentare il flusso e dove è possibile ridurre flusso già inviato.
Per un arco originale (i,j), la capacità residua in avanti è:
Se sull’arco è già presente flusso, compare anche un arco residuo all’indietro:
Questo arco inverso non rappresenta una condotta fisica nuova: rappresenta la possibilità algoritmica di correggere una scelta precedente, togliendo flusso da (i,j) per ridistribuirlo su altri cammini.
Cammini aumentanti
Un cammino da sorgente s a pozzo t nella rete residua è detto cammino aumentante. La quantità massima che si può aggiungere lungo quel cammino è il collo di bottiglia residuo:
Aggiornare il flusso di \Delta lungo il cammino aumenta il valore complessivo del flusso. Se un arco del cammino è un arco inverso, l’aggiornamento riduce il flusso sull’arco originale corrispondente.
Criterio di arresto
Gli algoritmi di Ford-Fulkerson, Edmonds-Karp e Dinic lavorano sulla rete residua. Quando non esiste più alcun cammino residuo da s a t, il flusso corrente è massimo.
La ragione è strutturale: i nodi ancora raggiungibili da s nella rete residua formano un insieme S^\star; il complemento T^\star contiene t. Gli archi da S^\star a T^\star nella rete originale sono saturi e identificano un taglio minimo. Per il teorema max-flow min-cut, flusso e taglio hanno lo stesso valore e certificano l’ottimalità.
Lettura operativa
| Oggetto | Formula o criterio | Significato |
|---|---|---|
| Capacità residua diretta | \displaystyle r_{ij}=u_{ij}-x_{ij} | spazio ancora disponibile sull’arco |
| Capacità residua inversa | \displaystyle r_{ji}=x_{ij} | flusso che si può annullare |
| Cammino aumentante | \displaystyle s\leadsto t nella rete residua | possibilità di migliorare il flusso |
| Bottleneck del cammino | \displaystyle \Delta=\min r_{ij} | incremento massimo ammissibile |
| Nessun cammino residuo | t non raggiungibile da s | flusso massimo raggiunto |
Errore tipico: ignorare gli archi inversi. Senza di essi, un algoritmo può restare bloccato su una scelta locale non ottima, perché non ha modo di riassegnare flusso già inviato.
Vedi anche: flusso massimo, teorema max-flow min-cut, ottimizzazione su reti.