1. Rete e flusso

Una rete di flusso (flow network) è un grafo orientato finito $G=(V,E)$ con due vertici distinti: una sorgente s e un pozzo t (sink). Ogni arco ha una capacità finita e non negativa c(u,v). Il flusso f(u,v) è la quantità che effettivamente percorre quell’arco.

Poniamo f(u,v) = 0 quando l’arco non esiste. Usiamo la convenzione del flusso non negativo su ciascun arco originale; non imponiamo f(u,v) = −f(v,u). Il valore del flusso è l’uscita netta dalla sorgente, uguale all’entrata netta nel pozzo:

Il problema del flusso massimo cerca un flusso ammissibile che massimizzi |f|. Non si sommano i flussi di tutti gli archi: la stessa quantità può attraversarne diversi. Se non esce flusso da t e non ne entra in s, bastano le somme in entrata a t o in uscita da s.

2. La rete residua: aggiungere e ripensare

Per ogni arco originale u → v creiamo due possibilità nella rete residua G_f. Manteniamo soltanto quelle con capacità residua strettamente positiva.

• Avanti, u → v: capacità c(u,v) − f(u,v). Possiamo aggiungere questa quantità.
• Indietro, v → u: capacità f(u,v). Possiamo annullare questa quantità già assegnata.

Esempio: un arco di capacità 7 che trasporta 4 lascia 3 unità in avanti e 4 indietro. Un arco inverso non è un nuovo tubo: usarlo riduce il flusso sull’arco originale, liberando risorse per un percorso diverso.

Un cammino aumentante è un cammino da s a t nella rete residua. Il suo collo di bottiglia Δ è la minima capacità residua lungo il cammino. Aumentiamo di Δ sugli archi percorsi in avanti e diminuiamo di Δ su quelli percorsi all’indietro. Il valore totale cresce di Δ.

3. Una rete, due modi di aumentare il flusso

Le etichette indicano flusso / capacità. Ford–Fulkerson con DFS visita prima a e poi b: così vediamo una scelta che sarà corretta con l’arco inverso b → a. Edmonds–Karp usa BFS e sceglie cammini con il minor numero di archi residui.

4. Il taglio certifica il massimo

Un taglio s–t è una partizione (S,T) di V, con s ∈ S e t ∈ T. La sua capacità c(S,T) è la somma delle capacità degli archi originali da S verso T; quelli da T verso S non si contano.

Per conservazione, il flusso netto attraverso qualsiasi taglio è |f|. Il flusso in avanti non supera la capacità del taglio e quello di ritorno è non negativo: quindi |f| ≤ c(S,T). Il teorema max-flow/min-cut afferma che questo limite si può raggiungere:

Perché l’assenza di cammini aumentanti basta

1. Sia S l’insieme dei vertici raggiungibili da s nella rete residua. Se t non è raggiungibile, (S,V ∖ S) è un taglio.
2. Ogni arco originale da S a T è saturo: altrimenti il suo arco residuo consentirebbe di raggiungere un altro vertice.
3. Ogni arco originale da T a S ha flusso zero: altrimenti l’arco residuo inverso attraverserebbe il taglio da S a T.
4. Quindi |f| = c(S,T). Abbiamo insieme un flusso massimo e un taglio minimo.

In modo equivalente: un flusso è massimo se e solo se non esiste un cammino aumentante nella sua rete residua. Flusso massimo e taglio minimo possono non essere unici.

5. Ford–Fulkerson ed Edmonds–Karp

Ford–Fulkerson è un metodo: ripete gli aumenti finché esiste un cammino residuo. Edmonds–Karp specifica come sceglierlo: una BFS trova quello più corto in numero di archi, non quello con maggiore capacità.

inizializza f = 0 su tutti gli archi
finché esiste un cammino P da s a t nella rete residua:
    Δ = minima capacità residua su P
    per ogni arco residuo e di P:
        residua[e] -= Δ
        residua[inverso(e)] += Δ
    valore += Δ
restituisci f e i vertici raggiungibili da s nel residuo

Nel codice con coppie residue, il flusso di un arco originale si ricava come capacità iniziale meno capacità residua avanti. Ogni aggiornamento deve modificare anche l’inverso.

Entrambi richiedono spazio O(n + m) con liste di adiacenza. Nel limite usuale di Edmonds–Karp si considerano i vertici della rete rilevante; l’inizializzazione di eventuali vertici isolati aggiunge O(n). Le distanze BFS nel residuo non diminuiscono: un arco può diventare il collo di bottiglia solo O(n) volte, da cui O(nm) aumenti.

Con capacità razionali Ford–Fulkerson termina, ma scalare a interi può produrre numeri molto grandi. Con capacità irrazionali e scelte arbitrarie dei cammini può non terminare. Con capacità intere esiste un flusso massimo intero, perché ogni aumento conserva l’integralità; non significa che ogni soluzione ottima debba essere intera.

6. Applicazioni

• Matching bipartito: aggiungi s → L, gli archi L → R e R → t, tutti con capacità 1. Un flusso massimo intero seleziona il massimo numero di coppie disgiunte.
• Cammini disgiunti per archi: con capacità unitarie, il valore massimo conta quanti cammini s–t possono evitare di condividere archi.
• Limiti sui vertici: separa v in v_in e v_out, collegati da un arco con la capacità del vertice; reindirizza gli archi in entrata e in uscita.
• Più sorgenti o pozzi: aggiungi una supersorgente o un superpozzo, con archi dimensionati sulle disponibilità e sulle richieste. Quando serve una capacità “infinita”, usa un limite finito sufficiente, per esempio la somma delle capacità originali.

Il flusso massimo ottimizza la quantità. Per ottimizzare anche un costo per unità trasportata serve un problema diverso: il flusso a costo minimo.

7. Errori comuni

• Cercare cammini solo negli archi originali non saturi. Si perdono gli archi inversi e si può arrestare il metodo prima dell’ottimo.
• Confondere saturo con definitivo. Un arco pieno può essere svuotato parzialmente da un successivo aumento inverso.
• Sommare entrambe le direzioni di un taglio. La capacità conta solo S → T; il flusso netto sottrae T → S.
• Interpretare il risultato come un singolo percorso. Il flusso può dividersi su più cammini e una soluzione ammissibile può contenere cicli.

8. Prova prima di aprire la soluzione