Problema del flusso massimo

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search
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[modifica | modifica wikitesto]

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

Definizione[modifica | modifica wikitesto]

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

Sia una rete con rispettivamente sorgente e pozzo di .

La capacità di un arco è una funzione , indicata con o , che rappresenta il massimo flusso che può passare per un arco.

Un flusso è una funzione , indicata con o , soggetta ai due vincoli seguenti:

  1. (vincolo di capacità: il flusso passante in un arco non può essere maggiore della capacità dello stesso);
  2. (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 , dove è la sorgente di . Esso rappresenta l'ammontare di flusso che parte dalla sorgente per arrivare al pozzo.

Il problema del flusso massimo è quello di massimizzare , ovvero, di instradare quanto più flusso possibile da a .

Soluzioni[modifica | modifica wikitesto]

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

  1. L'insieme dei nodi di è lo stesso di .
  2. Ogni arco di ha una capacità .
  3. Ogni arco di ha una capacità .

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

Metodo Complessità computazionale Note
Algoritmo di Ford-Fulkerson 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 Una specializzazione dell'algoritmo di Ford–Fulkerson sfruttante la ricerca in ampiezza.
Algoritmo di Dinic con flusso bloccante 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 e il massimo numero di fasi è . In reti con capacità unitarie l'algoritmo termina in tempo .
Algoritmo MPM (Malhotra, Pramodh-Kumar e Maheshwari)[6] Ci si riferisca alla pubblicazione originale.
Algoritmo di Dinic La struttura di albero dinamico velocizza la computazione del flusso massimo nel grafo stratificato fino a .
Algoritmo push-relabel generico
Algoritmo push-relabel con selezione FIFO
Algoritmo push-relabel con alberi dinamici
Algoritmo KRT (King, Rao, Tarjan)[7]
Algoritmo binario con flusso bloccante[8] Il valore corrisponde alla capacità massima della rete.
Algoritmo di James B Orlin + KRT (King, Rao, Tarjan)[9] L'algoritmo di Orlin trova il flusso massimo in tempo per mentre KRT risolve il problema in per .

Applicazioni[modifica | modifica wikitesto]

Note[modifica | modifica wikitesto]

  1. ^ (EN) A. Schrijver, On the history of the transportation and maximum flow problems, in Mathematical Programming, vol. 91, n. 3, 2002, pp. 437-445, DOI:10.1007/s101070100259.
  2. ^ (EN) Saul I. Gass e Arjang A. Assad, Mathematical, algorithmic and professional developments of operations research from 1951 to 1956, in An Annotated Timeline of Operations Research, International Series in Operations Research & Management Science, vol. 75, 2005, pp. 79-110, DOI:10.1007/0-387-25837-X_5, ISBN 1-4020-8116-2.
  3. ^ (EN) T. E. Harris e F. S. Ross, Fundamentals of a Method for Evaluating Rail Net Capacities (PDF), in Research Memorandum, Rand Corporation, 1955.
  4. ^ (EN) L. R. Ford e D. R. Fulkerson, Maximal flow through a network, in Canadian Journal of Mathematics, vol. 8, 1956, p. 399, DOI:10.4153/CJM-1956-045-5.
  5. ^ (EN) Ford, L.R., Jr.; Fulkerson, D.R., Flows in Networks, Princeton University Press (1962).
  6. ^ (EN) V.M. Malhotra, M.Pramodh Kumar e S.N. Maheshwari, An algorithm for finding maximum flows in networks, in Information Processing Letters, vol. 7, n. 6, 1978, pp. 277-278, DOI:10.1016/0020-0190(78)90016-9.
  7. ^ (EN) V. King, S. Rao e R. Tarjan, A Faster Deterministic Maximum Flow Algorithm, in Journal of Algorithms, vol. 17, n. 3, 1994, pp. 447-474, DOI:10.1006/jagm.1994.1044.
  8. ^ (EN) A. V. Goldberg e S. Rao, Beyond the flow decomposition barrier, in Journal of the ACM, vol. 45, n. 5, 1998, p. 783, DOI:10.1145/290179.290181.
  9. ^ (EN) James B. Orlin, Max flows in O(nm) time, or better, in STOC '13 Proceedings of the forty-fifth annual ACM symposium on Theory of computing, 2013, pp. 765-774, DOI:10.1145/2488608.2488705.

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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