主題
Search

網路流

網路流問題考慮一個圖 G，其中包含一組源點 S 和匯點 T，並且每條邊都分配了容量（權重）。問題是要找到從 S 到 T 的最大流量，同時遵守給定的邊容量。網路流問題可以在 O(n^3) 時間內解決（Edmonds 和 Karp 1972；Skiena 1990，第 237 頁）。它在 Wolfram 語言 中實現為FindMaximumFlow[g, source, sink].

另請參閱

增廣路徑, 最大流最小割定理, 網路

使用 探索

參考文獻

Edmonds, J. and Karp, R. M. "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems." J. ACM 19, 248-264, 1972.Even, S. and Tarjan, R. E. "Network Flow and Testing Graph Connectivity." SIAM J. Comput. 4, 507-518, 1975.Ford, L. R. and Fulkerson, D. R. Flows in Networks. Princeton, NJ: Princeton University Press, 1962.Gonery, R. E. and Hu, T. C. "Multiterminal Network Flows." J. SIAM 9, 551-570, 1961.Orlin, J. B. "A Faster Strongly Polynomial Minimum Cost Flow Algorithm." Proc. 20th ACM Symposium Theorem of Computing. pp. 377-387, 1988.Skiena, S. "Network Flow." §6.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 237-239, 1990.Skiena, S. S. "Network Flow." §8.4.9 in The Algorithm Design Manual. New York: Springer-Verlag, pp. 297-300, 1997.Tarjan, R. E. Data Structures and Network Algorithms. Philadelphia, PA: SIAM Press, 1983.

在 中被引用

網路流

請引用為

Weisstein, Eric W. “網路流。” 來自 —— 資源。 https://mathworld.tw/NetworkFlow.html

主題分類