Problema del flusso massimo

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.

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.^[1][2][3] Nel 1955, Lester R. Ford, Jr. e Delbert R. Fulkerson pubblicarono il primo algoritmo noto, l'algoritmo di Ford-Fulkerson.^[4][5]

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).

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

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

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

1. ${\displaystyle 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. ${\displaystyle \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 ${\displaystyle |f|=\sum _{v:(s,v)\in E}f_{sv}}$, dove ${\displaystyle s}$ è la sorgente di ${\displaystyle N}$. Esso rappresenta l'ammontare di flusso che parte dalla sorgente per arrivare al pozzo.

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

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

1. L'insieme dei nodi di ${\displaystyle G_{f}}$ è lo stesso di ${\displaystyle G}$.
2. Ogni arco ${\displaystyle e=(u,v)}$ di ${\displaystyle G_{f}}$ ha una capacità ${\displaystyle c_{e}-f(e)}$.
3. Ogni arco ${\displaystyle e'=(v,u)}$ di ${\displaystyle G_{f}}$ ha una capacità ${\displaystyle 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	${\displaystyle 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	${\displaystyle O(VE^{2})}$	Una specializzazione dell'algoritmo di Ford–Fulkerson sfruttante la ricerca in ampiezza.
Algoritmo di Dinic con flusso bloccante	${\displaystyle 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 ${\displaystyle O(VE)}$ e il massimo numero di fasi è ${\displaystyle n-1}$. In reti con capacità unitarie l'algoritmo termina in tempo ${\displaystyle O(\min\{V^{2/3},E^{1/2}\}E)}$.
Algoritmo MPM (Malhotra, Pramodh-Kumar e Maheshwari)[6]	${\displaystyle O(V^{3})}$	Ci si riferisca alla pubblicazione originale.
Algoritmo di Dinic	${\displaystyle O(VElog(V))}$	La struttura di albero dinamico velocizza la computazione del flusso massimo nel grafo stratificato fino a ${\displaystyle O(Elog(V))}$.
Algoritmo push-relabel generico	${\displaystyle O(V^{2}E)}$
Algoritmo push-relabel con selezione FIFO	${\displaystyle O(V^{3})}$
Algoritmo push-relabel con alberi dinamici	${\displaystyle O\left(VE\log {\frac {V^{2}}{E}}\right)}$
Algoritmo KRT (King, Rao, Tarjan)[7]	${\displaystyle O(EV\log _{\frac {E}{V\log V}}V)}$
Algoritmo binario con flusso bloccante[8]	${\displaystyle O\left(E\cdot \min(V^{\frac {2}{3}},{\sqrt {E}})\cdot \log {\frac {V^{2}}{E}}\log {U}\right)}$	Il valore ${\displaystyle U}$ corrisponde alla capacità massima della rete.
Algoritmo di James B Orlin + KRT (King, Rao, Tarjan)[9]	${\displaystyle O(VE)}$	L'algoritmo di Orlin trova il flusso massimo in tempo ${\displaystyle O(VE)}$ per ${\displaystyle E\leq O(V^{{16 \over 15}-\epsilon })}$ mentre KRT risolve il problema in ${\displaystyle O(VE)}$ per ${\displaystyle E>V^{1+\epsilon }}$.

Questa sezione sull'argomento matematica è ancora vuota. Aiutaci a scriverla!

• (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 (WC · ACNP).
• (EN) Eugene Lawler, 4. Network Flows, in Combinatorial Optimization: Networks and Matroids, Dover, 2001, pp. 109-177, ISBN 0-486-41453-1.

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

• 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).

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica