Un acquedotto porta acqua da una sorgente a una città attraverso una rete di tubi, ciascuno con una portata massima. Quanta acqua al secondo può arrivare, al massimo, alla città? E se si volesse ridurre quella quantità tagliando alcuni tubi, quali sarebbero i più convenienti da tagliare? Sono due domande in apparenza diverse, ma hanno la stessa risposta numerica. È uno dei risultati più belli dell'ottimizzazione combinatoria: il teorema flusso massimo – taglio minimo.
Il modello: una rete di flusso
Una rete di flusso è un grafo orientato con:
- una sorgente s, da cui il flusso parte;
- un pozzo t, dove il flusso arriva;
- una capacità c(u, v) ≥ 0 su ogni arco.
Un flusso assegna a ogni arco una quantità f(u, v) che rispetta due regole:
- vincolo di capacità: 0 ≤ f(u, v) ≤ c(u, v);
- conservazione: in ogni vertice diverso da s e t, quanto entra è uguale a quanto esce.
Il valore del flusso è la quantità totale che esce da s, uguale a quella che entra in t. Il problema del flusso massimo chiede il flusso di valore più alto.
Il grafo residuo
L'idea più ingegnosa è il grafo residuo. Per ogni arco (u, v) con flusso f e capacità c si considerano:
- un arco in avanti con capacità residua c − f, cioè quanto si può ancora spingere;
- un arco all'indietro (v, u) con capacità f, cioè quanto flusso si può «annullare».
Gli archi all'indietro sono essenziali. Permettono all'algoritmo di correggere una scelta precedente: se un primo percorso ha usato male un tubo, un percorso successivo può deviare quel flusso altrove.
Ford-Fulkerson: cammini aumentanti
Lo schema generale è semplice:
- parti dal flusso nullo;
- cerca nel grafo residuo un cammino da s a t, detto cammino aumentante;
- trova la capacità residua minima lungo il cammino (il «collo di bottiglia») e spingi quella quantità lungo tutto il cammino;
- ripeti finché non esistono più cammini aumentanti.
Quando l'algoritmo si ferma, il flusso è massimo. Con capacità intere ogni iterazione aumenta il flusso di almeno 1, quindi l'algoritmo termina e il flusso massimo trovato è a sua volta intero. Questa proprietà di integralità è fondamentale nelle applicazioni: garantisce soluzioni fatte di unità intere, come persone o veicoli.
Edmonds-Karp: scegliere bene il cammino
Ford-Fulkerson non specifica quale cammino aumentante scegliere, e una scelta sfortunata può richiedere moltissime iterazioni. Edmonds-Karp fissa la regola: si sceglie sempre il cammino aumentante con il minor numero di archi, trovato con una visita in ampiezza.
Con questa regola il numero di iterazioni è limitato indipendentemente dai valori delle capacità, e il costo totale è proporzionale a n · m². Per grafi molto grandi esistono algoritmi più rapidi, come quello di Dinic o i metodi push-relabel, ma Edmonds-Karp resta un ottimo punto di partenza: è corto, chiaro e affidabile.
Il taglio minimo
Un taglio s–t divide i vertici in due gruppi, S contenente s e T contenente t. La sua capacità è la somma delle capacità degli archi che vanno da S a T. Qualunque flusso deve attraversare il taglio, quindi nessun flusso può superare la capacità di nessun taglio.
Il teorema afferma che il valore del flusso massimo è uguale alla capacità del taglio minimo. Inoltre, alla fine di Ford-Fulkerson il taglio si trova gratis: S è l'insieme dei vertici ancora raggiungibili da s nel grafo residuo. Gli archi da S a T sono tutti saturi e formano il taglio minimo.
Un esempio
Archi con capacità: s→a 10, s→b 5, a→b 15, a→t 5, b→t 10.
- Cammino s→a→t: collo di bottiglia 5. Flusso totale 5.
- Cammino s→b→t: collo di bottiglia 5. Flusso totale 10.
- Cammino s→a→b→t: residui 5, 15, 5. Collo di bottiglia 5. Flusso totale 15.
A questo punto entrambi gli archi uscenti da s sono saturi: s→a porta 10 su 10, s→b porta 5 su 5. Non esistono più cammini aumentanti: il flusso massimo è 15, e il taglio minimo è {s} contro il resto, con capacità 10 + 5 = 15.
Dove si usa
- Logistica e trasporti: quante merci al giorno possono passare da un porto a un centro di distribuzione su una rete con limiti di capacità.
- Reti informatiche: la banda massima tra due punti, e i collegamenti che costituiscono il vero collo di bottiglia. Il taglio minimo indica dove investire per aumentare la capacità.
- Affidabilità: con capacità 1 su ogni arco, il flusso massimo è il numero di percorsi indipendenti tra due nodi, e il taglio minimo è il numero di collegamenti da interrompere per isolarli.
- Visione artificiale: la segmentazione di immagini in primo piano e sfondo si formula come taglio minimo su un grafo di pixel.
- Abbinamenti: assegnare lavoratori a turni o studenti a progetti si riduce a un flusso massimo su un grafo bipartito.
In sintesi
- Una rete di flusso ha sorgente, pozzo e capacità; il flusso rispetta capacità e conservazione.
- Ford-Fulkerson spinge flusso lungo cammini aumentanti nel grafo residuo.
- Edmonds-Karp sceglie i cammini più corti con una BFS, con costo n · m².
- Il flusso massimo è uguale alla capacità del taglio minimo, che si ricava dal grafo residuo finale.
- Con capacità intere il flusso massimo è intero, proprietà decisiva per assegnamenti e logistica.
