Vai al contenuto

5.5 L'algoritmo di Ford–Fulkerson

  • Per il Teorema 5.8, un flusso si può migliorare finché la sua rete residua ha un cammino aumentante. L'algoritmo di Ford–Fulkerson parte dal flusso nullo e aumenta il flusso lungo questi cammini finché non ne rimane nessuno.

Algoritmo: Algoritmo di Ford–Fulkerson

Input: un grafo orientato \(G=(N,A)\) con capacità intere \(u_{ij} \ge 0\), una sorgente \(s\) e un pozzo \(t\)
Output: un flusso massimo \(\vet{x}\) e un taglio minimo \((S,N \setminus S)\)
1Passo 0 (inizializzazione). Poni \(x_{ij}:=0\) per ogni \((i,j) \in A\), e \(v:=0\).
2Passo 1 (visita). Costruisci la rete residua \(G(\vet{x})\) e visitala a partire da \(s\).
3 Se \(t\) non è etichettato, STOP: \(\vet{x}\) è un flusso massimo, e \(S\) è l'insieme dei nodi etichettati.
4Passo 2 (aumento). Sia \(P\) il cammino dei predecessori da \(s\) a \(t\), e \(\delta:=\min_{(i,j) \in P} r_{ij}\).
5 Aumenta \(\vet{x}\) lungo \(P\) di \(\delta\), poni \(v:=v+\delta\), e torna al Passo 1.

  • Il Passo 1 può usare qualunque visita della sezione «Visita di un grafo» del Capitolo 1. In questo modulo l'algoritmo di Ford–Fulkerson usa la visita in profondità: \(\mathit{LIST}\) è una pila, gli archi residui che escono da ogni nodo sono esaminati per indice crescente della testa, e la visita si ferma appena \(t\) è etichettato.

  • Quando la visita non etichetta \(t\), ha etichettato tutti i nodi raggiungibili da \(s\) (Capitolo 1, Teorema «correttezza della visita»): formano l'insieme \(S\) del Passo 1.

Teorema 5.9: correttezza di Ford–Fulkerson

Siano le capacità intere. Allora ogni flusso calcolato dall'algoritmo di Ford–Fulkerson è intero, l'algoritmo si ferma dopo al più \(\tilde{v}\) aumenti, e all'arresto \(\vet{x}\) è un flusso massimo e \((S,N \setminus S)\) è un taglio minimo.

Dimostrazione

Usiamo il Lemma 5.7 e il Teorema 5.8.

  1. Integralità. Il flusso nullo è intero. Se \(\vet{x}\) è intero, tutte le capacità residue sono intere, quindi \(\delta\) è un intero positivo e il flusso aumentato è intero.

  2. Terminazione. Ogni flusso è ammissibile, e ogni aumento accresce il valore di \(\delta \ge 1\). Nessun valore supera \(\tilde{v}\), quindi gli aumenti sono al più \(\tilde{v}\).

  3. Ottimalità. All'arresto \(t\) non è etichettato, quindi \(G(\vet{x})\) non ha cammini aumentanti e \(S\) è l'insieme dei nodi raggiungibili da \(s\). La dimostrazione di (b) implica (c) dà \(v=u(S,N \setminus S)\): il flusso è massimo e il taglio è minimo. □

Corollario 5.10: integralità

Se tutte le capacità sono intere, esiste un flusso massimo con componenti intere.

Dimostrazione

È il flusso restituito dall'algoritmo di Ford–Fulkerson, per il Teorema 5.9. □

  • La stessa conclusione segue dal Teorema «vertici interi» del Capitolo 4: con l'arco \((t,s)\), il modello \(\mathrm{MF}\) è un modello di flusso di costo minimo con dati interi, e il suo ottimo è raggiunto in un vertice intero.

  • Le capacità razionali diventano intere moltiplicandole per un denominatore comune, che moltiplica ogni flusso e ogni taglio per lo stesso fattore: l'algoritmo si ferma anche con capacità razionali.

Teorema 5.11: tempo di esecuzione di Ford–Fulkerson

Con capacità intere, l'algoritmo di Ford–Fulkerson richiede tempo \(O((n+m)\,\tilde{v})\), e \(\tilde{v} \le (n-1)\,U\), dove \(U\) è la capacità più grande.

Dimostrazione

Ogni iterazione costruisce \(G(\vet{x})\) in tempo \(O(m)\), la visita in tempo \(O(n+m)\), perché \(G(\vet{x})\) ha al più \(2m\) archi (Capitolo 1, Teorema «tempo di esecuzione della visita»), e cambia al più \(n-1\) flussi lungo \(P\). Le iterazioni con un aumento sono al più \(\tilde{v}\), più l'ultima.

  • Per il Corollario 5.4 con \(S=\{s\}\), \(\tilde{v} \le u(\{s\},N \setminus \{s\})\), e da \(s\) escono al più \(n-1\) archi, ciascuno con capacità al più \(U\).

□

  • Il limite cresce con il valore \(U\) delle capacità, e non solo con il numero delle loro cifre, circa \(\log_2 U\): il tempo di esecuzione è pseudopolinomiale. L'Esempio 5.7 mostra che il numero di aumenti può davvero crescere con le capacità.

5.5.1 Ford–Fulkerson sulla rete di riferimento

Esempio 5.6: Ford–Fulkerson sulla rete di riferimento

Eseguiamo l'algoritmo sulla rete dell'Esempio 5.1. Ogni riga è un'iterazione: il cammino aumentante, le capacità residue dei suoi archi, gli archi all'indietro che usa, il collo di bottiglia e il nuovo valore.

iterazione cammino aumentante \(r_{ij}\) su \(P\) archi all'indietro \(\delta\) \(v\)
\(1\) \(1,2,4,3,5,6\) \(5,3,2,4,3\) – \(2\) \(2\)
\(2\) \(1,2,4,6\) \(3,1,4\) – \(1\) \(3\)
\(3\) \(1,3,4,6\) \(4,2,3\) \((3,4)\) \(2\) \(5\)
\(4\) \(1,3,5,4,6\) \(2,2,2,1\) – \(1\) \(6\)
\(5\) \(1,3,5,6\) \(1,1,1\) – \(1\) \(7\)

I flussi dopo ogni iterazione (\(k=0\) è il flusso nullo) sono:

\[ \begin{array}{c|ccccccccc} \hline {k} & {x_{12}} & {x_{13}} & {x_{24}} & {x_{32}} & {x_{35}} & {x_{43}} & {x_{46}} & {x_{54}} & {x_{56}} \\ \hline {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} \\ {1} & {2} & {0} & {2} & {0} & {2} & {2} & {0} & {0} & {2} \\ {2} & {3} & {0} & {3} & {0} & {2} & {2} & {1} & {0} & {2} \\ {3} & {3} & {2} & {3} & {0} & {2} & {0} & {3} & {0} & {2} \\ {4} & {3} & {3} & {3} & {0} & {3} & {0} & {4} & {1} & {2} \\ {5} & {3} & {4} & {3} & {0} & {4} & {0} & {4} & {1} & {3} \\ \hline \end{array} \]
  • L'iterazione \(1\) è la visita in profondità dell'Esempio «DFS dal nodo \(1\)» del Capitolo 1: tutti gli archi sono vuoti, \(G(\vet{0})=G\), e il cammino passa per l'arco \((4,3)\).

  • Dopo l'iterazione \(2\) il flusso è \(\bar{\vet{x}}\) dell'Esempio 5.1, e l'iterazione \(3\) è l'aumento dell'Esempio 5.3: l'arco all'indietro \((3,4)\) annulla le due unità inviate su \((4,3)\) nell'iterazione \(1\).

  • La sesta visita etichetta solo i nodi \(1\) e \(2\), e l'algoritmo si ferma: il flusso è \(\tilde{\vet{x}}\) dell'Esempio 5.5, e \(S=\{1,2\}\) dà il taglio minimo di capacità \(u_{13}+u_{24}=7\).

  • L'algoritmo esegue \(5\) aumenti, entro il limite \(\tilde{v}=7\) del Teorema 5.9.

5.5.2 Il numero di aumenti

Esempio 5.7: molti aumenti

Nella rete qui sotto, \(M\) è un intero positivo. I cammini \(1,2,4\) e \(1,3,4\) portano \(M\) unità ciascuno, e il taglio \(S=\{1\}\) ha capacità \(2M\), quindi \(\tilde{v}=2M\).

Figura 5

  • L'algoritmo di Ford–Fulkerson ammette qualunque cammino aumentante. Se i cammini \(1,2,3,4\) e \(1,3,2,4\) si alternano, il secondo attraverso l'arco all'indietro \((3,2)\), ogni collo di bottiglia è \(\delta=1\), dato dall'arco \((2,3)\) o dal suo arco all'indietro: servono \(2M\) aumenti, due milioni per \(M=10^6\).

  • Con la visita in profondità di questo modulo, per \(M \ge 2\), i cammini sono \(1,2,3,4\), poi \(1,2,4\), \(1,3,2,4\) e \(1,3,4\), con \(\delta=1\), \(M-1\), \(1\), \(M-1\): quattro aumenti.

L'algoritmo di Ford–Fulkerson aumenta il flusso lungo cammini della rete residua finché non ne rimane nessuno. Con capacità intere si ferma dopo al più \(\tilde{v}\) aumenti, con un flusso massimo intero e un taglio minimo; il suo tempo di esecuzione \(O((n+m)\,\tilde{v})\) è pseudopolinomiale.


Avanti: 5.6 L'algoritmo di Edmonds–Karp