最大流問題

在最佳化理論中，最大流問題（英語：Maximum flow problem）涉及到在一個單源點、單匯點的網絡流中找到一條最大的流。

一個網絡最大流的例子。源點為 s，匯點為 t。數字表示流和容量。

最大流問題可以被看作是一個更複雜的網絡流問題（迴圈問題，circulation problem）的特殊情況。s-t流（從源點s到匯點t）的最大值等於s-t割的最小容量，這被稱為最大流最小割定理。

歷史

最大流問題最早是在1954年由泰德·哈里斯（英語：Ted Harris (mathematician)）和F·S·羅斯（F. S. Ross）通過一個蘇聯鐵路的交通流量的簡化模型提出的。^[1][2][3] 1955年，小萊斯特·倫道夫·福特和德爾伯特·雷·富爾克森建立了第一個已知的演算法，福特-富爾克森演算法。^[4][5]

多年來，最大流問題的各種改進演算法被發現，例如傑克·埃德蒙茲（英語：Jack Edmonds）、理查德·卡普和葉菲姆·迪尼茨（英語：Yefim Dinitz）的最短增廣路演算法；迪尼茨的阻塞流演算法；安德魯·V·戈德堡（英語：Andrew V. Goldberg）和羅伯特·塔揚的Push-Relabel演算法；戈德堡和Rao的binary阻塞流演算法；Christiano、Kelner和亞歷山大·馬德瑞（Aleksander Madry）的電流演算法；Spielman發現一個最大流近似最佳解，但僅適用於無向圖。^[6][7]

定義

一個網絡流，源點為 s，匯點為 t。邊上的數字為容量。

設${\displaystyle N=(V,E)}$為一個網絡，其中${\displaystyle s}$和${\displaystyle t}$分別是${\displaystyle N}$的源點和匯點（${\displaystyle s,t\in V}$）。

一個邊的容量為對映${\displaystyle c:E\to \mathbb {R} ^{+}}$，記為${\displaystyle c_{uv}}$或${\displaystyle c(u,v)}$。它表示可以通過一條邊的流量的最大值。

一個流為一個對映${\displaystyle f:E\to \mathbb {R} ^{+}}$，記為${\displaystyle f_{uv}}$或${\displaystyle f(u,v)}$，遵循下面兩個限制：

1. 對於每個${\displaystyle (u,v)\in E}$，有${\displaystyle f_{uv}\leq c_{uv}}$（即容量限制：一個邊的流量不能超過它的容量）；
2. 對於每個${\displaystyle v\in V\setminus \{s,t\}}$，有${\displaystyle \sum _{u:(u,v)\in E}f_{uv}=\sum _{u:(v,u)\in E}f_{vu}}$（即流的保留：流入一個節點的流的總和必須等於流出這個節點的流的總和，源點和匯點除外）。

流量定義為 ${\displaystyle |f|=\sum _{v:(s,v)\in E}f_{sv}}$，其中${\displaystyle s}$為${\displaystyle N}$的源點，它表示從源點到匯點的流的數量。

最大流問題就是最大化${\displaystyle |f|}$，即從${\displaystyle s}$點到${\displaystyle t}$點儘可能規劃最大的流量。

解法

演算法	複雜度	描述
線性規劃
福特-富爾克森演算法	O(E max| f |)
埃德蒙茲-卡普演算法	O(VE2)	福特-富爾克森演算法的特例，使用廣度優先搜尋尋找增廣路徑.
迪尼茨阻塞流演算法	O(V2E)
MPM (Malhotra, Pramodh-Kumar and Maheshwari)演算法[8]	O(V3)	只適用於無環圖。參考 Original Paper.
Dinic演算法	O(VE log(V))
push-relabel maximum flow演算法	O(V2E)
Push-relabel演算法，使用FIFO vertex selection rule	O(V3)
Push-relabel演算法，使用 dynamic trees	${\displaystyle O\left(VE\log {\frac {V^{2}}{E}}\right)}$
KRT (King, Rao, Tarjan)演算法[9]	${\displaystyle O(EV\log _{\frac {E}{V\log V}}V)}$
Binary阻塞流演算法[10]	${\displaystyle O\left(E\cdot \min(V^{\frac {2}{3}},{\sqrt {E}})\cdot \log {\frac {V^{2}}{E}}\log {U}\right)}$
James B Orlin's + KRT (King, Rao, Tarjan)演算法[11]	${\displaystyle O(VE)}$	Orlin's algorithm （頁面存檔備份，存於互聯網檔案館） solves max-flow in O(VE) time for ${\displaystyle E\leq O(V^{{16 \over 15}-\epsilon })}$ while KRT solves it in O(VE) for ${\displaystyle E>V^{1+\epsilon }}$.

參考文獻

1. Schrijver, A. On the history of the transportation and maximum flow problems. Mathematical Programming. 2002, 91 (3): 437–445. doi:10.1007/s101070100259.
2. Gass, Saul I.; Assad, Arjang A. Mathematical, algorithmic and professional developments of operations research from 1951 to 1956. An Annotated Timeline of Operations Research. International Series in Operations Research & Management Science 75. 2005: 79–110. ISBN 1-4020-8116-2. doi:10.1007/0-387-25837-X_5.
3. Harris, T. E.; Ross, F. S. Fundamentals of a Method for Evaluating Rail Net Capacities (PDF). Research Memorandum (Rand Corporation). 1955 [2017-03-07]. （原始內容存檔 (PDF)於2017-02-17）.
4. Ford, L. R.; Fulkerson, D. R. Maximal flow through a network. Canadian Journal of Mathematics. 1956, 8: 399. doi:10.4153/CJM-1956-045-5.
5. Ford, L.R., Jr.; Fulkerson, D.R., Flows in Networks, Princeton University Press (1962).
6. Kelner, J. A.; Lee, Y. T.; Orecchia, L.; Sidford, A. An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (PDF). 2014: 217. ISBN 978-1-61197-338-9. arXiv:1304.2338 . doi:10.1137/1.9781611973402.16. （原始內容 (PDF)存檔於2016-03-03）.
7. Knight, Helen. New algorithm can dramatically streamline solutions to the ‘max flow’ problem. MIT News. 7 January 2014 [8 January 2014]. （原始內容存檔於2014-02-26）.
8. Malhotra, V.M.; Kumar, M.Pramodh; Maheshwari, S.N. An ${\displaystyle O(|V|^{3})}$ algorithm for finding maximum flows in networks. Information Processing Letters. 1978, 7 (6): 277–278. doi:10.1016/0020-0190(78)90016-9.
9. King, V.; Rao, S.; Tarjan, R. A Faster Deterministic Maximum Flow Algorithm. Journal of Algorithms. 1994, 17 (3): 447–474. doi:10.1006/jagm.1994.1044.
10. Goldberg, A. V.; Rao, S. Beyond the flow decomposition barrier. ACM期刊. 1998, 45 (5): 783. doi:10.1145/290179.290181.
11. Orlin, James B. Max flows in O(nm) time, or better. STOC '13 Proceedings of the forty-fifth annual ACM symposium on Theory of computing. 2013: 765–774. doi:10.1145/2488608.2488705.