網路流

出自 MBA智库百科(https://wiki.mbalib.com/)

網路流（Network flow）

　　在圖論中，網路流是指在一個每條邊都有容量（capacity）的有向圖分配流，使一條邊的流量不會超過它的容量。通常在運籌學中，有向圖稱為網路。頂點稱為節點（node）而邊稱為弧（arc）。一道流必須匹配一個結點的進出的流量相同的限制，除非這是一個源點（source）──有較多向外的流，或是一個匯點（sink）──有較多向內的流。一個網路可以用來模擬道路系統的交通量、管中的液體、電路中的電流或類似一些東西在一個結點的網路中游動的任何事物。

　　將一連串的水管繪畫成一個網路。每條水管有一特定的闊度，因此只可以保持一特定的水流量。當任何水管匯合，流入匯流點的總水量必須等於流出的水量，否則我們會很快地缺水，或者我們會團積水。我們有一個作為源點的入水口，和一個作為匯點的出水口。一道流便是一條由源點到匯點而使從出水口流出的總水量一致的可能路徑。直觀地，一個網路的總流量是水從出口流出的速率。

　　流可以關於在交通網路上的人或物質，或電力分配系統上的電力。對於任何這樣的實物網路，進入任何中途結點的流需要等於離開那結點的流。Bollobás以基爾霍夫電流定律描繪這限制的特性，同時較遲的作者（即Chartrand）提及它在某些守恆方程的普遍化。

　　在生態學中也可找到流網路的應用：當考慮在食物網中不同組織之間養料及能量的流，流網路便自然地產生。與這些網路有聯繫的數學問題和那些液體流或交通流網路中所產生的難題有很大分別。由Robert Ulanowicz及其他人發展的生態系統網路分析領域包含使用資訊理論及熱力學的概念去研究這些網路隨時間的演變。

　　利用網路流去找出最大流是最簡單及最普通的問題，它提供了在一指定的圖中由源點到匯點的最大可能總流量。還有很多其它問題可以利用最大流演算法去解決，假設它們可以適當地塑造成流網路的模樣，例如二部圖匹配（Bipartite Matching）、任務分配問題（Assignment Problem）和運輸問題（Transportation Problem）。

　　在多物網路流問題（Multi-commodity Flow Problem）中，可以有多個源點和匯點，和各種各樣的由指定源點發送到指定匯點的“物品（Commodities）”。例如這可能是不同的工廠生產的各種各樣的貨物經由“同一”運輸網路運送到不同的消費者手上。