用木桶原理改進最大流算法

李苑輝

(三亞航空旅游職業學院 數學教研室，海南 三亞 572000)

用木桶原理改進最大流算法

李苑輝

(三亞航空旅游職業學院 數學教研室，海南 三亞 572000)

傳統求網絡最大流算法需要反復將網絡圖進行標號和增流，存在步驟繁復、計算量大的問題。本文提出了一種尋找最大流的改進標號法。此方法通過尋找網絡中可能的最小割進行標號、分配流量，可以簡化計算過程，提高運算效率。

最大流問題;Ford-FuIkerson標號法;木桶原理;最小割

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

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

1 預備知識

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

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

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

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

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

2 理論基礎

Ford-FuIkerson標號法的實施步驟如下:首先給網絡一任意可行流(最簡單是給零流)，然后交替進行標號過程和增流過程，直至不存在流量可調鏈為止，這時就得到了最大流。

Ford-FuIkerson標號法存在的針對性差、步驟繁復、計算量大的問題。本文擬應用“木桶原理”，尋找最大流問題的改進方法;將此方法應用到求網絡最大流的計算中，可以簡化計算過程，提高運算效率。

木桶原理:由多塊木板構成的水桶，決定其盛水量的多少的關鍵因素不是其最長的板塊，而是其最短的板塊。

Ford-FuIkerson標號法的基本思路是:判斷網絡中是否存在增廣鏈，并設法將它們找出來。

筆者經過分析發現，結合木桶原理，我們可以將網絡圖劃分為若干個區域，每個區域包含若干條弧，每條弧可同時屬于幾個區域。每個區域都是從發點s到收點t的必經之路，即，若將某個區域的弧全截斷，整個網絡將斷流。計算出每個區域所含弧的容量之和Ck，則minCk即為整個網絡的“短板”，整個網絡的最大流不超過minCk.接著找到經過該“短板”中每條弧的最大流量的路。

據此，就得到了Ford-FuIkerson標號法在求網絡最大流中的改進算法:

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

第二步，給擁有最小容量和的區域K的每條弧“分配”流量。找出到收點的最小層數，選擇有最大容量的路，找出相應的自起點s到收點t的路。

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

3 實例演示

下面我們給出本文算法的一些應用。

例1 求下列網絡的最大流見圖1，圖2，各弧旁邊數字為cij

圖1 求網絡的最大流

圖2 將網絡劃分為四個區域

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

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

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

圖4 區域(2)飽和后的網絡圖

3.此時區域(2)中的各條弧均已飽和，網絡G如下(各弧旁邊數字為(cij，fij)):

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

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

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

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

圖5 S列t的流量圖

［1］杜紅.應用運籌學［M］.杭州:浙江大學出版社，2010.

［2］張宏斌.運籌學方法及其應用［M］.北京:清華大學出版社，2008.

［3］姚遠，宋振明.運籌學基礎教程［M］.開封:河南大學出版社，2008.

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

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

責任編輯:鐘 聲

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-)，男，廣東梅州人，助教，主要從事運籌學方面的研究。