串并有向圖的判定算法及應用實例

王琪

(江西制造職業技術學院 江西 南昌 330095)

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

1 相關定義

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

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

定義2[15]對有向圖G的每條弧如果均用一條邊代替它，得到一個無向圖，這個無向圖稱為G的基本圖。

定義3 某個點前繼的數量表示該點的入度，后繼的數量表示為該點的出度，刪除某個點包括刪除該點和與該點相連的邊。

定義4[15]兩個端點重合為一點的邊稱為環，兩個端點都相同的邊稱為重邊，一個有向圖，如果它既沒有環，也沒有重邊，則稱為簡單有向圖。

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

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

圖的表示方法很多，采用不同的表示方法，可獲得圖的不同的時空性能[16]。用鄰接矩陣表示圖的優點是易于計算機存儲。

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

本文中定義的有向圖的連通，指的是如果其基本圖是連通的，則表示該串并有向圖連通，串并有向圖中的連通分支對應其基本圖相同點和邊的連通分支。

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

（1）僅包含一個頂點的有向圖是可遷的串并有向圖。

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

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

（4）通過有限步應用（1）（2）（3）得到的有向圖是可遷的串并有向圖。

串并有向圖的主要特征是在一個串并有向圖中，所有結點均為串行或并行關系。串行關系的結點有先后順序，并行關系的結點為平行關系，沒有先后順序。通過串并有向圖的定義可知在串并有向圖中不存在回路。

定義9[15]一個樹是一個連通且無回路的圖。

定義10 二叉樹的遞歸定義。

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

樹是圖的特例。一個串并有向圖G可以分解為一個二叉樹Tr，Tr 稱為圖G的分解樹。如圖1 所示，圖1（a）表示一個串并有向圖，圖1（b）表示其對應的分解樹。Tr的葉子結點對應G的頂點，中間結點用S或P表示。S表示其左右兩個子樹之間是串行關系，并且左子樹優先于右子樹，P表示左右兩個子樹之間是并行關系。

圖1 一個串并有向圖及其分解樹

本文提出的串并有向圖的判定算法，其主要思想是對一個給定的有向圖的所有連通分支逐一進行遞歸分解，若所有連通分支都滿足相關條件，則判定該有向圖是串并有向圖。通過該算法能夠準確判斷一個有向圖是否為串并有向圖。

2 算法描述

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

Aa是G的連通分支Ga的n×n階鄰接矩陣，對圖G，運行以下算法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解決了串并有向圖判定的問題。

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

4 算法的實踐

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

圖2 一個串并有向圖的應用實例

對于有向圖3（a），其連通分支有且僅有一個，即為其本身。圖3（a）中入度為0 的點為n1、n3，刪去n1n3后得到圖3（b），圖3（b）中入度為0 的結點為n2、n4，則在圖3（a）的分解樹中，n1n3為并聯關系，n2n4也為并聯關系，并且n1、n3為n2n4的祖先結點，得到分解樹圖3（c），但是由圖3（c）可知n1優先于n4，在圖3（a）中n1n4并不存在優先約束關系，所以圖3（c）并不是圖3（a）的分解樹，圖3（a）沒有對應的分解樹，所以圖3（a）并不是串并有向圖。

圖3 一個非串并有向圖的應用實例

通過圖2和圖3兩個例圖可以發現，如果一個有向圖G是串并有向圖，則通過算法H的證明過程可以將G分解為一個對應的分解樹，驗證其為串并有向圖；如果一個有向圖G不是串并有向圖，通過算法H，G不能分解成一個分解樹，驗證其不是串并有向圖。

5 結語

本文首先定義相關概念，其次描述串并有向圖的判定算法的主體思想，進而提出算法H，通過證明發現算法H適用于判定有向圖是否為串并有向圖的問題，最后通過實例證明算法H能夠解決相關問題。