串并有向圖的判定算法及應(yīng)用實(shí)例

王琪

(江西制造職業(yè)技術(shù)學(xué)院 江西 南昌 330095)

單機(jī)排序問(wèn)題已經(jīng)有大量的研究，何欣怡[1]研究了帶拒絕的若干單機(jī)排序問(wèn)題，包括工件帶有截止日期約束、帶有退化和不可用區(qū)間和機(jī)器有不可用區(qū)間且工件不可恢復(fù)等相關(guān)子問(wèn)題。種貝貝[2]針對(duì)兩個(gè)代理所考慮的3 個(gè)不同目標(biāo)函數(shù)組合，分別討論了它們的KS 公平定價(jià)問(wèn)題。栗蘋(píng)[3]研究總提前損失問(wèn)題，包括工件將根據(jù)其工期前完成部分工件的持續(xù)時(shí)間進(jìn)行處罰。其他相關(guān)研究進(jìn)展包括基于凸優(yōu)化方法[4]、基于工件排列順序與公共窗口的位置優(yōu)化的方法[5]、基于劃分接受工件集和拒絕工件的方法[6]。此外，作為該問(wèn)題的重要解決思路，串并有向圖經(jīng)常作為約束條件使用，其應(yīng)用范圍十分廣泛。例如：成龍等人[7]提出的關(guān)于1｜sp_Graph｜∑Wj(1-e-rcj)問(wèn)題的最優(yōu)算法；閆楊等人[8]研究的1｜sp_Graph｜WjCj問(wèn)題；高文軍等人[9]討論工件間具有串并有向圖約束的preempt-repeat 模型，則是用LAWLER EL[10]提出的任務(wù)合并和由底向上搜索分解樹(shù)的方法求解；陳昊[11]、張大宇[12]、黃玉[13]、萬(wàn)龍[14]這些學(xué)者在相關(guān)研究中也均涉及串并有向圖。這些問(wèn)題中工件間的優(yōu)先約束均為串并有向圖，但是串并有向圖僅僅是作為既定的前提約束條件，并沒(méi)有對(duì)這個(gè)約束條件進(jìn)行判定。而據(jù)筆者所知，在現(xiàn)有研究中，只給出了串并有向圖的定義或者其分解樹(shù)的特征，根據(jù)這些定義或者特征只能提取出串并有向圖的必要條件，均不能成為判斷一個(gè)有向圖是否為串并有向圖的充分條件。所以，研究串并有向圖的判定算法問(wèn)題具有重要意義。

1 相關(guān)定義

為了解決串并有向圖的判定問(wèn)題，首先需要明確與串并有向圖相關(guān)的定義。相關(guān)定義如下文所述。

定義1[15]一個(gè)有向圖G是一個(gè)有序二元組，記為G=(N，A)，其中N={}n1，n2，…nn稱(chēng)為G的點(diǎn)集合，A={aij}稱(chēng)為G的弧集合，aij是一個(gè)有序二元數(shù)組(ni，nj)，記為aij=(ni，nj)，稱(chēng)aij從ni連向nj，ni稱(chēng)為nj的前繼，nj稱(chēng)為ni的后繼。

定義2[15]對(duì)有向圖G的每條弧如果均用一條邊代替它，得到一個(gè)無(wú)向圖，這個(gè)無(wú)向圖稱(chēng)為G的基本圖。

定義3 某個(gè)點(diǎn)前繼的數(shù)量表示該點(diǎn)的入度，后繼的數(shù)量表示為該點(diǎn)的出度，刪除某個(gè)點(diǎn)包括刪除該點(diǎn)和與該點(diǎn)相連的邊。

定義4[15]兩個(gè)端點(diǎn)重合為一點(diǎn)的邊稱(chēng)為環(huán)，兩個(gè)端點(diǎn)都相同的邊稱(chēng)為重邊，一個(gè)有向圖，如果它既沒(méi)有環(huán)，也沒(méi)有重邊，則稱(chēng)為簡(jiǎn)單有向圖。

定義5[15]在有向圖G中，一個(gè)點(diǎn)和弧的交錯(cuò)序列(ni，aij，nj，…n1)稱(chēng)為G中由ni到n1的一條有向路，記為(ni，n1)有向路。G中一條至少包含一條弧，并且ni=n1的(ni，n1)有向路，稱(chēng)為G的一條有向回路。

定義6[15]對(duì)有向圖G，定義一個(gè)n×n階的鄰接矩陣A=(aij)，其中A稱(chēng)為G的鄰接矩陣。

圖的表示方法很多，采用不同的表示方法，可獲得圖的不同的時(shí)空性能[16]。用鄰接矩陣表示圖的優(yōu)點(diǎn)是易于計(jì)算機(jī)存儲(chǔ)。

定義7[15]圖G中若存在一條由ni到nj的路。則稱(chēng)ni和nj是連通的，如果G中任意兩點(diǎn)都是連通的，則稱(chēng)G是連通的。設(shè)N'?N，E′?E，如果對(duì)E′中任意一條邊eij={ni，nj}，都有ni∈N′和nj∈N′，則稱(chēng)G′=(N′，E′)是G的一個(gè)子圖。G的極大連通子圖稱(chēng)為G的一個(gè)連通分支。

本文中定義的有向圖的連通，指的是如果其基本圖是連通的，則表示該串并有向圖連通，串并有向圖中的連通分支對(duì)應(yīng)其基本圖相同點(diǎn)和邊的連通分支。

定義8[10]可遷的串并有向圖按如下遞歸方式定義。

（1）僅包含一個(gè)頂點(diǎn)的有向圖是可遷的串并有向圖。

（2）若G1=(N1，A1)和G2=()N2，A2是可遷的串并有向圖，且N1∩N2=?，則G=G1×G2=(N1∪N2，A1∪A2∪N1×N2)是可遷的串并有向圖，稱(chēng)G是由G1和G2串行合成的。

（3）若G1=(N1，A1)和G2=(N2，A2)是可遷的串并有向圖，且N1∩N2=?，則G=G1×G2=(N1∪N2，A1∪A2)是可遷的串并有向圖，稱(chēng)G是由G1和G2并行合成的。

（4）通過(guò)有限步應(yīng)用（1）（2）（3）得到的有向圖是可遷的串并有向圖。

串并有向圖的主要特征是在一個(gè)串并有向圖中，所有結(jié)點(diǎn)均為串行或并行關(guān)系。串行關(guān)系的結(jié)點(diǎn)有先后順序，并行關(guān)系的結(jié)點(diǎn)為平行關(guān)系，沒(méi)有先后順序。通過(guò)串并有向圖的定義可知在串并有向圖中不存在回路。

定義9[15]一個(gè)樹(shù)是一個(gè)連通且無(wú)回路的圖。

定義10 二叉樹(shù)的遞歸定義。

二叉樹(shù)(Binary Tree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集，它或者是空集（n=0），或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱(chēng)作這個(gè)根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。

樹(shù)是圖的特例。一個(gè)串并有向圖G可以分解為一個(gè)二叉樹(shù)Tr，Tr 稱(chēng)為圖G的分解樹(shù)。如圖1 所示，圖1（a）表示一個(gè)串并有向圖，圖1（b）表示其對(duì)應(yīng)的分解樹(shù)。Tr的葉子結(jié)點(diǎn)對(duì)應(yīng)G的頂點(diǎn)，中間結(jié)點(diǎn)用S或P表示。S表示其左右兩個(gè)子樹(shù)之間是串行關(guān)系，并且左子樹(shù)優(yōu)先于右子樹(shù)，P表示左右兩個(gè)子樹(shù)之間是并行關(guān)系。

圖1 一個(gè)串并有向圖及其分解樹(shù)

本文提出的串并有向圖的判定算法，其主要思想是對(duì)一個(gè)給定的有向圖的所有連通分支逐一進(jìn)行遞歸分解，若所有連通分支都滿(mǎn)足相關(guān)條件，則判定該有向圖是串并有向圖。通過(guò)該算法能夠準(zhǔn)確判斷一個(gè)有向圖是否為串并有向圖。

2 算法描述

串并有向圖判定算法的主要過(guò)程：令G1,G2,…,Gn是有向圖G（非空?qǐng)D）的n個(gè)連通分支。對(duì)Gi(i∈1，…，n)，找到其所有入度為0 的結(jié)點(diǎn)，定義為結(jié)點(diǎn)集K，如果K為空集，則說(shuō)明Gi中包含有向回路，判定Gi不是串并有向圖，如果K不是空集，刪除K中的所有結(jié)點(diǎn)后再找到新的有向圖中所有入度為0 的結(jié)點(diǎn)，定義為結(jié)點(diǎn)集T。如果T為空集，則說(shuō)明Gi為單節(jié)點(diǎn)，根據(jù)定義8 的（1）說(shuō)明Gi是串并有向圖，如果T不為空集，則判斷圖G中是否使結(jié)點(diǎn)集K中每一個(gè)點(diǎn)ni與結(jié)點(diǎn)集T中的任意一點(diǎn)ni都存在由ni指向nj的有向弧相連。如果否，則Gi中不是串并有向圖，如果是，則在Gi中中刪去點(diǎn)集K定義為新的圖Gi中，重復(fù)以上過(guò)程，進(jìn)行遞歸判斷。若G1,G2,…,Gn均是串并有向圖，則最終判定圖G為串并有向圖。

Aa是G的連通分支Ga的n×n階鄰接矩陣，對(duì)圖G，運(yùn)行以下算法H。

步驟1：DefineG1.G2…Gp?G；

步驟2：func(Gq)｛Tq=1；

步驟4：IfK≠? ThenTq=0；

步驟5：ElseGq′:=Gq-K；

步驟7：IfT≠? Then

步驟9：If func(Gq) =0 ThenTq=0 End End End End

步驟10：ReturnTa；｝

步驟11：tg=1；

步驟12：for ｛q=1;q≤p;q++｝

步驟13：｛If func(Gq)=0 Then tg=0 and Break；End｝

步驟14：If tg=1 then ReturnGis sp-Graph

步驟15：Else ReturnGis not sp-Graph End

3 算法的證明

定理1 算法H解決了串并有向圖判定的問(wèn)題。

證明 對(duì)于任意有向圖G=(N,A)的任意一個(gè)連通分支Ga，Ga的分解樹(shù)為T(mén)a，假設(shè){n1，n2，…，nk}表Ga中入度為0 的點(diǎn)集K，若K=?，則說(shuō)明Ga中存在有向回路，判定Ga不是串并有向圖；若K≠?，｛nk+1…nt｝表示Ga刪去K中的點(diǎn)之后新的入度為0的點(diǎn)集T，若T=?，則說(shuō)明Ga是單節(jié)點(diǎn)，判定Ga是串并有向圖，若T≠?，則在Ga中，只有ni(ni∈K)入度均為0，表明ni(ni∈K)的優(yōu)先順序在Ga的點(diǎn)集Na中是最高級(jí)，所以在Ta中，對(duì)任意一結(jié)點(diǎn)nj(nj∈T)，ni(ni∈K)一定都是nj的祖先結(jié)點(diǎn)。找到離nj最近的S結(jié)點(diǎn)，設(shè)為S′。則n1…nk在S′的左子樹(shù)中，nk+1…nt在S′的右子樹(shù)中，表明K中的結(jié)點(diǎn)優(yōu)先于T中的結(jié)點(diǎn)。因?yàn)閚1…nk之間沒(méi)有優(yōu)先順序，所以它們之間為并聯(lián)關(guān)系，通過(guò)P結(jié)點(diǎn)相連，說(shuō)明S'的左子樹(shù)中除了葉子結(jié)點(diǎn)之外全為P節(jié)點(diǎn)。同理，對(duì)于T中的結(jié)點(diǎn)也均為并聯(lián)關(guān)系，S′的右子樹(shù)中除了葉子結(jié)點(diǎn)之外全為P節(jié)點(diǎn)。所以在Ta中由ni(ni∈K)到nj(nj∈T)的路徑上只有一個(gè)S′結(jié)點(diǎn)，其余均為P結(jié)點(diǎn)。對(duì)應(yīng)于原圖Ga，則說(shuō)明ni與nj之間為串聯(lián)關(guān)系，ni與nj之間存在有向弧由ni指向nj。所以K中和T中的所有點(diǎn)相互之間均為串聯(lián)或并聯(lián)關(guān)系。令Ga刪去K，重復(fù)以上分析過(guò)程，證明Ga中所有點(diǎn)均為串并關(guān)系，Ga是串并有向圖。若G的所有連通分支都是串并有向圖，肯定能判定G是串并有向圖。

4 算法的實(shí)踐

對(duì)于串并有向圖2（a），其連通分支即為其本身。圖2（a）中入度為0 的點(diǎn)為n1，定義K={n1}，刪去K后得到圖2（b），圖2（b）中入度為0的結(jié)點(diǎn)包括n2和n3，定義T=｛n2,n3｝，由算法的證明可知，n1的優(yōu)先級(jí)高于n2，n2與n3的優(yōu)先級(jí)相同，假設(shè)在圖2（a）的分解樹(shù)中，S1是離n2最近的S結(jié)點(diǎn)，所以n1在S的左子樹(shù)中，n2、n3在S1的右子樹(shù)中并且n2、n3通過(guò)P結(jié)點(diǎn)相連，得到分解樹(shù)圖2（c），再在圖2（b）中刪去T，得到圖2（d），圖2（d）中n4入度為0，則n2與n3均為n4的祖先結(jié)點(diǎn)，n4與n2、n3串聯(lián)，則n4在離n4最近的S結(jié)點(diǎn)S1的右子樹(shù)中，n2、n3在S1的左子樹(shù)中，所以在圖2（c）的基礎(chǔ)上加上n4后得到圖2（e）；圖2（d）刪去n4后得到圖2（f），圖2（f）中n5、n6是入度為0 的結(jié)點(diǎn)，則n4是n5、n6的祖先結(jié)點(diǎn)，并且n5和n6并聯(lián)，n4在離n5最近的S結(jié)點(diǎn)S2的左子樹(shù)中，n5和n6在S2的右子樹(shù)中，所以在圖2（e）的基礎(chǔ)上得到圖2（g）。圖2（g）是一個(gè)分解樹(shù)，這說(shuō)明根據(jù)算法的證明過(guò)程進(jìn)行分解后，圖2（a）的確為一個(gè)串并有向圖。

圖2 一個(gè)串并有向圖的應(yīng)用實(shí)例

對(duì)于有向圖3（a），其連通分支有且僅有一個(gè)，即為其本身。圖3（a）中入度為0 的點(diǎn)為n1、n3，刪去n1n3后得到圖3（b），圖3（b）中入度為0 的結(jié)點(diǎn)為n2、n4，則在圖3（a）的分解樹(shù)中，n1n3為并聯(lián)關(guān)系，n2n4也為并聯(lián)關(guān)系，并且n1、n3為n2n4的祖先結(jié)點(diǎn)，得到分解樹(shù)圖3（c），但是由圖3（c）可知n1優(yōu)先于n4，在圖3（a）中n1n4并不存在優(yōu)先約束關(guān)系，所以圖3（c）并不是圖3（a）的分解樹(shù)，圖3（a）沒(méi)有對(duì)應(yīng)的分解樹(shù)，所以圖3（a）并不是串并有向圖。

圖3 一個(gè)非串并有向圖的應(yīng)用實(shí)例

通過(guò)圖2和圖3兩個(gè)例圖可以發(fā)現(xiàn)，如果一個(gè)有向圖G是串并有向圖，則通過(guò)算法H的證明過(guò)程可以將G分解為一個(gè)對(duì)應(yīng)的分解樹(shù)，驗(yàn)證其為串并有向圖；如果一個(gè)有向圖G不是串并有向圖，通過(guò)算法H，G不能分解成一個(gè)分解樹(shù)，驗(yàn)證其不是串并有向圖。

5 結(jié)語(yǔ)

本文首先定義相關(guān)概念，其次描述串并有向圖的判定算法的主體思想，進(jìn)而提出算法H，通過(guò)證明發(fā)現(xiàn)算法H適用于判定有向圖是否為串并有向圖的問(wèn)題，最后通過(guò)實(shí)例證明算法H能夠解決相關(guān)問(wèn)題。