談?wù)動邢驁D的一個應(yīng)用
—— 求網(wǎng)絡(luò)最大流問題

周承貴

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

談?wù)動邢驁D的一個應(yīng)用
—— 求網(wǎng)絡(luò)最大流問題

周承貴

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

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

源匯；增廣鏈；最大流

1 引言

圖論中討論的網(wǎng)絡(luò)最大流是一類應(yīng)用十分廣泛的問題。比如現(xiàn)實生活中的交通系統(tǒng)中有人流、車流、貨物流等；金融系統(tǒng)中有現(xiàn)金流；通信系統(tǒng)中有信息流；供水（油）系統(tǒng)中有水（油）流等，解決這類系統(tǒng)優(yōu)化問題有十分重要的現(xiàn)實意義。

2 基本概念

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

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

所謂最大流問題就是在網(wǎng)絡(luò)圖中尋找流量最大的可行流。

3 網(wǎng)絡(luò)最大流的求法

3.1 增廣鏈的定義

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

求網(wǎng)絡(luò)最大流的思想是通過標(biāo)號法尋找從源到匯是否有流量可以增加的增廣鏈，如有增廣鏈，則調(diào)整增廣鏈上弧的流量，來獲取流值的更大流，直到找到最大流為止。

3.2 具體操作方法

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

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

（4）對新可行流重復(fù)（1）到（3）過程，當(dāng)再也找不到新的增廣鏈時，此時源的流出量（或匯的流入量）就是網(wǎng)絡(luò)圖的最大流。

4 應(yīng)用舉例

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

圖1

圖2

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

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

圖3

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

5 結(jié)束語

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

1 趙樹利.計算機數(shù)學(xué)基礎(chǔ)［M］.北京：高等教育出版社，2004.2 2 云連英.工程應(yīng)用數(shù)學(xué)［M］.北京：高等教育出版社，2000.4 3 張忠志.離散數(shù)學(xué)［M］.北京：高等教育出版社，2004.2

4 CEAC信息化培訓(xùn)認(rèn)證管理辦公室編.計算機數(shù)學(xué)基礎(chǔ)［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