談談有向圖的一個應用
—— 求網絡最大流問題

周承貴

（桂林理工大學南寧分校，廣西 南寧 530001）

談談有向圖的一個應用
—— 求網絡最大流問題

周承貴

（桂林理工大學南寧分校，廣西 南寧 530001）

網絡最大流是一類應用很廣泛的問題，有十分重要的現實意義，本文給出一種求網絡最大流的有效快捷的算法，此算法使計算網絡最大流變得簡便且具有很強的實用性。

源匯；增廣鏈；最大流

1 引言

圖論中討論的網絡最大流是一類應用十分廣泛的問題。比如現實生活中的交通系統中有人流、車流、貨物流等；金融系統中有現金流；通信系統中有信息流；供水（油）系統中有水（油）流等，解決這類系統優化問題有十分重要的現實意義。

2 基本概念

［定義1］在有向圖（網絡圖）中，只有流出量而沒有流入量的頂點稱為源；只有流入量而沒有流出量的頂點稱為匯；既有流入量也有流出量的頂點稱為中間點；圖中每一條弧一般都標注有兩個權數（Cij，fij），其中前一個權Cij表示這條弧能容納的最大流量，稱為弧的容量，后一個權數fij表示該條弧現有的流量，稱為弧的現有流量。若現有流量等于弧的容量，則稱該弧為飽和弧，否則稱不飽和弧。特別地，若弧的現有流量為0，則稱該弧為零流弧，否則稱非零流弧。

［定義2］若在一個網絡圖中每一條弧滿足0≤fij≤Cij且中間點的流入量和流出量相等，同時源的流出量和匯的流入量也相等，則稱網絡圖存在可行流。

所謂最大流問題就是在網絡圖中尋找流量最大的可行流。

3 網絡最大流的求法

3.1 增廣鏈的定義

［定義3］設f是一個可行流，若A是從VS到Vt的一條增廣鏈，則A應該滿足以下條件：①與前進方向一致的弧（稱前向弧，記作A＋）為非飽和弧；②與前進方向相反的弧（稱后向弧，記作A－）為非零流弧。

求網絡最大流的思想是通過標號法尋找從源到匯是否有流量可以增加的增廣鏈，如有增廣鏈，則調整增廣鏈上弧的流量，來獲取流值的更大流，直到找到最大流為止。

3.2 具體操作方法

（1）對具有可行流f的網絡圖，尋找一條由VS到Vt的增廣鏈，直到找到為止；若不存在VS到Vt的增廣鏈，則最大可行流為f。

（2）在所找到的增廣鏈取調整流量值θ＝min{（cij－fij）A+，（fij）A－}。

（4）對新可行流重復（1）到（3）過程，當再也找不到新的增廣鏈時，此時源的流出量（或匯的流入量）就是網絡圖的最大流。

4 應用舉例

求如圖1所示輸油管道網從vs到vt的最大流。

圖1

圖2

略解：第一條增廣鏈為：vs→v3→v4→vt，流量調整值為：θ1＝min{2，3，2}＝2，調整流量得圖2。

第二條增廣鏈為：vs→v1→v2→vt，流量調整值為：θ2＝min{1，2，2}＝1，調整流量得圖3。

圖3

在圖3中再也找不到增廣鏈，因此這時源的流出量就是輸油管道網的最大流，且易求得管道的最大流為8。

5 結束語

使用上面的算法計算網絡最大流的問題能使問題的解決變得簡便易行，具有很強的實用性。

1 趙樹利.計算機數學基礎［M］.北京：高等教育出版社，2004.2 2 云連英.工程應用數學［M］.北京：高等教育出版社，2000.4 3 張忠志.離散數學［M］.北京：高等教育出版社，2004.2

4 CEAC信息化培訓認證管理辦公室編.計算機數學基礎［M］.北京：高等教育出版社，2006.2

Chats the Oriented Graph an Application——Asks the Network Maximal-flow Problem

Zhou Chenggui

The network maximal-flow is a kind of application very widespread question, has the very vital practical significance, this article gives one kind to ask network most the big class the effective quick algorithm, this algorithm causes the computing network to change most greatly easily, and has the very strong usability.

the source collects; augments the chain; maximal-flow

O157.5

A

1000－8136（2011）06－0133－02