徐光聯(lián),孫文新
鶴壁職業(yè)技術(shù)學(xué)院 電子信息工程學(xué)院,河南 鶴壁 458030
節(jié)點(diǎn)環(huán)流網(wǎng)絡(luò)中的最大流算法
徐光聯(lián),孫文新
鶴壁職業(yè)技術(shù)學(xué)院 電子信息工程學(xué)院,河南 鶴壁 458030
為了求出節(jié)點(diǎn)有容量并有存儲(chǔ)功能的網(wǎng)絡(luò)中的最大流,提出使用改進(jìn)的帶有節(jié)點(diǎn)環(huán)流的網(wǎng)絡(luò)模型。在改進(jìn)的網(wǎng)絡(luò)模型中,網(wǎng)絡(luò)節(jié)點(diǎn)改由新的結(jié)構(gòu)代替,即節(jié)點(diǎn)分為入點(diǎn)和出點(diǎn),增加中轉(zhuǎn)弧和節(jié)點(diǎn)環(huán)。提出了進(jìn)出節(jié)點(diǎn)的配平算法,使用了改進(jìn)的流量守恒約束,通過虛擬源、虛擬匯進(jìn)行配平,使用最大流算法求出由節(jié)點(diǎn)環(huán)流調(diào)節(jié)過的最大流。在配平算法中,遇到入流容量小于出流容量,要判斷節(jié)點(diǎn)環(huán)流量的大小;遇到入流容量大于出流容量,要判斷節(jié)點(diǎn)環(huán)流的殘容量大小。算法應(yīng)用于流的分配或流的匯聚。
網(wǎng)絡(luò)流;節(jié)點(diǎn)環(huán)流;最大流算法;流量守恒
網(wǎng)絡(luò)最大流是運(yùn)籌學(xué)重要的內(nèi)容,一般是在連通無環(huán)弧的s-t網(wǎng)絡(luò)[1]中應(yīng)用的,如運(yùn)輸電網(wǎng)、油氣管線、通信網(wǎng)絡(luò)等。常用的組合算法有標(biāo)號(hào)法、Dinic法、推拉流算法等;常用的線性規(guī)劃算法有網(wǎng)絡(luò)單純形法、網(wǎng)絡(luò)內(nèi)點(diǎn)法[2-3]等。網(wǎng)絡(luò)中弧有容量,但是節(jié)點(diǎn)無容量。為了解決節(jié)點(diǎn)有容量的問題,可以使用節(jié)點(diǎn)分裂法[4-5],通過把有容量的節(jié)點(diǎn)分裂成2個(gè)點(diǎn)并在其中加入一條邊,從而將節(jié)點(diǎn)和邊都為有容量的問題轉(zhuǎn)化為僅邊有容量的問題,但這種轉(zhuǎn)化可能破壞了網(wǎng)絡(luò)的平面性。文獻(xiàn)[6-7]分別給出了在不破壞網(wǎng)絡(luò)的平面性條件下,將節(jié)點(diǎn)和邊都有容量約束的無向平面網(wǎng)絡(luò)和有向平面網(wǎng)絡(luò)最大流問題轉(zhuǎn)化為僅有邊容量約束的網(wǎng)絡(luò)最大流問題,然后采用網(wǎng)絡(luò)最大流算法求解,但這些轉(zhuǎn)化方法復(fù)雜,實(shí)現(xiàn)有一定困難。文獻(xiàn)[2-3]引入人工智能中搜索的方法,根據(jù)網(wǎng)絡(luò)可行流分解定理,在組合算法基礎(chǔ)上,提出了網(wǎng)絡(luò)最大流新算法。上述方法都保持了網(wǎng)絡(luò)中節(jié)點(diǎn)之間的平等性。這里給出一種擴(kuò)展的帶有節(jié)點(diǎn)環(huán)流的NIO網(wǎng)絡(luò),一方面能夠繼承原來的理論,另一方面可以更簡單地處理節(jié)點(diǎn)有容量的實(shí)際問題。
1.1 N網(wǎng)絡(luò)模型
常用的N網(wǎng)絡(luò)流模型[1]定義如下。
定義1設(shè)N是一個(gè)單源單匯網(wǎng)絡(luò),N=(V,A,s,t,C),是一個(gè)有向簡單圖。其中V是節(jié)點(diǎn)集合,A是有向邊(弧)集合,s∈V是源點(diǎn),入度為0,t∈V是匯點(diǎn),出度為0。C是定義在弧集A上的一個(gè)非負(fù)容量函數(shù)。如果節(jié)點(diǎn)vi、vj∈V,稱弧(vi,vj)中vj為弧頭,vi為弧尾;弧上的容量記為C(vi,vj),弧上的流量記為f(vi,vj)。稱這種帶源點(diǎn)和匯點(diǎn)的網(wǎng)絡(luò)為容量網(wǎng)絡(luò)。
為了敘述方便,符號(hào)C(vi,vj)可簡記為C(i,j)或Cij,流量f(vi,vj)記為f(i,j)或fij;源點(diǎn)s和匯點(diǎn)t為vs、vt的簡寫;V–{s,t}中的節(jié)點(diǎn)稱為中轉(zhuǎn)點(diǎn)。給定一個(gè)網(wǎng)絡(luò)N,約定V中的節(jié)點(diǎn)個(gè)數(shù)為|V| = n,弧集A中弧的個(gè)數(shù)為|A|=m。
定義2如果流f定義在網(wǎng)絡(luò)N上[4-5],滿足下述條件:
1.2 擴(kuò)展的NIO網(wǎng)絡(luò)及其節(jié)點(diǎn)構(gòu)造
在一個(gè)有向圖D=(V,A)中,如果D中有重弧,節(jié)點(diǎn)有容量和自環(huán),則不符合網(wǎng)絡(luò)N的要求,通過一個(gè)轉(zhuǎn)換把其構(gòu)造成為一個(gè)有向簡單圖,轉(zhuǎn)換原則如下。
1)重弧合并原則。如果 vi、vj∈V,且vi到vj有l(wèi)條有向(重)邊,則可合并為一條弧,記為aij。
2)節(jié)點(diǎn)分開原則。節(jié)點(diǎn)有容量也有自環(huán),如圖1所示。
圖1 N網(wǎng)絡(luò)節(jié)點(diǎn)
自環(huán)記為aii=(vi,vi),環(huán)有容量,記為Cii環(huán),環(huán)有流量,記為fii環(huán),節(jié)點(diǎn)的進(jìn)出容量(進(jìn)出流量)記為Cii0(fii0)。把節(jié)點(diǎn)分開為入點(diǎn)vi?和出點(diǎn)vi+時(shí),如圖2所示,從入點(diǎn)vi?到出點(diǎn)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é)點(diǎn)分開后,定向連接弧與環(huán)的正向重弧同向。根據(jù)重弧合并原則,設(shè)環(huán)的正向弧上的環(huán)流容量(流量)為Cii+(fii+);環(huán)的反向弧的環(huán)流容量(流量)為Cii-(fii-),正、反向弧上的環(huán)流容量(流量)數(shù)值大小相等而方向相反,因?yàn)镃ii0(fii0)表示定向連接弧的容量(流量)。根據(jù)轉(zhuǎn)換原則中的重弧合并規(guī)定,同向弧流合并,稱為中轉(zhuǎn)弧,記為Ci(fi),其中Ci=Cii++Cii0,fi=fii++fii0。合并后的結(jié)果如圖3所示。
圖2 網(wǎng)絡(luò)節(jié)點(diǎn)分開示意
圖3 NIO網(wǎng)絡(luò)節(jié)點(diǎn)
NIO節(jié)點(diǎn)構(gòu)造:原來的節(jié)點(diǎn)v被v+、v?這2個(gè)點(diǎn)替代,產(chǎn)生了2條新弧,所有的入弧連接到vi?,所有出弧從vi+向外連接,則入點(diǎn)vi-有唯一的一個(gè)出弧指向出點(diǎn)vi+,即中轉(zhuǎn)弧。如果節(jié)點(diǎn)沒有自環(huán),則定義節(jié)點(diǎn)自環(huán)的容量(流量)記為0(0)。若有多個(gè)自環(huán),則合并成一個(gè)。顯然,有以下定理:
定理1 根據(jù)重弧合并和節(jié)點(diǎn)分開原則,所構(gòu)造出的有向圖是一個(gè)有向簡單圖[8]。
定義3 設(shè) N=(V,A,s,t,C)是定義1中的網(wǎng)絡(luò),要表示N中節(jié)點(diǎn)的容量和環(huán)流,根據(jù)節(jié)點(diǎn)分開原則構(gòu)造擴(kuò)展網(wǎng)絡(luò)[8]:NIO=(V?,V+,A,s?,s+,t?,t+,C),其中V?、V+是V中節(jié)點(diǎn)分開后的入點(diǎn)集和出點(diǎn)集,A是擴(kuò)展后的有向邊(弧)集,s?、s+是源點(diǎn)s分開后的源點(diǎn)入點(diǎn)和源點(diǎn)出點(diǎn),t?、t+是匯點(diǎn)t分開后匯點(diǎn)的入點(diǎn)和匯點(diǎn)的出點(diǎn),C是擴(kuò)展后有向邊(弧)上的容量函數(shù)。
擴(kuò)展網(wǎng)絡(luò)矩陣:NIO網(wǎng)絡(luò)對(duì)應(yīng)的鄰接矩陣記為MIO,其元素是入點(diǎn)和出點(diǎn)組成的弧集,其子域可由弧上的容量(流量)等權(quán)值元素組成。
MIO中的弧集由集合:(V?∪V+∪{s?,s+,t?,t+})×(V?∪V+∪{s?,s+,t?,t+})中的元素表示。NIO網(wǎng)絡(luò)中,所有可能出現(xiàn)的弧所表示的矩陣MIO如下所示。
注1:MIO中的弧(vs-,vi-),(vi+,vt+), i=1,2,…,n,在正常情況下,它不存在,在特殊情況下使用,例如虛擬源或虛擬匯。2:MIO中的弧為0表示弧不存在,因而不使用。
1.3 節(jié)點(diǎn)的虛擬源與虛擬匯
根據(jù)可行流的守恒條件,對(duì)于除源點(diǎn)和匯點(diǎn)外的中間點(diǎn)vi,流入和流出應(yīng)該相等而產(chǎn)生平衡,但實(shí)際上有很多情況下是不平衡的,為了平衡流量[8-9],使用以下定義:
定義4 在NIO網(wǎng)絡(luò)中,增加從源點(diǎn)入點(diǎn)到中間點(diǎn)入點(diǎn)的輔助弧和流:f(vs?,vi?)稱為虛擬源,C(vs?,vi?)稱為虛擬源容量;增加從中間點(diǎn)出點(diǎn)到匯點(diǎn)出點(diǎn)輔助弧和流:f(vi+,vt+)稱為虛擬匯,C(vi+,vt+)稱為虛擬匯容量。
2.1 NIO網(wǎng)絡(luò)中節(jié)點(diǎn)環(huán)流
節(jié)點(diǎn)環(huán)流定義背景:如果網(wǎng)絡(luò)表示河流網(wǎng),則河流為弧,水庫為節(jié)點(diǎn),水庫中的水為節(jié)點(diǎn)環(huán)流,水庫的容量為節(jié)點(diǎn)環(huán)流容量,洪水來臨時(shí)水庫可滯流,干旱時(shí)期水庫可放水澆田,水庫起調(diào)節(jié)作用。由此背景,定義節(jié)點(diǎn)環(huán)流參與最大流算法的容量調(diào)節(jié)算法。N網(wǎng)絡(luò)要求可行流遵守流量守恒約束,而在改進(jìn)的NIO網(wǎng)絡(luò)中,使用改進(jìn)的流量守恒約束,也就是配平算法。根據(jù)入流、出流平衡分為3種情況,即:入流容量小于出流容量(又分為環(huán)流足、環(huán)流不足2種情況);出入流平衡;入流容量大于出流容量(又分為環(huán)流容量足、環(huán)流容量不足2種情況)。在這個(gè)算法中,節(jié)點(diǎn)的中轉(zhuǎn)流容量設(shè)為足夠大,即不起約束作用(另文討論起約束作用),主要起作用的是環(huán)流容量、環(huán)流量。
2.2 節(jié)點(diǎn)入流容量小于出流容量的配平算法
這意味著環(huán)流儲(chǔ)備用盡。簡記為:“入流小環(huán)流不足”。
3)配平后的出流容量maxC(i, j)配平后:
4)容量配平計(jì)算過后,再計(jì)算最大流。
如果網(wǎng)絡(luò)中沿s-t方向的弧容量是遞增的,則節(jié)點(diǎn)環(huán)流不斷流出,成為一種匯聚流,用公式(1)~(3)。
2.3 節(jié)點(diǎn)入流容量等于出流容量
入流容量等于出流容量,則已經(jīng)配平,簡記“出入流已平衡”,這是一般的可行流情形。
2.4 節(jié)點(diǎn)入流容量大于出流容量
對(duì)于節(jié)點(diǎn)vi,設(shè)虛擬匯容量為C( vi+,vt+),虛擬匯為f( vi+,vt+),又設(shè)殘容量[9]為Cre(vi, vi),且Cre(vi, vi)=C( vi, vi)?f( vi, vi)。
如果網(wǎng)絡(luò)中沿s-t方向的弧容量是遞減的,則節(jié)點(diǎn)環(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)流容量設(shè)為100,即在本例中,源與匯的能力設(shè)為足夠大。
分析:例1中,沿s-t方向的弧容量有增加的,有減少的,這是一個(gè)綜合性調(diào)劑的算例。
算法:圖5中的節(jié)點(diǎn)環(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。計(jì)算后的節(jié)點(diǎn)環(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é)點(diǎn)環(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é)點(diǎn)環(huán)流2,作為源,流出2,剩下2-2=0。
圖4 N網(wǎng)絡(luò)入流容量小于出流容量
圖5 NIO網(wǎng)絡(luò)入流容量小于出流容量
例3:圖6(上行)屬于“入流大環(huán)容足”型,節(jié)點(diǎn)環(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é)點(diǎn)環(huán)流為6作為源,滯流為3,故環(huán)流為6+3=9<10=環(huán)容量10。
圖6 N網(wǎng)絡(luò)入流容量大于出流容量
圖7 NIO網(wǎng)絡(luò)入流容量大于出流容量
例4:圖6(下行)中“入流大環(huán)容不足”的情形為節(jié)點(diǎn)環(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é)點(diǎn)環(huán)流8,作為匯,滯流2,故環(huán)流為8+2=10,達(dá)到環(huán)流最大值,不能再增加。
例5:如圖8所示N網(wǎng)絡(luò)圖,節(jié)點(diǎn)有環(huán)流,數(shù)據(jù)見圖。通過環(huán)流調(diào)劑,求其最大流。
圖8 N網(wǎng)絡(luò)圖例
圖9 NIO網(wǎng)絡(luò)圖例題
圖8是N網(wǎng)絡(luò)下的圖,所對(duì)應(yīng)的NIO網(wǎng)絡(luò)圖如圖9所示,通過虛擬源、匯配平如圖9中虛線所示。
算法:進(jìn)行容量配平。
對(duì)于v1,入流容量=13>8=出流容量,Δ=13-8=5,環(huán)流容量(流量)=12(10),殘容量為12-10=2,則Δ>2,是“入流大環(huán)容不足”型,設(shè)虛擬匯為殘容量2(2)。
對(duì)于v2,入流容量=12>4+5=出流容量,Δ=12-(4+5)=3,環(huán)流容量(流量)=8(5),殘容量為8-5=3,則Δ=3,是“入流大環(huán)容足”型,設(shè)虛擬匯為殘容量3(3)。
對(duì)于v3,入流容量=8+4<6+7=出流容量,Δ=(8+ 4)-(6+7)=-1,環(huán)流容量(流量)=10(5),環(huán)流量5>|-1|= |Δ|,是“入流小環(huán)流足”型,設(shè)虛擬源數(shù)值為|Δ|,即1(1)。
對(duì)于v4,入流容量=5<8=出流容量,Δ=5-8=-3,環(huán)流容量(流量)=2(2),環(huán)流量2<|-3|=|Δ|,是“入流小環(huán)流不足”型,設(shè)虛擬源數(shù)值為環(huán)流量,即2(2)。
對(duì)于v5,入流容量=6=出流容量,是“入流出流平衡”,不用配平。
對(duì)于v6,入流容量=7+8>6=出流容量,Δ=15-6=9,環(huán)流容量(流量)=10(5),殘容量為10-5=5,則Δ>5,是“入流大環(huán)容不足”型,設(shè)虛擬匯為殘容量5(5)。
這樣容量配平完成,虛擬的源和匯已經(jīng)標(biāo)定,這樣,用最大法計(jì)算出最大流為22。
對(duì)比節(jié)點(diǎn)環(huán)流變化如表1所示。
表1 節(jié)點(diǎn)環(huán)流變化表
討論:例5中,源12+13=25,25-1-2=22,匯=6+ 6=12,12+2+5+3=22,符合最大流算法。
帶有節(jié)點(diǎn)環(huán)流的NIO網(wǎng)絡(luò)中,其節(jié)點(diǎn)環(huán)流可以調(diào)節(jié)弧上的流量,是計(jì)算最大流的根據(jù),這是一個(gè)創(chuàng)新點(diǎn),它是從河流與水庫的關(guān)系中抽象出來的,符合實(shí)際情況。而NIO網(wǎng)絡(luò)又是N網(wǎng)絡(luò)的改進(jìn),其節(jié)點(diǎn)結(jié)構(gòu)符合現(xiàn)代流通網(wǎng)絡(luò)中節(jié)點(diǎn)的進(jìn)、出、儲(chǔ)存、轉(zhuǎn)發(fā)等應(yīng)用功能;可利用其MIO矩陣可進(jìn)行統(tǒng)計(jì)分析等計(jì)算等,因而,可作為應(yīng)用研究的課題另文討論。運(yùn)用節(jié)點(diǎn)環(huán)流容量、流量配平出來的虛擬源、虛擬匯,滿足了最大流計(jì)算的條件,而限制中轉(zhuǎn)流容量,并把節(jié)點(diǎn)環(huán)流容量、流量設(shè)為0,就成為點(diǎn)和邊有容量約束的另一種處理節(jié)點(diǎn)的有容量網(wǎng)絡(luò)。而不限制節(jié)點(diǎn)中轉(zhuǎn)容量,且把節(jié)點(diǎn)環(huán)流容量、流量設(shè)為0,就成為一般N網(wǎng)絡(luò)。NIO網(wǎng)絡(luò)能夠成為異常處理的模型[10]且應(yīng)用廣泛。所以說NIO網(wǎng)絡(luò)繼承了N網(wǎng)絡(luò)的功能,是一種改進(jìn)的性能更好的網(wǎng)絡(luò)。
[1] 高隨祥. 圖論與網(wǎng)絡(luò)流理論[M]. 北京: 高等教育出版社, 2005: 292-293.
[2] 厙向陽, 羅曉霞. 點(diǎn)和邊有容量約束的網(wǎng)絡(luò)最大流新算法[J]. 計(jì)算機(jī)應(yīng)用, 2008, 28(1): 143-145.
[3] 厙向陽. 點(diǎn)和邊有容量約束的網(wǎng)絡(luò)最小費(fèi)用最大流算法[J].計(jì)算機(jī)應(yīng)用研究, 2010,27(8): 3112-3154.
[4] 王朝瑞. 圖論[M]. 3版. 北京: 高等教育出版社, 2005: 292-293.
[5] 張先迪, 李正良. 圖論及及其應(yīng)用[M]. 北京: 高等教育出版社, 2005: 251-253.
[6] 張憲超, 萬穎瑜, 陳國良. 一類實(shí)際網(wǎng)絡(luò)中的最小截算法[J].軟件學(xué)報(bào), 2003, 14(5): 885-890.
[7] 張憲超, 江賀, 陳國良. 節(jié)點(diǎn)和邊都有容量的有向平面網(wǎng)絡(luò)中的最小截和最大流[J]. 計(jì)算機(jī)學(xué)報(bào), 2006, 29(4): 543-551.
[8] 徐光聯(lián). 節(jié)點(diǎn)有自環(huán)的網(wǎng)絡(luò)流數(shù)學(xué)模型[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 2011, 9(17): 148.
[9] J 邦詹森, G 古廷. 有向圖理論、算法用應(yīng)用[M]. 姚兵, 張輔忠, 譯. 北京: 科學(xué)出版社, 2009: 87-88.
[10] 徐光聯(lián), 尚亞蕾. 網(wǎng)絡(luò)系統(tǒng)異常處理的數(shù)學(xué)模型[J]. 科學(xué)技術(shù)與工程, 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.
河南省基礎(chǔ)與前沿技術(shù)研究項(xiàng)目(122300410258).
徐光聯(lián)(1954-), 男,副教授;孫文新(1966-), 女,副教授.
孫文新,E-mail: sunwxin126@126.com.