網路流理論(network-flows)是一種類比水流的解決問題方法，與線性規劃密切相關。網路流的理論和套用在不斷發展，出現了具有增益的流、多終端流、多商品流以及網路流的分解與合成等新課題。網路流的套用已遍及通訊、運輸、電力、工程規劃、任務分派、設備更新以及計算機輔助設計等眾多領域。
基本介紹
- 中文名：網路流理論
- 外文名：Network flow theory
- 提出者：L.R.福特和D.R.富爾克森
- 提出時間：1956年
- 套用學科：網路
- 學科：計算機技術
理論研究,理論創建,發展歷程,常用算法,套用,
理論研究
圖論中的一種理論與方法，研究網路上的一類最最佳化問題。1955年，T.E.哈里斯在研究鐵路最大通量時首先提出在一個給定的網路上尋求兩點間最大運輸量的問題。1956年，L.R.福特和D.R.富爾克森等人給出了解決這類問題的算法，從而建立了網路流理論。如果把下圖看作一個公路網，頂點v1…v6表示6座城鎮，每條邊上的權數表示兩城鎮間的公路長度。現在要問：若從起點v1將物資運送到終點v6去，應選擇那條路線才能使總運輸距離最短?這樣一類問題稱為最短路問題。如果把上圖看作一個輸油管道網，v1表示傳送點，v6表示接收點，其他點表示中轉站，各邊的權數表示該段管道的最大輸送量。現在要問怎樣安排輸油線路才能使從v1到v6的總運輸量為最大?這樣的問題稱為最大流問題。
理論創建
最大流理論是由福特和富爾克森於1956年創立的，他們指出最大流的流值等於最小割(截集)的容量這個重要的事實，並根據這一原理設計了用標號法求最大流的方法，後來又有人加以改進，使得求解最大流的方法更加豐富和完善。最大流問題的研究密切了圖論和運籌學，特別是與線性規劃的聯繫，開闢了圖論套用的新途徑。
最大流問題僅注意網路流的流通能力，沒有考慮流通的費用。實際上費用因素是很重要的。例如在交通運輸問題中，往往要求在完成運輸任務的前提下，尋求一個使總運輸費用最省的運輸方案，這就是最小費用流問題。如果只考慮單位貨物的運輸費用，那么這個問題就變成最短路問題。由此可見，最短路問題是最小費用流問題的基礎。現已有一系列求最短路的成功方法。最小費用流(或最小費用最大流)問題，可以交替使用求解最大流和最短路兩種方法，通過疊代得到解決。網路最大流問題和它的對偶問題——最小截問題，是一對經典組合最佳化問題，它們在許多工程領域和科學領域有重要的套用，是計算機科學和運籌學重要的內容，最大流問題已經有40多年的研究歷史，近年來，隨著各種網路的飛速發展，最大流問題的研究也取得了很大的進展，對最大流問題研究做了詳細的總結，並對下一步研究趨勢進行了預測。
發展歷程
目前網路流的理論和套用在不斷發展，出現了具有增益的流、多終端流、多商品流以及網路流的分解與合成等新課題。網路流的套用已遍及通訊、運輸、電力、工程規劃、任務分派、設備更新以及計算機輔助設計等眾多領域。
常用算法
1、augment path，直譯為“增廣路徑”，其思想大致如下：
原有網路為G，設有一輔助圖G'，其定義為V(G') = V(G)，E(G')初始值（也就是容量）與E(G)相同。每次操作時從Source點搜尋出一條到Sink點的路徑，然後將該路徑上所有的容量減去該路徑上容量的最小值，然後對路徑上每一條邊<u,v>添加或擴大反方向的容量，大小就是剛才減去的容量。一直到沒有路為止。此時輔助圖上的正向流就是最大流。
我們很容易覺得這個算法會陷入死循環，但事實上不是這樣的。我們只需要注意到每次網路中由Source到Sink的流都增加了，若容量都是整數，則這個算法必然會結束。
增廣路方法可以解決最大流問題，然而它有一個不可避免的缺陷，就是在極端情況下每次只能將流擴大1（假設容量、流為整數），這樣會造成性能上的很大問題，解決這個問題有一個複雜得多的算法，就是預推進算法。
2、push label，直譯為“預推進”算法。
3、壓入與重標記(Push-Relabel)算法
除了用各種方法在剩餘網路中不斷找增廣路(augmenting)的Ford-Fulkerson系的算法外，還有一種求最大流的算法被稱為壓入與重標記(Push-Relabel)算法。它的基本操作有：壓入，作用於一條邊，將邊的始點的預流儘可能多的壓向終點；重標記，作用於一個點，將它的高度（也就是label）設為所有鄰接點的高度的最小值加一。Push-Relabel系的算法普遍要比Ford-Fulkerson系的算法快，但是缺點是相對難以理解。
Relabel-to-Front使用一個鍊表保存溢出頂點，用Discharge操作不斷使溢出頂點不再溢出。Discharge的操作過程是：若找不到可被壓入的臨邊，則重標記，否則對臨邊壓入，直至點不再溢出。算法的主過程是：首先將源點出發的所有邊充滿，然後將除源和匯外的所有頂點保存在一個鍊表里，從鍊表頭開始進行Discharge，如果完成後頂點的高度有所增加，則將這個頂點置於鍊表的頭部，對下一個頂點開始Discharge。
Relabel-to-Front算法的時間複雜度是O(V^3)，還有一個叫Highest Label Preflow Push的算法複雜度據說是O(V^2*E^0.5)。我研究了一下HLPP，感覺它和Relabel-to-Front本質上沒有區別，因為Relabel-to-Front每次前移的都是高度最高的頂點，所以也相當於每次選擇最高的標號進行更新。還有一個感覺也會很好實現的算法是使用佇列維護溢出頂點，每次對pop出來的頂點discharge，出現了新的溢出頂點時入隊。
Push-Relabel類的算法有一個名為gap heuristic的最佳化，就是當存在一個整數0<k<V，沒有任何頂點滿足h[v]=k時，對所有h[v]>k的頂點v做更新，若它小於V+1就置為V+1。
