王琪

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

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

1 相關(guān)定義

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

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

定義2[15]對有向圖G的每條弧如果均用一條邊代替它，得到一個(gè)無向圖，這個(gè)無向圖稱為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)的邊稱為環(huán)，兩個(gè)端點(diǎn)都相同的邊稱為重邊，一個(gè)有向圖，如果它既沒有環(huán)，也沒有重邊，則稱為簡單有向圖。

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

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

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

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

本文中定義的有向圖的連通，指的是如果其基本圖是連通的，則表示該串并有向圖連通，串并有向圖中的連通分支對應(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)是可遷的串并有向圖，稱G是由G1和G2串行合成的。

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

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

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

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

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

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

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

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

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

2 算法描述

串并有向圖判定算法的主要過程：令G1,G2,…,Gn是有向圖G（非空圖）的n個(gè)連通分支。對Gi(i∈1，…，n)，找到其所有入度為0 的結(jié)點(diǎn)，定義為結(jié)點(diǎn)集K，如果K為空集，則說明Gi中包含有向回路，判定Gi不是串并有向圖，如果K不是空集，刪除K中的所有結(jié)點(diǎn)后再找到新的有向圖中所有入度為0 的結(jié)點(diǎn)，定義為結(jié)點(diǎn)集T。如果T為空集，則說明Gi為單節(jié)點(diǎn)，根據(jù)定義8 的（1）說明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ù)以上過程，進(jìn)行遞歸判斷。若G1,G2,…,Gn均是串并有向圖，則最終判定圖G為串并有向圖。

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

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

4 算法的實(shí)踐

對于串并有向圖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)先級高于n2，n2與n3的優(yōu)先級相同，假設(shè)在圖2（a）的分解樹中，S1是離n2最近的S結(jié)點(diǎn)，所以n1在S的左子樹中，n2、n3在S1的右子樹中并且n2、n3通過P結(jié)點(diǎn)相連，得到分解樹圖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的右子樹中，n2、n3在S1的左子樹中，所以在圖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的左子樹中，n5和n6在S2的右子樹中，所以在圖2（e）的基礎(chǔ)上得到圖2（g）。圖2（g）是一個(gè)分解樹，這說明根據(jù)算法的證明過程進(jìn)行分解后，圖2（a）的確為一個(gè)串并有向圖。

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

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

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

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

5 結(jié)語

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