劉義磊，黃素果

畢節(jié)學院資源與安全工程學院，貴州畢節(jié) 551700

0 引言

在實際生產(chǎn)、生活過程當中，真實網(wǎng)絡(luò)的結(jié)點和邊都是有容量限制的，我們一般需要知道這樣一個網(wǎng)絡(luò)中源和匯這兩個指定結(jié)點之間傳輸?shù)淖畲罅髁浚⒄页鲞_到這個最大流量的具體辦法，網(wǎng)絡(luò)最大流問題就是描個問題的數(shù)學模型。

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

1 最大流算法

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

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

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

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

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

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

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

1.2 Push-relabel algorithms算法

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

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

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

3）然后讓source node往其它所有緊挨的node里都注入特定的流量，然后計算剩余網(wǎng)絡(luò)的狀態(tài)；

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

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

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

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

2 求解最大流的通路法在礦井通風系統(tǒng)中的應(yīng)用

已知某礦井的通風網(wǎng)絡(luò)結(jié)構(gòu)簡圖G如圖1所示，對其進行加虛分支，形成新的網(wǎng)絡(luò)結(jié)構(gòu)圖G′，如圖2所示，在通風網(wǎng)絡(luò)系統(tǒng)的改造過程中，確定最大流是必不可少的，在此應(yīng)用通路法來求解該網(wǎng)絡(luò)的最大流。通路法確定通風網(wǎng)絡(luò)最大流為以下四個步驟：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 某礦通風網(wǎng)絡(luò)簡圖

圖2 加虛分支后的通風網(wǎng)絡(luò)圖

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

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

3 結(jié)論

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

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

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

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

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