最大流算法在礦井通風系統中的應用

劉義磊，黃素果

畢節學院資源與安全工程學院，貴州畢節 551700

0 引言

在實際生產、生活過程當中，真實網絡的結點和邊都是有容量限制的，我們一般需要知道這樣一個網絡中源和匯這兩個指定結點之間傳輸的最大流量，并找出達到這個最大流量的具體辦法，網絡最大流問題就是描個問題的數學模型。

礦井通風系統設計所需的一個重要的主要參數就是礦井通風所需最小風量，它也是對各種分風算法進行選擇的前提條件。礦井通風系統形成之后，礦井最小總風量就是不受分風算法影響的一個定值。但是由于風速太大時會導致粉塵增多等現象，針對不同的巷道先頂了不同的風速上限，因此對于通風系統來說其最大風量和最小風量都是有限制的，最終都歸結到網絡的極值流問題，其中重要的也就是最大流問題。

1 最大流算法

最大流問題是網絡流理論的核心問題之一，它牽涉到特殊的線性規劃，是一個經典的優化組合問題。通俗地講，最大流問題就是在網絡當中以最快捷的辦法把特定物質從某處輸送至另一處。該問題源于美蘇之間的爭端，美國想準確獲得有關蘇聯能夠最快的獲得國際補給的鐵路線路，以及如何最大限度地切斷其補給線路。最終通過調查計算發現這兩個問題相互聯系，不可分割對待，并且最大流問題得到合理處理的同時，也解決了最徹底地切斷蘇聯補給的最小割問題。

最大流問題發展到今天，學者們建立了一系列較為完善的理論，也尋找出了許多的算法。如Ford-Fulkson算法、Dinic算法、Gold-berg推進和重標號算法以及Gold-berg和Rao的二分長度阻塞流算法等等，這些經典算法及相關技術對網絡最大流問題的研究起到了非常重要的推動作用。

1.1 Ford-Fulkson增載軌算法和Dinic阻塞流算法

Ford-Fulkson算法第一次將組合優化的方法應用到最大流問題。初次將剩余網絡、增載軌等概念引入，把最大流問題的求解進行歸納總結，成為從一個初值開始不斷遞增直到求得最優解的迭代過程，打下了用組合方法進行求解的基礎。

Ford-Fulkerson Algorithm可以概括為：Residual networks augmenting paths and cuts三大思想，最重要的一點的是利用Residue network的論點求解出maximum flow。

將最大流問題的求解過程當做一個迭代的過程，每次迭代都是為了使網絡中的流量增大，那么如果想最大限度地減少計算量，那么只有想法設法將迭代次數減少，并且降低每一步的復雜程度。如果想將迭代次數降低，那么需要每次迭代時都要使網絡中的流量遞增程度盡可能的增大。比較方便的是找出網絡中的一部分作為子圖，然后求出該子圖中所需的最大流，最終在剩余的網絡里重復這一步驟。

Dinic算法首次將距離這一定義延伸到求解過程中來，它在網絡中定義出了分層網絡，這是一個非常獨特的無環網絡，分層網絡就是僅保留距離相鄰的結點之間的邊，然后在定義出的分層網絡中進一步求阻塞流。

1.2 Push-relabel algorithms算法

Push-relabel algorithms算法的主要思路是在網絡中，流出的量可能比流進的量還要多，有流量進來就放其流入，流不出去時再做處理。Push-relabel algorithms算法的流程如下：

1）設定一個函數f(x)，它是一個高度函數，表示的意義是x點的高度，作為一個中間參考坐標，只有比其高的點能往比其低的點流動；

2）程序運行時，設source node的高度是x(node數)，除此之外的點的高度都是0，這樣source node就足以流往其它任何一個點；

3）然后讓source node往其它所有緊挨的node里都注入特定的流量，然后計算剩余網絡的狀態；

4）對每一個active node都重復Relabel的動作，如果在其中某個node有流體存在，但是和它所相鄰的所有node的f(x)都高于它，這時要為它的f(x)增加一條可以流出去的支路；

5）然后對每一個能夠做Push動作的node重復Push；

6）反復執行Relabe和Push的工作，直到無任何active node，最后從source node流出的總的流量就是最大流量。

Push-relabel algorithms提供了最大流的新的思路，并且它的效率也非常的高，復雜度僅僅為O(V2E)，比一般的算法占有一定的優勢。

2 求解最大流的通路法在礦井通風系統中的應用

已知某礦井的通風網絡結構簡圖G如圖1所示，對其進行加虛分支，形成新的網絡結構圖G′，如圖2所示，在通風網絡系統的改造過程中，確定最大流是必不可少的，在此應用通路法來求解該網絡的最大流。通路法確定通風網絡最大流為以下四個步驟：1）增加虛分支；2）求通路；3）最小可增廣通路；4）通路增廣

圖1中各分支的容量和容許流為 ：e1（12，0），e2（10，0），e3（20，0），e4（9，0），e5（8，0），e6（8，0），e7（7，0），e8（18，0）。

對于圖2，a=9，b=10。所加虛分支的容量依次為：

c91=c12=12，c95=c56=12，c4，10=c34=20，c8，10=c78=18。

可確定出圖2的通路為：

P1={e9，e1，e2，e3，e11}，P2={e9，e1，e2，e5，e8，e12}，

P3={e10，e6，e4，e2，e3，e11}，P4={e10，e6，e7，e8，e12}，

P5={e10，e6，e4，e2，e5，e8，e12}。

最小可增廣通路為P4。

圖1 某礦通風網絡簡圖

圖2 加虛分支后的通風網絡圖

對P4中的各分支進行增廣，增廣后P4中各分支的容量和容許流量分別為 ：e10（8，7），e6（8，7），e7（7，7），e8（18，7），e12（18，7）。然后繼續搜索最小可增廣通路，并進行通路增廣，直到找不到可增廣通路為止，隨后依次進行增廣的通路為P3，P2和P1，通路增廣過程完成后，用下式計算最大流，

至于如何使風流按照一定的方式流動，可采用增阻法、降阻法或增能法進行風量調節。

3 結論

1）介紹了最大流問題的研究歷史，總結了這段時期內人們建立的最大流問題較為完善的理論和算法，并分析了經典算法及相關技術對網絡最大流問題的研究起到的推動作用；2）針對求解最大流在礦井通風系統中的應用實例進行分析，該實例用通路法求解最大流，只需進行4次增廣，通過與其他方法的對比可知該方法具有運算量小的優點，能夠在復雜的網絡問題中極大地減小運算量，從而減小出錯概率、減輕工作負擔。

[1]張憲超，陳國良.小容量網絡上的最大流算法[J].計算機研究與發展，2001(2).

[2]沈金龍，喻錦華.計算機通信網最大流算法的分析和實現[J].南京郵電學院學報，1994(4).

[3]凌永發，王杰，李正明.網絡最大流問題典型組合算法研究[J].云南民族大學學報：自然科學版，2006(3).

[4]解季萍，楊超，謝剛.網絡最大流問題和典型阻塞流算法研究[J].西南林學院學報，2005(2).