周承貴

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

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

周承貴

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

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

源匯；增廣鏈；最大流

1 引言

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

2 基本概念

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

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

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

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

3.1 增廣鏈的定義

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

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

3.2 具體操作方法

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

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

（4）對(duì)新可行流重復(fù)（1）到（3）過程，當(dāng)再也找不到新的增廣鏈時(shí)，此時(shí)源的流出量（或匯的流入量）就是網(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中再也找不到增廣鏈，因此這時(shí)源的流出量就是輸油管道網(wǎng)的最大流，且易求得管道的最大流為8。

5 結(jié)束語

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

1 趙樹利.計(jì)算機(jī)數(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)證管理辦公室編.計(jì)算機(jī)數(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