徐光聯(lián)，孫文新

鶴壁職業(yè)技術學院 電子信息工程學院，河南 鶴壁 458030

節(jié)點環(huán)流網(wǎng)絡中的最大流算法

徐光聯(lián)，孫文新

鶴壁職業(yè)技術學院 電子信息工程學院，河南 鶴壁 458030

為了求出節(jié)點有容量并有存儲功能的網(wǎng)絡中的最大流，提出使用改進的帶有節(jié)點環(huán)流的網(wǎng)絡模型。在改進的網(wǎng)絡模型中，網(wǎng)絡節(jié)點改由新的結(jié)構代替，即節(jié)點分為入點和出點，增加中轉(zhuǎn)弧和節(jié)點環(huán)。提出了進出節(jié)點的配平算法，使用了改進的流量守恒約束，通過虛擬源、虛擬匯進行配平，使用最大流算法求出由節(jié)點環(huán)流調(diào)節(jié)過的最大流。在配平算法中，遇到入流容量小于出流容量，要判斷節(jié)點環(huán)流量的大??；遇到入流容量大于出流容量，要判斷節(jié)點環(huán)流的殘容量大小。算法應用于流的分配或流的匯聚。

網(wǎng)絡流；節(jié)點環(huán)流；最大流算法；流量守恒

網(wǎng)絡最大流是運籌學重要的內(nèi)容，一般是在連通無環(huán)弧的s-t網(wǎng)絡[1]中應用的，如運輸電網(wǎng)、油氣管線、通信網(wǎng)絡等。常用的組合算法有標號法、Dinic法、推拉流算法等；常用的線性規(guī)劃算法有網(wǎng)絡單純形法、網(wǎng)絡內(nèi)點法[2-3]等。網(wǎng)絡中弧有容量，但是節(jié)點無容量。為了解決節(jié)點有容量的問題，可以使用節(jié)點分裂法[4-5]，通過把有容量的節(jié)點分裂成2個點并在其中加入一條邊，從而將節(jié)點和邊都為有容量的問題轉(zhuǎn)化為僅邊有容量的問題，但這種轉(zhuǎn)化可能破壞了網(wǎng)絡的平面性。文獻[6-7]分別給出了在不破壞網(wǎng)絡的平面性條件下，將節(jié)點和邊都有容量約束的無向平面網(wǎng)絡和有向平面網(wǎng)絡最大流問題轉(zhuǎn)化為僅有邊容量約束的網(wǎng)絡最大流問題，然后采用網(wǎng)絡最大流算法求解，但這些轉(zhuǎn)化方法復雜，實現(xiàn)有一定困難。文獻[2-3]引入人工智能中搜索的方法，根據(jù)網(wǎng)絡可行流分解定理，在組合算法基礎上，提出了網(wǎng)絡最大流新算法。上述方法都保持了網(wǎng)絡中節(jié)點之間的平等性。這里給出一種擴展的帶有節(jié)點環(huán)流的NIO網(wǎng)絡，一方面能夠繼承原來的理論，另一方面可以更簡單地處理節(jié)點有容量的實際問題。

1 N網(wǎng)絡和NIO網(wǎng)絡

1.1 N網(wǎng)絡模型

常用的N網(wǎng)絡流模型[1]定義如下。

定義1設N是一個單源單匯網(wǎng)絡，N=(V，A，s，t，C)，是一個有向簡單圖。其中V是節(jié)點集合，A是有向邊(弧)集合，s∈V是源點，入度為0，t∈V是匯點，出度為0。C是定義在弧集A上的一個非負容量函數(shù)。如果節(jié)點vi、vj∈V，稱弧(vi，vj)中vj為弧頭，vi為弧尾；弧上的容量記為C(vi，vj)，弧上的流量記為f(vi，vj)。稱這種帶源點和匯點的網(wǎng)絡為容量網(wǎng)絡。

為了敘述方便，符號C(vi，vj)可簡記為C(i，j)或Cij，流量f(vi，vj)記為f(i，j)或fij；源點s和匯點t為vs、vt的簡寫；V–{s，t}中的節(jié)點稱為中轉(zhuǎn)點。給定一個網(wǎng)絡N，約定V中的節(jié)點個數(shù)為|V| = n，弧集A中弧的個數(shù)為|A|=m。

定義2如果流f定義在網(wǎng)絡N上[4-5]，滿足下述條件：

1.2 擴展的NIO網(wǎng)絡及其節(jié)點構造

在一個有向圖D=(V，A)中，如果D中有重弧，節(jié)點有容量和自環(huán)，則不符合網(wǎng)絡N的要求，通過一個轉(zhuǎn)換把其構造成為一個有向簡單圖，轉(zhuǎn)換原則如下。

1）重弧合并原則。如果 vi、vj∈V，且vi到vj有l(wèi)條有向（重）邊，則可合并為一條弧，記為aij。

2）節(jié)點分開原則。節(jié)點有容量也有自環(huán)，如圖1所示。

圖1 N網(wǎng)絡節(jié)點

自環(huán)記為aii=(vi，vi),環(huán)有容量，記為Cii環(huán)，環(huán)有流量，記為fii環(huán)，節(jié)點的進出容量（進出流量）記為Cii0(fii0)。把節(jié)點分開為入點vi?和出點vi+時，如圖2所示，從入點vi?到出點vi+有一條定向連接弧，記為弧(vi?,vi+)，其容量（流量）就是Cii0(fii0)。自環(huán)(vi，vi)上的容量（流量）是Cii(fii)，分開為2條，一條是從vi?到vi+，是環(huán)的正向重弧(vi?,vi+)，另一條是從vi+到vi?，是環(huán)的反向弧(vi+,vi?)。節(jié)點分開后，定向連接弧與環(huán)的正向重弧同向。根據(jù)重弧合并原則，設環(huán)的正向弧上的環(huán)流容量（流量）為Cii+(fii+)；環(huán)的反向弧的環(huán)流容量（流量）為Cii-(fii-)，正、反向弧上的環(huán)流容量（流量）數(shù)值大小相等而方向相反，因為Cii0(fii0)表示定向連接弧的容量（流量）。根據(jù)轉(zhuǎn)換原則中的重弧合并規(guī)定，同向弧流合并，稱為中轉(zhuǎn)弧，記為Ci(fi)，其中Ci=Cii++Cii0，fi=fii++fii0。合并后的結(jié)果如圖3所示。

圖2 網(wǎng)絡節(jié)點分開示意

圖3 NIO網(wǎng)絡節(jié)點

NIO節(jié)點構造：原來的節(jié)點v被v+、v?這2個點替代，產(chǎn)生了2條新弧，所有的入弧連接到vi?，所有出弧從vi+向外連接，則入點vi-有唯一的一個出弧指向出點vi+，即中轉(zhuǎn)弧。如果節(jié)點沒有自環(huán)，則定義節(jié)點自環(huán)的容量(流量)記為0(0)。若有多個自環(huán)，則合并成一個。顯然，有以下定理：

定理1 根據(jù)重弧合并和節(jié)點分開原則，所構造出的有向圖是一個有向簡單圖[8]。

定義3 設 N=(V，A，s，t，C)是定義1中的網(wǎng)絡，要表示N中節(jié)點的容量和環(huán)流，根據(jù)節(jié)點分開原則構造擴展網(wǎng)絡[8]：NIO=(V?,V+,A,s?,s+,t?,t+,C)，其中V?、V+是V中節(jié)點分開后的入點集和出點集，A是擴展后的有向邊(弧)集，s?、s+是源點s分開后的源點入點和源點出點，t?、t+是匯點t分開后匯點的入點和匯點的出點，C是擴展后有向邊(弧)上的容量函數(shù)。

擴展網(wǎng)絡矩陣：NIO網(wǎng)絡對應的鄰接矩陣記為MIO，其元素是入點和出點組成的弧集，其子域可由弧上的容量(流量)等權值元素組成。

MIO中的弧集由集合：(V?∪V+∪{s?,s+,t?,t+})×(V?∪V+∪{s?,s+,t?,t+})中的元素表示。NIO網(wǎng)絡中，所有可能出現(xiàn)的弧所表示的矩陣MIO如下所示。

注1：MIO中的弧(vs-,vi-),(vi+,vt+), i=1,2,…,n，在正常情況下，它不存在，在特殊情況下使用，例如虛擬源或虛擬匯。2：MIO中的弧為0表示弧不存在，因而不使用。

1.3 節(jié)點的虛擬源與虛擬匯

根據(jù)可行流的守恒條件，對于除源點和匯點外的中間點vi，流入和流出應該相等而產(chǎn)生平衡，但實際上有很多情況下是不平衡的，為了平衡流量[8-9]，使用以下定義：

定義4 在NIO網(wǎng)絡中，增加從源點入點到中間點入點的輔助弧和流：f(vs?，vi?)稱為虛擬源，C(vs?，vi?)稱為虛擬源容量；增加從中間點出點到匯點出點輔助弧和流：f(vi+，vt+)稱為虛擬匯，C(vi+，vt+)稱為虛擬匯容量。

2 容量配平與最大流

2.1 NIO網(wǎng)絡中節(jié)點環(huán)流

節(jié)點環(huán)流定義背景：如果網(wǎng)絡表示河流網(wǎng)，則河流為弧，水庫為節(jié)點，水庫中的水為節(jié)點環(huán)流，水庫的容量為節(jié)點環(huán)流容量，洪水來臨時水庫可滯流，干旱時期水庫可放水澆田，水庫起調(diào)節(jié)作用。由此背景，定義節(jié)點環(huán)流參與最大流算法的容量調(diào)節(jié)算法。N網(wǎng)絡要求可行流遵守流量守恒約束，而在改進的NIO網(wǎng)絡中，使用改進的流量守恒約束，也就是配平算法。根據(jù)入流、出流平衡分為3種情況，即：入流容量小于出流容量（又分為環(huán)流足、環(huán)流不足2種情況）；出入流平衡；入流容量大于出流容量（又分為環(huán)流容量足、環(huán)流容量不足2種情況）。在這個算法中，節(jié)點的中轉(zhuǎn)流容量設為足夠大，即不起約束作用（另文討論起約束作用），主要起作用的是環(huán)流容量、環(huán)流量。

2.2 節(jié)點入流容量小于出流容量的配平算法

這意味著環(huán)流儲備用盡。簡記為：“入流小環(huán)流不足”。

3）配平后的出流容量maxC(i, j)配平后：

4）容量配平計算過后，再計算最大流。

如果網(wǎng)絡中沿s-t方向的弧容量是遞增的，則節(jié)點環(huán)流不斷流出，成為一種匯聚流，用公式（1）～（3）。

2.3 節(jié)點入流容量等于出流容量

入流容量等于出流容量，則已經(jīng)配平，簡記“出入流已平衡”，這是一般的可行流情形。

2.4 節(jié)點入流容量大于出流容量

對于節(jié)點vi，設虛擬匯容量為C( vi+,vt+)，虛擬匯為f( vi+,vt+)，又設殘容量[9]為Cre(vi, vi)，且Cre(vi, vi)=C( vi, vi)?f( vi, vi)。

如果網(wǎng)絡中沿s-t方向的弧容量是遞減的，則節(jié)點環(huán)流不斷增加，成為一種分配流，用公式（4）～（6）。

2.5 配平算法舉例

例1：已知圖4(上行)屬于“入流小環(huán)流足”型，C( vs, v1)=5，C( v1, vt)=8，C( v1, v1)=10，且f( v1, v1)=4。其NIO圖如圖5所示。即環(huán)流容量為10，流量為4。源s和匯t的中轉(zhuǎn)流容量設為100，即在本例中，源與匯的能力設為足夠大。

分析：例1中，沿s-t方向的弧容量有增加的，有減少的，這是一個綜合性調(diào)劑的算例。

算法：圖5中的節(jié)點環(huán)流容量（流量）=10(4)，入流容量小于出流容量，即

C( vs, v1)=5＜8=C( v1, vt)，

差值

Δ=C( vs, v1)?C( v1, vt)=5?8=?3

且?3≤4=環(huán)流量。所以虛擬源容量、流量均為?3=3，記為3(3)。在配平后的圖中，最大流為8。計算后的節(jié)點環(huán)流原來是4，作為源，流出3，剩下了4-3=1。

例2：如圖4（下行），是“入流小環(huán)流不足”型：C( vs, v1)=5，C( v1, vt)=8，C( v1, v1)=10，且f( v1, v1)=2。其NIO圖如圖5所示，即環(huán)流容量為10，流量為2。

算法：圖5中的節(jié)點環(huán)流容量（流量）=10(2)，C( vs, v1)=5＜8=C( v1, vt)，差值

Δ=C( vs, v1)?C( v1, vt)=5?8=?3，

且

?3＞2=環(huán)流量；

所以虛擬源容量、流量均為環(huán)流量2，記為2(2)。在配平后的圖中，最大流為7，其中節(jié)點環(huán)流2，作為源，流出2，剩下2-2=0。

圖4 N網(wǎng)絡入流容量小于出流容量

圖5 NIO網(wǎng)絡入流容量小于出流容量

例3：圖6（上行）屬于“入流大環(huán)容足”型，節(jié)點環(huán)流容量（流量）=10(6)，其NIO圖為圖7。

算法：由于C( vs, v1)=8＞5=C( v1, vt)，差值

Δ=C( vs, v1)?C( v1, vt)=8?5=3

且

Δ=3≤4=10?6=環(huán)容量?環(huán)流量=殘容量

即

Δ≤Cre(vi, vi)=C( vi, vi)?f( vi, vi)=10?6=4則令C( vi+,vi+)=f( v1+,vt+)=Δ，所以虛擬匯容量、流量均為=3，記為3(3)。在配平后的圖中，最大流為8，其中節(jié)點環(huán)流為6作為源，滯流為3，故環(huán)流為6+3=9＜10=環(huán)容量10。

圖6 N網(wǎng)絡入流容量大于出流容量

圖7 NIO網(wǎng)絡入流容量大于出流容量

例4：圖6（下行）中“入流大環(huán)容不足”的情形為節(jié)點環(huán)流容量（流量）=10(8),其NIO圖為圖7。

算法：由于C( vs, v1)=8＞5=C( v1, vt)，差值

Δ=C( vs, v1)?C( v1, vt)=8?5=3

且

Δ=3＞2=殘容量=環(huán)容量?環(huán)流量=10?8

即

Δ=3＞Cre(vi, vi)=C( vi, vi)?f( vi, vi)=10?8=2

則令：C( vi+,vt+)=f( vi+,vt+)=Cre(vi, vi)=2。所以虛擬匯容量、流量均取殘容量，值為=2，記為2(2)。在配平后的圖中，最大流為7，其中節(jié)點環(huán)流8，作為匯，滯流2，故環(huán)流為8+2=10，達到環(huán)流最大值，不能再增加。

3 綜合應用舉例

例5：如圖8所示N網(wǎng)絡圖，節(jié)點有環(huán)流，數(shù)據(jù)見圖。通過環(huán)流調(diào)劑，求其最大流。

圖8 N網(wǎng)絡圖例

圖9 NIO網(wǎng)絡圖例題

圖8是N網(wǎng)絡下的圖，所對應的NIO網(wǎng)絡圖如圖9所示，通過虛擬源、匯配平如圖9中虛線所示。

算法：進行容量配平。

對于v1，入流容量=13＞8=出流容量，Δ=13-8=5,環(huán)流容量（流量）=12(10)，殘容量為12-10=2，則Δ＞2,是“入流大環(huán)容不足”型，設虛擬匯為殘容量2(2)。

對于v2，入流容量=12＞4+5=出流容量，Δ=12-(4+5)=3，環(huán)流容量（流量）=8(5)，殘容量為8-5=3，則Δ=3,是“入流大環(huán)容足”型，設虛擬匯為殘容量3(3)。

對于v3，入流容量=8+4＜6+7=出流容量，Δ=(8+ 4)-(6+7)=-1,環(huán)流容量（流量）=10(5)，環(huán)流量5＞|-1|= |Δ|,是“入流小環(huán)流足”型，設虛擬源數(shù)值為|Δ|，即1(1)。

對于v4，入流容量=5＜8=出流容量，Δ=5-8=-3，環(huán)流容量（流量）=2(2)，環(huán)流量2＜|-3|=|Δ|,是“入流小環(huán)流不足”型，設虛擬源數(shù)值為環(huán)流量，即2(2)。

對于v5，入流容量=6=出流容量，是“入流出流平衡”，不用配平。

對于v6，入流容量=7+8＞6=出流容量，Δ=15-6=9,環(huán)流容量（流量）=10(5)，殘容量為10-5=5，則Δ＞5,是“入流大環(huán)容不足”型，設虛擬匯為殘容量5(5)。

這樣容量配平完成，虛擬的源和匯已經(jīng)標定，這樣，用最大法計算出最大流為22。

對比節(jié)點環(huán)流變化如表1所示。

表1 節(jié)點環(huán)流變化表

討論：例5中，源12+13=25，25-1-2=22，匯=6+ 6=12，12+2+5+3=22，符合最大流算法。

4 結(jié)束語

帶有節(jié)點環(huán)流的NIO網(wǎng)絡中，其節(jié)點環(huán)流可以調(diào)節(jié)弧上的流量，是計算最大流的根據(jù)，這是一個創(chuàng)新點，它是從河流與水庫的關系中抽象出來的，符合實際情況。而NIO網(wǎng)絡又是N網(wǎng)絡的改進，其節(jié)點結(jié)構符合現(xiàn)代流通網(wǎng)絡中節(jié)點的進、出、儲存、轉(zhuǎn)發(fā)等應用功能；可利用其MIO矩陣可進行統(tǒng)計分析等計算等，因而，可作為應用研究的課題另文討論。運用節(jié)點環(huán)流容量、流量配平出來的虛擬源、虛擬匯，滿足了最大流計算的條件，而限制中轉(zhuǎn)流容量，并把節(jié)點環(huán)流容量、流量設為0，就成為點和邊有容量約束的另一種處理節(jié)點的有容量網(wǎng)絡。而不限制節(jié)點中轉(zhuǎn)容量，且把節(jié)點環(huán)流容量、流量設為0，就成為一般N網(wǎng)絡。NIO網(wǎng)絡能夠成為異常處理的模型[10]且應用廣泛。所以說NIO網(wǎng)絡繼承了N網(wǎng)絡的功能，是一種改進的性能更好的網(wǎng)絡。

[1] 高隨祥. 圖論與網(wǎng)絡流理論[M]. 北京: 高等教育出版社, 2005: 292-293.

[2] 厙向陽, 羅曉霞. 點和邊有容量約束的網(wǎng)絡最大流新算法[J]. 計算機應用, 2008, 28(1): 143-145.

[3] 厙向陽. 點和邊有容量約束的網(wǎng)絡最小費用最大流算法[J].計算機應用研究, 2010,27(8): 3112-3154.

[4] 王朝瑞. 圖論[M]. 3版. 北京: 高等教育出版社, 2005: 292-293.

[5] 張先迪, 李正良. 圖論及及其應用[M]. 北京: 高等教育出版社, 2005: 251-253.

[6] 張憲超, 萬穎瑜, 陳國良. 一類實際網(wǎng)絡中的最小截算法[J].軟件學報, 2003, 14(5): 885-890．

[7] 張憲超, 江賀, 陳國良. 節(jié)點和邊都有容量的有向平面網(wǎng)絡中的最小截和最大流[J]. 計算機學報, 2006, 29(4): 543-551．

[8] 徐光聯(lián). 節(jié)點有自環(huán)的網(wǎng)絡流數(shù)學模型[J]. 數(shù)學的實踐與認識, 2011, 9(17): 148.

[9] J 邦詹森, G 古廷. 有向圖理論、算法用應用[M]. 姚兵, 張輔忠, 譯. 北京: 科學出版社, 2009: 87-88.

[10] 徐光聯(lián), 尚亞蕾. 網(wǎng)絡系統(tǒng)異常處理的數(shù)學模型[J]. 科學技術與工程, 2010, 5(14): 123-124.

Maximum flow algorithm in network with node loop

XU Guanglian, SUN Wenxin

School of Electronic Engineering, Hebi College of Vocation and Technology, Hebi 458030, China

In order to search maximum flow in the network with node capacity and node memory function, a network model with the node loop is proposed. The node of the network is substituted by the new structure of the node in the improved network, which is divided into enter-flow point and out-flow point, and added with the transfer arc and node loop. A balancing algorithm is proposed for entering and leaving the node and the improved flow conservation constraints are used; using the virtual source and virtual sink of balance, the maximum flow regulated by the node loop is calculated. In the balancing algorithm, when the enter-flow capacity is less than the out-flow capacity, the node ring flow size should be determined; otherwise, the residual capacity of the node loop should be determined. The algorithm is applied to the distribution or convergence of flow.

network flow, node loop flow; maximum flow algorithm; flow conservation

O157

A

1009-671X（2014）01-0048-06

10.3969/j.issn.1009-671X.201306011

2013-06-08.

河南省基礎與前沿技術研究項目（122300410258）.

徐光聯(lián)(1954-), 男，副教授;孫文新(1966-), 女，副教授.

孫文新，E-mail: sunwxin126@126.com.