用木桶原理改進(jìn)最大流算法

李苑輝

(三亞航空旅游職業(yè)學(xué)院 數(shù)學(xué)教研室，海南 三亞 572000)

用木桶原理改進(jìn)最大流算法

李苑輝

(三亞航空旅游職業(yè)學(xué)院 數(shù)學(xué)教研室，海南 三亞 572000)

傳統(tǒng)求網(wǎng)絡(luò)最大流算法需要反復(fù)將網(wǎng)絡(luò)圖進(jìn)行標(biāo)號(hào)和增流，存在步驟繁復(fù)、計(jì)算量大的問題。本文提出了一種尋找最大流的改進(jìn)標(biāo)號(hào)法。此方法通過尋找網(wǎng)絡(luò)中可能的最小割進(jìn)行標(biāo)號(hào)、分配流量，可以簡(jiǎn)化計(jì)算過程，提高運(yùn)算效率。

最大流問題;Ford-FuIkerson標(biāo)號(hào)法;木桶原理;最小割

研究網(wǎng)絡(luò)的流量是很有意義的，例如交通系統(tǒng)中的車流、金融系統(tǒng)中的現(xiàn)金流、控制系統(tǒng)中的信息流、供水系統(tǒng)中的水流等，人們往往比較關(guān)心在既定網(wǎng)絡(luò)中能通過的最大流量以及網(wǎng)絡(luò)中各條邊的流量，以此判斷設(shè)備的充分利用程度。這就提出了最大流問題。

在運(yùn)籌學(xué)中通常用Ford-FuIkerson標(biāo)號(hào)法在給定可行流圖中求解出最大流量圖。此方法應(yīng)用非常之科學(xué)、嚴(yán)謹(jǐn)，但是涉及到較多的圖論專業(yè)知識(shí)，非專業(yè)人員應(yīng)用起來有一定的難度。本文擬對(duì)最大流問題的算法作出一些簡(jiǎn)化處理，以使得改進(jìn)后的方法更易使用。基本思路是:盡快找到一條從起點(diǎn)到收點(diǎn)的路徑，獲得通過這條路徑的最大流量;如此不斷重復(fù)，直到剩余流量的弧已不能組成新的從起點(diǎn)到收點(diǎn)的路徑為止;這時(shí)獲得的最大流量之和便是我們要求得到的通過網(wǎng)絡(luò)的最大流量。為減少路徑選擇方面的隨意性，特將管理學(xué)上的“木桶原理”應(yīng)用其中，以期簡(jiǎn)化尋找最優(yōu)解的過程。

1 預(yù)備知識(shí)

定義1 最大流問題:給出一個(gè)帶有一個(gè)起點(diǎn)(稱作源)和一個(gè)收點(diǎn)(稱作匯)以及若干中間點(diǎn)(轉(zhuǎn)運(yùn)點(diǎn))的連通網(wǎng)絡(luò)，其每條弧的權(quán)為通過這條弧的容量，在不超過每條弧容量的前提下，求從起點(diǎn)到收點(diǎn)的最大流量。

定義2 網(wǎng)絡(luò)中弧的容量與流量:網(wǎng)絡(luò)中某條弧(i，j)的最大通過能力成為它的容量，記為cij，cij≥0;而其流量是指通過它的實(shí)際流量，記為fij。

定義3 飽和弧與非飽和弧:當(dāng)弧上的流量等于容量，即fij=cij時(shí)，稱為飽和弧;當(dāng)弧上的流量小于容量，即 0 μfij＜cij時(shí)，稱為非飽和弧。

定義4 割及割容量:在容量網(wǎng)絡(luò)G=(V，A)中，若頂點(diǎn)集V被分為兩個(gè)非空集合S和T，使得起點(diǎn)s∈S，收點(diǎn) t∈T，且有 S∪T=V，S∩T=?，則將弧集(S，T)稱為分離 s和 t的一個(gè)割集。割集(S，T)中所有弧的容量之和稱為該割集的容量，簡(jiǎn)稱割容量或割量。在容量網(wǎng)絡(luò)G=(V，A)的所有割集中，割容量最小的割集稱為最小割。

定義5 最大流最小割定理:在任一容量網(wǎng)絡(luò)G=(V，A)中，從起點(diǎn)s到收點(diǎn)t的最大流量，等于分離s和t的最小割容量。

2 理論基礎(chǔ)

Ford-FuIkerson標(biāo)號(hào)法的實(shí)施步驟如下:首先給網(wǎng)絡(luò)一任意可行流(最簡(jiǎn)單是給零流)，然后交替進(jìn)行標(biāo)號(hào)過程和增流過程，直至不存在流量可調(diào)鏈為止，這時(shí)就得到了最大流。

Ford-FuIkerson標(biāo)號(hào)法存在的針對(duì)性差、步驟繁復(fù)、計(jì)算量大的問題。本文擬應(yīng)用“木桶原理”，尋找最大流問題的改進(jìn)方法;將此方法應(yīng)用到求網(wǎng)絡(luò)最大流的計(jì)算中，可以簡(jiǎn)化計(jì)算過程，提高運(yùn)算效率。

木桶原理:由多塊木板構(gòu)成的水桶，決定其盛水量的多少的關(guān)鍵因素不是其最長(zhǎng)的板塊，而是其最短的板塊。

Ford-FuIkerson標(biāo)號(hào)法的基本思路是:判斷網(wǎng)絡(luò)中是否存在增廣鏈，并設(shè)法將它們找出來。

筆者經(jīng)過分析發(fā)現(xiàn)，結(jié)合木桶原理，我們可以將網(wǎng)絡(luò)圖劃分為若干個(gè)區(qū)域，每個(gè)區(qū)域包含若干條弧，每條弧可同時(shí)屬于幾個(gè)區(qū)域。每個(gè)區(qū)域都是從發(fā)點(diǎn)s到收點(diǎn)t的必經(jīng)之路，即，若將某個(gè)區(qū)域的弧全截?cái)啵麄€(gè)網(wǎng)絡(luò)將斷流。計(jì)算出每個(gè)區(qū)域所含弧的容量之和Ck，則minCk即為整個(gè)網(wǎng)絡(luò)的“短板”，整個(gè)網(wǎng)絡(luò)的最大流不超過minCk.接著找到經(jīng)過該“短板”中每條弧的最大流量的路。

據(jù)此，就得到了Ford-FuIkerson標(biāo)號(hào)法在求網(wǎng)絡(luò)最大流中的改進(jìn)算法:

第一步，將連接起點(diǎn)的所有弧和連接收點(diǎn)的所有弧分別劃為一個(gè)區(qū)域，中間點(diǎn)之間的弧再視情況劃分出若干個(gè)區(qū)域;一條弧可同時(shí)屬于幾個(gè)區(qū)域;計(jì)算出每個(gè)區(qū)域的最小容量和Ck(k=1，2，3…)，求出minCk.由木桶原理可知，整個(gè)網(wǎng)絡(luò)圖的最大流不超過minCk。

第二步，給擁有最小容量和的區(qū)域K的每條弧“分配”流量。找出到收點(diǎn)的最小層數(shù)，選擇有最大容量的路，找出相應(yīng)的自起點(diǎn)s到收點(diǎn)t的路。

第三步，若區(qū)域K中的每條弧都已飽和，則此時(shí)網(wǎng)絡(luò)G的最大流即為Ck.若區(qū)域K中有非飽和弧(i，j)，檢查當(dāng)前的非飽和弧，反向追蹤，依需要作出調(diào)整，直至與弧(i，j)相連接的弧飽和，此時(shí)亦得到網(wǎng)絡(luò)G的最大流。

3 實(shí)例演示

下面我們給出本文算法的一些應(yīng)用。

例1 求下列網(wǎng)絡(luò)的最大流見圖1，圖2，各弧旁邊數(shù)字為cij

圖1 求網(wǎng)絡(luò)的最大流

圖2 將網(wǎng)絡(luò)劃分為四個(gè)區(qū)域

1.將網(wǎng)絡(luò)劃分為四個(gè)區(qū)域，算出每個(gè)區(qū)域的容量之和Ck(k=1，2，3，4.).由minCk=23可知區(qū)域(2)的容量最小。由木桶原理可知，s到t的最大流不超過23。

2.從區(qū)域(2)入手，給其每條弧分配流量。發(fā)點(diǎn)s到收點(diǎn)t的最小層數(shù)為3，故可選擇有最大容量的路μ1={s，2，4，t}，其最大流量為6，此時(shí)弧(2，4)飽和。接下來分別給弧(1，5)、弧(1，3)、弧(2，3)分配流量，方法類似。s到t的各條路的流量圖如圖3所示。

圖3 給區(qū)域(2)每條弧分配流量

圖4 區(qū)域(2)飽和后的網(wǎng)絡(luò)圖

3.此時(shí)區(qū)域(2)中的各條弧均已飽和，網(wǎng)絡(luò)G如下(各弧旁邊數(shù)字為(cij，fij)):

如圖4可知s到t的最大流即為區(qū)域(2)的容量之和23，因此可得s到t的流量圖如圖5，(以下各弧旁邊數(shù)字為fij):

本文使用的“木桶原理”求最大流，可視為最大流最小割定理的一個(gè)推廣或視為求最小割容量的弱化條件。一般而言，求最小割容量過程繁瑣、計(jì)算量大(割的數(shù)量最多可達(dá)2n個(gè)，其中n為中間節(jié)點(diǎn)的個(gè)數(shù))，如本文圖1中割的數(shù)量即達(dá)15個(gè)。本文不直接窮舉全部不同割及其容量來確定最大流，而是先比較幾個(gè)割容量的大小(即本文中的分區(qū)域比較容量和的大小)，給容量和較

小的割中的每條弧分配流量，以此來求出流量圖。這樣就避免了原有算法的諸多麻煩，達(dá)到了簡(jiǎn)化計(jì)算的效果。

事實(shí)上，用木桶原理找到網(wǎng)絡(luò)的最大流的同時(shí)，我們也得到了一個(gè)最小割(即區(qū)域(2))。而最小割的容量決定了網(wǎng)絡(luò)總的通過能力。因此，要想提高網(wǎng)絡(luò)的通過能力，首先應(yīng)該改善最小割中每條弧的容量和輸送狀況。另一方面，一旦最小割中弧的通過能力被降低，那么整個(gè)網(wǎng)絡(luò)的總輸送能力也必然會(huì)減少。

圖5 S列t的流量圖

［1］杜紅.應(yīng)用運(yùn)籌學(xué)［M］.杭州:浙江大學(xué)出版社，2010.

［2］張宏斌.運(yùn)籌學(xué)方法及其應(yīng)用［M］.北京:清華大學(xué)出版社，2008.

［3］姚遠(yuǎn)，宋振明.運(yùn)籌學(xué)基礎(chǔ)教程［M］.開封:河南大學(xué)出版社，2008.

［4］夏冬晴.最大流算法的改良［J］.邵陽學(xué)院學(xué)報(bào):自然科學(xué)版，2004(6):12－13.

［5］謝凡榮.求解運(yùn)輸問題的一個(gè)算法［J］.運(yùn)籌與管理，2002，11(3):69－73.

責(zé)任編輯:鐘 聲

The improvement of maximum flow algorithm based on Barrel Principle

LI Yuan-hui
(Mathematics Department，Sanya Aviation and Tourism College，Sanya 572000，China)

The traditional algorithm for maximum flow in network needs repeatedly labeling and flow-increasing for network diagrams，showing problems of complicated steps and large computation.This paper presents an improved labeling method for searching maximum flow，which labels and distributes flow by finding the possible minimum cut，it can simplify the calculation process and improve operational efficiency.

maximum flow problem;Ford-FuIkerson Labeling Method;Barrel Principle;minimum cut

O157.5

A

1009－3907(2011)06－0047－03

2010-03-10

李苑輝(1982-)，男，廣東梅州人，助教，主要從事運(yùn)籌學(xué)方面的研究。