節點環流網絡中的最大流算法

徐光聯，孫文新

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

節點環流網絡中的最大流算法

徐光聯，孫文新

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

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

網絡流；節點環流；最大流算法；流量守恒

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

1 N網絡和NIO網絡

1.1 N網絡模型

常用的N網絡流模型[1]定義如下。

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

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

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

1.2 擴展的NIO網絡及其節點構造

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

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

2）節點分開原則。節點有容量也有自環，如圖1所示。

圖1 N網絡節點

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

圖2 網絡節點分開示意

圖3 NIO網絡節點

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

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

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

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

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

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

1.3 節點的虛擬源與虛擬匯

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

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

2 容量配平與最大流

2.1 NIO網絡中節點環流

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

2.2 節點入流容量小于出流容量的配平算法

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

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

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

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

2.3 節點入流容量等于出流容量

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

2.4 節點入流容量大于出流容量

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

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

2.5 配平算法舉例

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

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

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

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

差值

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

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

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

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

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

且

?3＞2=環流量；

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

圖4 N網絡入流容量小于出流容量

圖5 NIO網絡入流容量小于出流容量

例3：圖6（上行）屬于“入流大環容足”型，節點環流容量（流量）=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=環容量?環流量=殘容量

即

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

圖6 N網絡入流容量大于出流容量

圖7 NIO網絡入流容量大于出流容量

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

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

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

且

Δ=3＞2=殘容量=環容量?環流量=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，其中節點環流8，作為匯，滯流2，故環流為8+2=10，達到環流最大值，不能再增加。

3 綜合應用舉例

例5：如圖8所示N網絡圖，節點有環流，數據見圖。通過環流調劑，求其最大流。

圖8 N網絡圖例

圖9 NIO網絡圖例題

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

算法：進行容量配平。

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

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

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

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

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

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

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

對比節點環流變化如表1所示。

表1 節點環流變化表

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

4 結束語

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

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

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

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

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

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

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

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

[8] 徐光聯. 節點有自環的網絡流數學模型[J]. 數學的實踐與認識, 2011, 9(17): 148.

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

[10] 徐光聯, 尚亞蕾. 網絡系統異常處理的數學模型[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）.

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

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