5.5 L'algoritmo di Ford–Fulkerson¶
Parte 3 · Flussi · Capitolo 5 · Capitolo 5: Flusso massimo · Dispensa, volume 3 (PDF) · Slide · Esercizi: Flusso massimo · App: Flusso massimo: Ford–Fulkerson ed Edmonds–Karp
- 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
STOP: \(\vet{x}\) è un flusso massimo, e \(S\) è l'insieme dei nodi etichettati.-
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.
-
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.
-
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}\).
-
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:
-
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\).
-
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