區(qū)間圖最小連通支配集問題的最優(yōu)算法

周星宏，李 鵬，王愛法，趙文平

(重慶理工大學(xué) 理學(xué)院， 重慶 400054)

0 引言

圖的支配集理論近年來已成為圖論中發(fā)展較快的分支之一，在社會(huì)網(wǎng)絡(luò)[1]、自適應(yīng)網(wǎng)絡(luò)[2]、統(tǒng)計(jì)力學(xué)[3]、編碼理論[4]、監(jiān)控系統(tǒng)[5]等領(lǐng)域被廣泛應(yīng)用。支配集中存在許多變形問題，如雙重支配集、羅馬支配集、連通支配集、最小支配集、永恒支配集等。其中連通支配集因其在無線傳感器網(wǎng)絡(luò)中的重要作用受到學(xué)者的廣泛研究，詳見文獻(xiàn)[6-10]。受傳統(tǒng)有線網(wǎng)絡(luò)物理骨干網(wǎng)的啟發(fā)，學(xué)者們提出將虛擬骨干網(wǎng)引入到無線傳感器網(wǎng)絡(luò)的拓?fù)淇刂浦?，以減少網(wǎng)絡(luò)資源的消耗。因此，將無線傳感器網(wǎng)絡(luò)構(gòu)造為磁盤圖時(shí)，虛擬骨干網(wǎng)即是圖的連通支配集，并需同時(shí)具備以下2個(gè)屬性：①每個(gè)不在虛擬骨干網(wǎng)中的節(jié)點(diǎn)可直接與相鄰的節(jié)點(diǎn)通信；②虛擬骨干網(wǎng)中的所有節(jié)點(diǎn)都能在虛擬骨干網(wǎng)內(nèi)相互通信。為使虛擬骨干網(wǎng)盡可能小，學(xué)者們繼續(xù)研究最小連通支配集(MCDS)。而區(qū)間圖MCDS問題是該方向的重要課題。

區(qū)間圖是弦圖的一個(gè)子類，在信息存儲(chǔ)分配和特殊的網(wǎng)絡(luò)管理等領(lǐng)域有著重要應(yīng)用，與其相關(guān)的支配集問題近年來有如下研究：Braga等[11]證明了對(duì)于單位區(qū)間圖中的永恒支配集問題可在線性時(shí)間內(nèi)解決；Soulignac[12]通過改進(jìn)算法，提出時(shí)間復(fù)雜度為O(|E(G)|)的算法來求解單位區(qū)間圖上的雙重支配集問題；Araki等[13]提出可在O(|V(G)|)時(shí)間內(nèi)求出連通單位區(qū)間圖在給定連續(xù)排序下的最小安全支配集；對(duì)于區(qū)間圖的最小支配集問題，Das等[14]提出了一種新的求解支配集的算法，該算法求解的支配集在一定的條件下是最優(yōu)的；Rinemberg等[15]證明了區(qū)間圖的永恒支配數(shù)和團(tuán)連通覆蓋數(shù)是一致的；Lin等[16]證實(shí)了區(qū)間圖的外連通支配集問題可在O(|V(G)|)時(shí)間內(nèi)求解。

將對(duì)實(shí)線上n個(gè)區(qū)間的MCDS問題進(jìn)行研究，分為以下4個(gè)部分：首先，介紹相關(guān)的基礎(chǔ)知識(shí)；其次，回顧區(qū)間圖連通支配集問題求解的相關(guān)算法并指出其不適用之處，進(jìn)而提出求解區(qū)間圖MCDS的線性算法且進(jìn)行了理論分析和實(shí)例驗(yàn)證；再次，給出該算法的時(shí)間和空間復(fù)雜度分析；最后，對(duì)文章進(jìn)行總結(jié)并提出下一步的研究計(jì)劃。

1 基本概念

所用的圖都是簡單圖，即有限、無向、無自環(huán)、無重邊的圖。不失一般性，假設(shè)每個(gè)區(qū)間都包含2個(gè)端點(diǎn)，且沒有2個(gè)區(qū)間共用一個(gè)公共端點(diǎn)。

定義1當(dāng)u和v是一條邊的2個(gè)端點(diǎn)時(shí)，它們是鄰接的且互為鄰居。

定義2v在圖G中的鄰居集合加上v本身稱為v的閉鄰域，記為NG[v]。

定義3頂點(diǎn)v的度(在無自環(huán)圖中)是關(guān)聯(lián)邊的數(shù)目，記為degG(v)。

定義4給定簡單無向圖G=(V，E)和集合D?V，如果V中的每個(gè)頂點(diǎn)都屬于D或與D中的至少一個(gè)頂點(diǎn)相鄰，則D稱為G的支配集。

定義5支配數(shù)γ(G)是G中支配集包含頂點(diǎn)數(shù)的最小值。

定義6集合Dc是圖G的頂點(diǎn)集V的子集，即Dc?V(G)，如果集合Dc是圖G的一個(gè)支配集，且其導(dǎo)出子圖G[D]是連通的，那么稱Dc是G的一個(gè)連通支配集。

定義7連通支配數(shù)γc(G)是G中連通支配集包含頂點(diǎn)數(shù)的最小值。

定義8圖G為區(qū)間圖，如果圖中每個(gè)頂點(diǎn)v與直線上的某個(gè)閉區(qū)間集I之間一一對(duì)應(yīng)，且2個(gè)頂點(diǎn)鄰接當(dāng)且僅當(dāng)它們對(duì)應(yīng)的區(qū)間有非空的交。

定義9若G是區(qū)間圖，且G存在一個(gè)區(qū)間表示，使得每個(gè)頂點(diǎn)對(duì)應(yīng)的區(qū)間長度都一致，則稱G為單位區(qū)間圖。

2 相關(guān)算法

由于無線傳感器網(wǎng)絡(luò)中，既沒有任何固定的基礎(chǔ)設(shè)施，也沒有任何集中的控制，且隨著節(jié)點(diǎn)數(shù)量的增加，網(wǎng)絡(luò)性能會(huì)受到影響。因此，為了實(shí)現(xiàn)高效的路由，可以選擇其中一些節(jié)點(diǎn)組成一個(gè)虛擬骨干網(wǎng)，從相關(guān)網(wǎng)絡(luò)的節(jié)點(diǎn)構(gòu)造一個(gè)稱為區(qū)間圖的圖模型。2012年，Sudhakaraiah等[17]提出了區(qū)間圖的連通網(wǎng)絡(luò)支配集算法，經(jīng)研究發(fā)現(xiàn)Sudhakaraiah等的算法是不適用的，2.1小節(jié)中給出了該算法的詳細(xì)過程，并對(duì)其不足之處進(jìn)行說明。2.2小節(jié)中提出了區(qū)間圖上求解MCDS的最優(yōu)多項(xiàng)式算法。

2.1 算法回顧

算法1中的符號(hào)變量說明：2個(gè)區(qū)間i=[ai,bi]，j=[aj,bj]，非相交區(qū)間NI(i)=j，如果bi

算法1區(qū)間圖的MCDS算法[17]

Input：interval familyI={1,2,3,…,n}

Output：minimal connected network dominating set of an interval graph from a directed networkD

Step1: fori=1 ton

{p=NI(i)

q=min(i)

R=nbd[p]

S=nbd[q]

Next(i)=min({R}{S})

ifNext(i)=nullthen go to Step1

else

joinitoNext(i) and go to Step1}

Step2: forj=2 ton

{ ifI1is intersect toIjcontained inIj

joinI0toIj,

ifIn+1is intersect toIjcontained inIj

joinIn+1toIj}

Step3: find pathsP1,P2,…,Pkfor somekfrom

node forI0toIn+1

Step4: forj=1 tok

{ if nodes ofPjare connected inG,

MCDS={nodes ofPj} }

Step5: end

例1用算法1求下面區(qū)間圖G的MCDS。圖1和圖2均來自參考文獻(xiàn)[17]，但頂點(diǎn)2、3的順序未按右端點(diǎn)排序。

圖1 區(qū)間圖G(例1)

步驟1

nbd[1]={1,2,3}，nbd[2]={1,2,3,4}

nbd[3]={1,2,3,4}，nbd[4]={2,3,4,5,6}

nbd[5]={4,5,6,7}，nbd[6]={4,5,6,7,9}

nbd[7]={5,6,7,8,9}，nbd[8]={7,8,9,10}

nbd[9]={6,7,8,9,10}，nbd[10]={8,9,10}

min(1)=1，min(2)=1，min(3)=1

min(4)=2，min(5)=4，min(6)=4

min(7)=5，min(8)=7，min(9)=6

min(10)=8

NI(1)=4，NI(2)=5，NI(3)=5

NI(4)=7，NI(5)=8，NI(6)=8

NI(7)=10，NI(8)=null，NI(9)=null

NI(10)=null

Next(i)= min({nbd[N(i)]} {nbd[min(i)]})

Next(1)= min({nbd[N(1)]} {nbd[min(1)]})

= min({nbd[4]} {nbd[1]})

= min({2,3,4,5,6} {1,2,3})=4

Next(2)=min({nbd[N(2)]} {nbd[min(2)]})=4

Next(3)=min({nbd[N(3)]} {nbd[min(3)]})=4

Next(4)=min({nbd[N(4)]} {nbd[min(4)]})=5

Next(5)=min({nbd[N(5)]} {nbd[min(5)]})=7

Next(6)=min({nbd[N(6)]} {nbd[min(6)]})=7

Next(7)=min({nbd[N(7)]} {nbd[min(7)]})=8

Next(8)=min({nbd[N(8)]} {nbd[min(8)]})=null

Next(9)=min({nbd[N(9)]} {nbd[min(9)]})=null

Next(10)=min({nbd[N(10)]} {nbd[min(10)]})=null

步驟2如圖2所示，把區(qū)間圖擴(kuò)大，在首尾擴(kuò)展2個(gè)虛擬區(qū)間I0和In+1，然后得到一個(gè)定向網(wǎng)絡(luò)圖[17]，如圖3所示。其中N={0,1,2,3,4,5,6,7,8,9,10,11}，L=L1∪L2。

圖2 區(qū)間圖G首尾擴(kuò)展2個(gè)虛擬區(qū)間I0和In+1

圖3 定向網(wǎng)絡(luò)圖D(N，L)

步驟3由圖3可以得到3條路徑分別為：0-3-4-5-7-8-11；0-2-4-5-7-8-11；0-1-4-5-7-8-11。

步驟4輸出結(jié)果為{3,4,5,7,8}，{2,4,5,7,8}。

步驟5結(jié)束。

但是可以找到D={v2,v4,v6,v9}是區(qū)間圖G的MCDS。明顯地，對(duì)于圖1的MCDSγc(G)=4≠5，所以，算法1輸出的結(jié)果不是MCDS，因此Sudhakaraiah等的算法是不適用的。

2.2 區(qū)間圖MCDS問題的線性算法

以下是提出的區(qū)間圖MCDS算法。算法中輸入的區(qū)間圖都是連通的。

算法2區(qū)間圖MCDS問題算法

Input：一個(gè)區(qū)間圖G=(V，E)，頂點(diǎn)集V(G)={v1,v2,…,vn}，每個(gè)頂點(diǎn)分別對(duì)應(yīng)區(qū)間{I1,I2,…,In}，對(duì)于1≤i≤n，有Ii=[ai,bi]，其中ai、bi分別是區(qū)間Ii的左右端點(diǎn)。其中b1

Output：G的一個(gè)MCDSD

Step1：letj=r(1) andD={vr(1)}//Ir(1)是I1本身或與I1相交的右端點(diǎn)最大的區(qū)間

Step2：do ifvr(j)?NG[vl]∥Ir(j)是Ij本身或與Ij相交的右端點(diǎn)最大的區(qū)間，

{j=r(j)， andD=D∪{vj}}

Step3：outputD

Step4：end

例2用算法2求下面區(qū)間圖G的MCDS。

由圖4可知左端點(diǎn)最大的頂點(diǎn)為vl=v13，NG[v13]={v12,v13,v14,v15}，根據(jù)算法2可得如下步驟：

圖4 區(qū)間圖G(例2)

步驟1G={v1,v2,v3,…,v15}，v1的鄰居有{v2,v3}，其中右端點(diǎn)最大鄰居為vr(1)=v3，此時(shí)j=r(1)=3，D={v3}。

步驟2由步驟1得vr(1)=v3，且v3?NG[v13]，j=r(3)=6，即v3的鄰居中右端點(diǎn)最大的點(diǎn)為v6，D={v3,v6}；v6?NG[v13]，j=r(6)=7，即v6的鄰居中右端點(diǎn)最大的點(diǎn)為v7，所以D={v3,v6,v7}；v7?NG[v13]，j=r(7)=9，即v7的鄰居中右端點(diǎn)最大的點(diǎn)為v9，所以D={v3,v6,v7,v9}；v9?NG[v13]，j=r(9)=12，即v9的鄰居中右端點(diǎn)最大的點(diǎn)為v12，故D={v3,v6,v7,v9,v12}；v12∈NG[v13]時(shí)，算法結(jié)束迭代。

步驟3輸出D={v3,v6,v7,v9,v12}。

步驟4結(jié)束。

綜上γc(G)≤5，經(jīng)驗(yàn)算知，圖4的MCDS為D={v3,v6,v7,v9,v12}，故γc(G)=5。

定理1 算法2輸出的集合D是區(qū)間圖G的一個(gè)MCDS。

證明令區(qū)間圖G=(V，E)，其中V(G)={v1,v2,…,vn}，每個(gè)頂點(diǎn)分別對(duì)應(yīng)區(qū)間{I1,I2,…,In}，對(duì)于1≤i≤n，有Ii=[ai,bi]，其中ai、bi分別是區(qū)間Ii的左右端點(diǎn)。其中b1

1) 若γc(G)=1，則|D′|=1，設(shè)D′={vp}，因?yàn)镈′能支配G，所以vp能支配v1，即vp∈NG[v1]，如圖5所示?？傻胮≤r(1)，從而NG[vp]?NG[vr(1)]，所以{vr(1)}也是G的MCDS。往證，算法2輸出的是D={vr(1)}。設(shè)vl是區(qū)間圖G中左端點(diǎn)最大的點(diǎn)，因?yàn)関r(1)可以支配G，所以vr(1)∈NG[vl]。由算法2可知，算法停止迭代，進(jìn)而輸出D={vr(1)}。

圖5 γc(G)=1時(shí)的區(qū)間圖

2) 當(dāng)γc(G)≥2時(shí)，由前文的假設(shè)可知，D′是區(qū)間圖G的某個(gè)MCDS。所以D′可以支配v1，故存在圖G中的某個(gè)頂點(diǎn)vk∈D′∩NG[v1]。若vr(1)?D′，由于vr(1)是v1鄰居中右端點(diǎn)最大的點(diǎn)，故NG[vk]?NG[vr(1)]，如圖6所示。用vr(1)替換vk，即D′-vk+vr(1)也是區(qū)間圖G的MCDS。因此，不妨設(shè)vr(1)∈D′，下面考慮：G*=G-v1-v2-…-vr(1)-1，G*還可表示為G*={vr(1),vr(1)+1,…,vn}。此時(shí)vr(1)是圖G*在Ir(1),Ir(1)+1,…,In中右端點(diǎn)最小的點(diǎn)，且G*中左端點(diǎn)最大的點(diǎn)仍為vl。由數(shù)學(xué)歸納原理，通過算法繼續(xù)迭代，可以得到D*=D-vr(1)是G*的一個(gè)MCDS。

圖6 γc(G)≥2時(shí)的區(qū)間圖

接下來證明D=D*+vr(1)是區(qū)間圖G的MCDS，按以下步驟：①D是G的支配集；②D是G的連通支配集；③D是G的MCDS。

首先，D*可支配G*={vr(1),vr(1)+1,…,vn}，且vr(1)能支配{v1,v2,…,vr(1)-1}，故D=D*+vr(1)是G的支配集。

其次，正因?yàn)棣胏(G)≥2，從而vr(r(1))存在。由于D*是G*的一個(gè)MCDS，可知vr(1)與vr(r(1))鄰接，所以D=D*+vr(1)是連通的，易知，γc(G)≤|D|=1+|D*|=1+γc(G*)。

圖7 區(qū)間圖G的一個(gè)

因此|D|=1+|D*|=1+γc(G*)=γc(G)，即D是區(qū)間圖G的MCDS。

綜上，由數(shù)學(xué)歸納原理知定理1成立。

3 時(shí)間復(fù)雜度和空間復(fù)雜度分析

定理2算法2的時(shí)間復(fù)雜度和空間復(fù)雜度都是線性的。

證明設(shè)輸入的區(qū)間圖G=(V，E)，頂點(diǎn)為v1,v2,…,vn，每個(gè)頂點(diǎn)對(duì)應(yīng)的區(qū)間為I1,I2,…,In。在Step1中，找到j(luò)=r(1)(Ir(1)是I1本身或與I1相交的右端點(diǎn)最大的區(qū)間)，需要的時(shí)間是O(degG(v1))；同理，對(duì)于Step2中的每個(gè)j，找到r(j)(Ir(j)是Ij本身或與Ij相交的右端點(diǎn)最大的區(qū)間)，需要的時(shí)間是O(degG(vj))，因此整個(gè)算法需要的時(shí)間為：

其中：m是G的邊數(shù)，n是G的頂點(diǎn)數(shù)。同時(shí)，因?yàn)槊恳徊街恍璐鎯?chǔ)D，而D的頂點(diǎn)數(shù)不會(huì)超過n，所以該算法的空間復(fù)雜度是O(m+n)。由此可見，整個(gè)算法的時(shí)間和空間復(fù)雜度都是線性的。

4 結(jié)論

通過對(duì)區(qū)間圖上MCDS問題的研究，設(shè)計(jì)線性算法。實(shí)例驗(yàn)證和理論分析都表明該算法是線性的，時(shí)間和空間復(fù)雜度均為O(m+n)。綜上，此算法對(duì)提高無線傳感器網(wǎng)絡(luò)性能方面具有較高的實(shí)際應(yīng)用價(jià)值。下一步，將繼續(xù)研究圖的支配集問題，例如區(qū)間圖k-羅馬支配集問題和安全控制集問題。