Vai al contenuto

5.5 L'algoritmo Ford-Fulkerson

Parte 3 · Flussi · Capitolo 5 · Capitolo 5: Flusso massimo · Dispensa, volume 3 (PDF) · Esercizi: Flusso massimo · App: Flusso massimo: Ford–Fulkerson ed Edmonds–Karp

  • Per Teorema 5.8, un flusso può essere migliorato purché la sua rete residua abbia una percorso aumentante. L'algoritmo Ford–Fulkerson parte dal flusso zero e aumenta lungo tali percorsi fino a non ne è rimasto nessuno.

Algoritmo: Algoritmo Ford–Fulkerson

Input: un grafo diretto \(G=(N,A)\) con capacità intere \(u_{ij} \ge 0\), una sorgente \(s\) e un sink \(t\)
Output: un flusso massimo \(\vet{x}\) e un taglio minimo \((S,N \setminus S)\)
1Passaggio 0 (inizializzazione). Imposta \(x_{ij}:=0\) per ogni \((i,j) \in A\) e \(v:=0\).
2Passaggio 1 (ricerca). Costruisci la rete residua \(G(\vet{x})\) e cercala da \(s\).
3 Se \(t\) non è etichettato, STOP: \(\vet{x}\) è un flusso massimo e \(S\) è l'insieme dei nodi etichettati.
4Passaggio 2 (aumento). Sia \(P\) il percorso dei predecessori da \(s\) a \(t\) e \(\delta:=\min_{(i,j) \in P} r_{ij}\).
5 Aumenta \(\vet{x}\) insieme a \(P\) di \(\delta\), imposta \(v:=v+\delta\) e vai al passaggio 1.

  • Nel passaggio 1 è possibile utilizzare qualsiasi ricerca di Capitolo 1, Sezione «Grafo cerca». In questo modulo l'algoritmo Ford–Fulkerson utilizza la ricerca approfondita: \(\mathit{LIST}\) è uno stack, il gli archi residui che escono da ciascun nodo vengono scansionati aumentando l'indice della testa e la ricerca si interrompe non appena \(t\) è etichettato.

  • Quando la ricerca non etichetta \(t\), ha etichettato tutti i nodi raggiungibili da \(s\) (Capitolo 1, Teorema «correttezza della ricerca»): costituiscono l'insieme \(S\) dello Step 1.

Teorema 5.9: correttezza di Ford–Fulkerson

Lascia che le capacità siano intere. Allora ogni flusso calcolato dall'algoritmo Ford-Fulkerson è intero, l'algoritmo si ferma dopo al massimo gli aumenti \(\tilde{v}\) e alla fermata \(\vet{x}\) è un flusso massimo e \((S,N \setminus S)\) è un taglio minimo.

Dimostrazione

Usiamo Lemma 5.7 e Teorema 5.8.

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

  2. Terminazione. Ogni flusso è fattibile e ogni aumento aumenta il valore di \(\delta \ge 1\). Nessun valore supera \(\tilde{v}\), quindi ci sono al massimo aumenti \(\tilde{v}\).

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

Corollario 5.10: integralità

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

Dimostrazione

Il flusso restituito dall'algoritmo Ford–Fulkerson, da Teorema 5.9. □

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

  • Le capacità razionali diventano intere dopo la moltiplicazione per un denominatore comune, che moltiplica ogni flusso e ogni taglio dello stesso fattore: l'algoritmo si ferma anche alle capacità razionali.

Teorema 5.11: tempo di esecuzione di Ford–Fulkerson

Con capacità intere, l'algoritmo Ford–Fulkerson viene eseguito nel tempo \(O((n+m)\,\tilde{v})\) e \(\tilde{v} \le (n-1)\,U\), where \(U\) è la capacità maggiore.

Dimostrazione

Ogni iterazione crea \(G(\vet{x})\) nel tempo \(O(m)\), lo cerca nel tempo \(O(n+m)\), poiché \(G(\vet{x})\) ha al massimo \(2m\) archi (Capitolo 1, Teorema «tempo di esecuzione della ricerca»), e le variazioni al massimo \(n-1\) scorrono lungo \(P\). Ci sono al massimo \(\tilde{v}\) iterazioni con un aumento, più l'ultima.

  • Di Corollario 5.4 con \(S=\{s\}\), \(\tilde{v} \le u(\{s\},N \setminus \{s\})\), e \(s\) ha al massimo \(n-1\) archi uscenti, ciascuno con capacità al massimo \(U\).

□

  • Il limite cresce con il valore \(U\) delle capacità, e non solo con il numero delle loro cifre, di circa \(\log_2 U\): il tempo di esecuzione è pseudopolinomio. Esempio 5.7 mostra che il numero di gli aumenti possono 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 di Esempio 5.1. Ogni riga è un'iterazione: il percorso aumentante, le capacità residue dei suoi archi, gli archi arretrati che utilizza, il collo di bottiglia e il nuovo valore.

iterazione e percorso 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 zero) sono:

\[ \begin{array}{c|cccccccccc} \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 ricerca approfondita di Capitolo 1, Esempio «DFS da nodo \(1\)»: tutti gli archi sono vuoti, \(G(\vet{0})=G\), e il percorso passa attraverso l'arco \((4,3)\).

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

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

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

5.5.2 Il numero di aumenti

Esempio 5.7: molti miglioramenti

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

Figura 5

  • L'algoritmo Ford–Fulkerson consente qualsiasi percorso aumentante. Se i percorsi \(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: sono necessari gli aumenti \(2M\), due milioni per \(M=10^6\).

  • Con la ricerca approfondita di questo modulo, per \(M \ge 2\), i percorsi sono \(1,2,3,4\), quindi \(1,2,4\), \(1,3,2,4\) e \(1,3,4\), con \(\delta=1\), \(M-1\), \(1\), \(M-1\): quattro ampliamenti.

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

Avanti: 5.6 L'algoritmo Edmonds–Karp