Problema del flusso massimo

Una rete con un esempio di flusso massimo. La sorgente è s ed il pozzo è t. I numeri denotano flusso e capacità degli archi.

Nella teoria dell'ottimizzazione, il problema del flusso massimo consiste nel trovare, in una rete di flusso con una sola sorgente ed un solo pozzo, un flusso ammissibile che sia massimo.

Il problema del flusso massimo può essere visto come un caso particolare di problemi più complessi sulle reti di flusso, come il problema della circolazione. Il valore massimo di un flusso s-t (ovvero un flusso generato da una sorgente s che si esaurisce in un pozzo t) è equivalente alla capacità minima di un taglio s-t nella medesima rete, come enunciato dal teorema del flusso massimo e taglio minimo.

Storia

Il problema del flusso massimo venne formulato per la prima volta nel 1954 da T. E. Harris e F. S. Ross per la semplificazione del modello del flusso del sistema ferroviario sovietico. Nel 1955, Lester R. Ford, Jr. e Delbert R. Fulkerson pubblicarono il primo algoritmo noto, l'algoritmo di Ford-Fulkerson.

Negli anni a venire, vennero ideate varie soluzioni al problema, fra cui le più note sono quelle degli statunitensi Edmonds e Karp (1972) e del sovietico Dinitz (1970).

Definizione

Una rete di flusso, con sorgente s e pozzo t. I numeri vicini agli archi rappresentano le rispettive capacità.

Sia $N=(V,E)$ una rete con $s,t\in V$ rispettivamente sorgente e pozzo di $N$.

La capacità di un arco è una funzione $c:E\to \mathbb {R} ^{+}$, indicata con $c_{uv}$ o $c(u,v)$, che rappresenta il massimo flusso che può passare per un arco.

Un flusso è una funzione $f:E\to \mathbb {R} ^{+}$, indicata con $f_{uv}$ o $f(u,v)$, soggetta ai due vincoli seguenti:

1. $f_{uv}\leq c_{uv}\forall (u,v)\in E$ (vincolo di capacità: il flusso passante in un arco non può essere maggiore della capacità dello stesso);
2. $\sum _{u:(u,v)\in E}f_{uv}=\sum _{u:(v,u)\in E}f_{vu}\forall v\in V\setminus \{s,t\}$ (vincolo di conservazione del flusso: la somma dei flussi entranti in un nodo dev'essere uguale alla somma dei flussi uscenti dallo stesso, tranne che per la sorgente ed il pozzo).

Il valore di flusso è definito da $|f|=\sum _{v:(s,v)\in E}f_{sv}$, dove $s$ è la sorgente di $N$. Esso rappresenta l'ammontare di flusso che parte dalla sorgente per arrivare al pozzo.

Il problema del flusso massimo è quello di massimizzare $|f|$, ovvero, di instradare quanto più flusso possibile da $s$ a $t$.

Soluzioni

Per comprendere le varie soluzioni del problema è necessario introdurre il concetto di rete residua. Data una rete di flusso $G$ ed un flusso $f$ su $G$, definiamo la rete residua $G_{f}$ su $G$ rispetto a $f$ come segue:

1. L'insieme dei nodi di $G_{f}$ è lo stesso di $G$.
2. Ogni arco $e=(u,v)$ di $G_{f}$ ha una capacità $c_{e}-f(e)$.
3. Ogni arco $e'=(v,u)$ di $G_{f}$ ha una capacità $f(e)$.

La seguente tabella elenca gli algoritmi più noti per risolvere il problema del flusso massimo.

Metodo	Complessità computazionale	Note
Algoritmo di Ford-Fulkerson	$O(E\ max|f|)$	La terminazione dell'algoritmo è garantita se tutti i pesi sono razionali, altrimenti è possibile che l'algoritmo non converga al valore massimo. In ogni caso, se l'algoritmo termina, è garantita la correttezza del risultato.
Algoritmo di Edmonds-Karp	$O(VE^{2})$	Una specializzazione dell'algoritmo di Ford–Fulkerson sfruttante la ricerca in ampiezza.
Algoritmo di Dinic con flusso bloccante	$O(V^{2}E)$	In ogni fase dell'algoritmo viene costruito un grafo stratificato tramite ricerca in ampiezza sul grafo residuo. Il flusso massimo su un grafo stratificato può essere calcolato in tempo $O(VE)$ e il massimo numero di fasi è $n-1$. In reti con capacità unitarie l'algoritmo termina in tempo $O(\min\{V^{2/3},E^{1/2}\}E)$.
Algoritmo MPM (Malhotra, Pramodh-Kumar e Maheshwari)	$O(V^{3})$	Ci si riferisca alla pubblicazione originale.
Algoritmo di Dinic	$O(VElog(V))$	La struttura di albero dinamico velocizza la computazione del flusso massimo nel grafo stratificato fino a $O(Elog(V))$.
Algoritmo push-relabel generico	$O(V^{2}E)$
Algoritmo push-relabel con selezione FIFO	$O(V^{3})$
Algoritmo push-relabel con alberi dinamici	$O\left(VE\log {\frac {V^{2}}{E}}\right)$
Algoritmo KRT (King, Rao, Tarjan)	$O(EV\log _{\frac {E}{V\log V}}V)$
Algoritmo binario con flusso bloccante	$O\left(E\cdot \min(V^{\frac {2}{3}},{\sqrt {E}})\cdot \log {\frac {V^{2}}{E}}\log {U}\right)$	Il valore $U$ corrisponde alla capacità massima della rete.
Algoritmo di James B Orlin + KRT (King, Rao, Tarjan)	$O(VE)$	L'algoritmo di Orlin trova il flusso massimo in tempo $O(VE)$ per $E\leq O(V^{{16 \over 15}-\epsilon })$ mentre KRT risolve il problema in $O(VE)$ per $E>V^{1+\epsilon }$.

Bibliografia

• (EN) Joseph Cheriyan and Kurt Mehlhorn, An analysis of the highest-level selection rule in the preflow-push max-flow algorithm, in Information Processing Letters, vol. 69, n. 5, 1999, pp. 239-242, DOI:10.1016/S0020-0190(99)00019-8.
• (EN) Daniel D. Sleator and Robert E. Tarjan, A data structure for dynamic trees (PDF), in Journal of Computer and System Sciences, vol. 26, n. 3, 1983, pp. 362-391, DOI:10.1016/0022-0000(83)90006-5, ISSN 0022-0000.
• (EN) Eugene Lawler, 4. Network Flows, in Combinatorial Optimization: Networks and Matroids, Dover, 2001, pp. 109-177, ISBN 0-486-41453-1.

Voci correlate

• Algoritmo di Ford-Fulkerson
• Algoritmo di Edmonds-Karp
• Algoritmo di Dinic
• Problema del flusso di costo minimo

Collegamenti esterni

• Marco Di Summa, Il problema del Flusso Massimo (PDF), su math.unipd.it, Università degli Studi di Padova, Dipartimento di Matematica. URL consultato il 31 agosto 2016 (archiviato il 27 giugno 2013).