李有浩,趙承業(yè),董合德

(中國計量大學(xué) 理學(xué)院,浙江 杭州 310018)

圖的支配問題在圖的相關(guān)研究中一直是一個很熱門的分支,因為其具有很多的變形和實際的相關(guān)應(yīng)用,從理論到算法[1-2],各種論點層出不窮.而連通支配集[3]就是圖支配的一個重要分支問題.定義集合C?V(G),G(C)是集合C在圖G=(V,E)中的生成子圖,N(v)表示頂點v所有鄰居節(jié)點,N[v]=N(v)∪{v}如果滿足1)|N[v]∩C|≥1,?v∈V(G),2)G(C)是連通的,那么就稱集合C是圖G的連通支配集.相關(guān)的研究也有很多,如文獻[4,5].

誤報容錯支配集是圖的支配問題的一個新的有趣的延伸[6-10],從容錯的角度來看,其實是介于圖的2-tuple支配和3-tuple支配之間的一個圖的支配問題.這個問題最早是由Slater在2009年提出的[7],其實際意義可以對應(yīng)社交網(wǎng)絡(luò)中如下的一種情況.

我們對于一般的社交網(wǎng)絡(luò)可以用圖G=(V,E)來表示,圖G中的每一個點代表一個社交個體,如果兩個個體之間可以相互交換信息的話,那么就給這兩個個體所對應(yīng)的圖G中的點連上一條邊.這里假設(shè)圖G中的每一個點都可能是一個入侵節(jié)點,例如一個著火點或是一個破壞者等等.假設(shè)存在這樣的入侵者點v′.網(wǎng)絡(luò)中還存在具有保護裝置的點,它可以檢測出其鄰居節(jié)點是否是入侵節(jié)點,并且匯報這一入侵點的位置.要求盡可能布置最少的保護節(jié)點,而且還能準(zhǔn)確找到網(wǎng)絡(luò)中的入侵節(jié)點.這在網(wǎng)絡(luò)的拓撲圖中,相當(dāng)于找到最小的滿足條件的支配集D,在D中所有的點布置保護裝置.然而這樣的保護裝置可能會損壞而不會匯報信息,為了使其能繼續(xù)準(zhǔn)確找到入侵點,這樣的支配集D必須是雙支配集.此外,這樣的保護裝置可能會匯報假的信息,這個時候即使D是雙支配集也可能不能準(zhǔn)確的找到入侵的節(jié)點.為了解決這一問題,Slater提出了誤報容錯支配集這一概念,并且證明下面的引理[7].

引理1:集合L是圖G的一個誤報容錯支配集當(dāng)且僅當(dāng):

1)集合L是圖的一個雙支配集;

2)對于圖G中的任意一對節(jié)點u,v,都有|(N[u]∪N[v])∩L|≥3.

1　連通誤報容錯支配集問題精確算法

連通的誤報容錯支配集問題已經(jīng)被證明是屬于NP-完全問題[9],即很難找到這種問題的多項式時間的算法.這節(jié)給出一般圖上構(gòu)造最小連通誤報容錯支配集的精確算法,算法的思想就是根據(jù)連通誤報容錯支配集的定義,對所有的點進行遍歷判斷.

對于一般的連通圖(頂點數(shù)超過3)G=(V,E),頂點數(shù)為n,算法是從尋找其最小的雙支配集開始.

1)利用整數(shù)規(guī)劃求得圖G的最小雙支配集的頂點數(shù)s.

2)求得所有從n個點中選取s個點的組合集D.

3)遍歷D中所有的集合L,判斷集合L是否滿足雙支配、點對三支配、子圖連通的條件,如果都滿足跳出循環(huán),輸出集合L.

4)如果遍歷完D中所有的集合都不能滿足其是連通誤報容錯支配集的三個條件,則令s=s+1,并轉(zhuǎn)到步驟2繼續(xù)循環(huán).

由于這里用到的是遍歷判斷的思想,對于每一個點的情況,其可能屬于支配集,也可能不屬于支配集,所以算法的復(fù)雜度為O(2n).

2　連通誤報容錯支配集問題的啟發(fā)式算法構(gòu)造

這節(jié)提出了構(gòu)造一般連通圖上的連通誤報容錯支配集的一種基于貪婪策略的多項式時間啟發(fā)式算法.

2.1　問題描述及符號表示

問題描述:設(shè)圖G=(V,E),n=|V|為圖的節(jié)點數(shù).找到圖G的一個集合L,保證其圖G的連通誤報容錯支配集的前提下,使L的節(jié)點數(shù)盡可能的少.

符號說明:在算法執(zhí)行過程中,節(jié)點和節(jié)點對的狀態(tài)都可能發(fā)生變化.節(jié)點可能出現(xiàn)未定義,1-被支配,2-被支配,支配這4種狀態(tài);節(jié)點對可能出現(xiàn)未定義,1-被支配,2-被支配,3-被支配這4種狀態(tài).假定在算法初始階段,所有節(jié)點和節(jié)點對狀態(tài)均為未定義.設(shè)當(dāng)前操作節(jié)點為v,定義關(guān)于節(jié)點v的下列符號:

L0:節(jié)點狀態(tài)為未定義的節(jié)點集合.初始時,L0=V.

L1:節(jié)點狀態(tài)為支配的節(jié)點集合.初始時,L1=?.

L2:算法執(zhí)行過程中當(dāng)前的節(jié)點狀態(tài)為1-被支配,2-被支配的節(jié)點集合,其也是可能成為支配點的集合.初始時,L2=?.

d0(v):N[v]中狀態(tài)為未定義的節(jié)點個數(shù).

d1(v):N[v]中狀態(tài)為1-被支配的節(jié)點個數(shù).

d2(v):N[v]中狀態(tài)為2-被支配的節(jié)點個數(shù).

P0:狀態(tài)為未定義的節(jié)點對集合.

P1:算法執(zhí)行過程中當(dāng)前節(jié)點對狀態(tài)為1-被支配或2-被支配的節(jié)點對集合.初始時,P1=?.

P2:狀態(tài)為3-被支配的節(jié)點對集合.初始時,P2=?.

d0(pv):節(jié)點v閉領(lǐng)域內(nèi)的節(jié)點對中狀態(tài)為未定義的節(jié)點對數(shù).

d1(pv):節(jié)點v閉領(lǐng)域內(nèi)的節(jié)點對中狀態(tài)為1-被支配或2-被支配的節(jié)點對對數(shù).

規(guī)則描述:在算法執(zhí)行過程中,狀態(tài)為支配的節(jié)點的閉鄰域內(nèi)的節(jié)點狀態(tài)也會發(fā)生變化,同時需要選擇新的支配節(jié)點,直到滿足條件,具體規(guī)則如下:

規(guī)則Ⅰ設(shè)節(jié)點v為支配節(jié)點,則任意一非支配節(jié)點u∈N[v]的狀態(tài)變化如下:

1)若節(jié)點u的當(dāng)前狀態(tài)為未定義,則其狀態(tài)變?yōu)?-被支配;

2)若節(jié)點u的當(dāng)前狀態(tài)為1-被支配,則其狀態(tài)變?yōu)?-被支配.

規(guī)則Ⅱ設(shè)節(jié)點v為當(dāng)前支配節(jié)點,選擇新的支配節(jié)點的規(guī)則如下:

1)找出L2中d0(u)最大值所對應(yīng)的節(jié)點u,若節(jié)點u唯一,則將該節(jié)點作為新的支配節(jié)點,否則把這些節(jié)點放入一個集合里,記為D0(v),轉(zhuǎn)入2);

2)找出D0(v)中d1(u)最大值所對應(yīng)的節(jié)點u,若節(jié)點u唯一,則將該節(jié)點作為新的支配節(jié)點,否則把這些節(jié)點放入一個集合里,記為D1(v),轉(zhuǎn)入3);

3)找出D1(v)中d2(u)最大值所對應(yīng)的節(jié)點u,若節(jié)點u唯一,則將該節(jié)點作為新的支配節(jié)點,否則取這些節(jié)點中序號較小者作為新的支配點.

規(guī)則Ⅲ若所有節(jié)點均為2-支配,部分節(jié)點對未滿足3-支配,選擇新的支配節(jié)點規(guī)則如下:

1)找出L2中d0(pu)最大值所對應(yīng)的節(jié)點u,若節(jié)點u唯一,則將該節(jié)點作為新的支配節(jié)點,否則把這d1(pu)些節(jié)點放入一個集合里,記為P0(v),轉(zhuǎn)入2);

2)找出P0(v)中最大值所對應(yīng)的節(jié)點u,若節(jié)點u唯一,則將該節(jié)點作為新的支配節(jié)點,否則取這些節(jié)點中序號較小者作為新的支配點.

2.2　算法構(gòu)造

這節(jié)給出的連通誤報支配集的啟發(fā)式算法的主要思想是:首先使圖中的任意節(jié)點的狀態(tài)變化為2-被支配,繼續(xù)添加新的支配點使圖中所有的節(jié)點對狀態(tài)變?yōu)?-被支配.其中第一步是基于最小生成樹的思想,對圖G設(shè)置集合S來放置支配節(jié)點,集合V-S中與集合S鄰接且度數(shù)相對較大的節(jié)點優(yōu)先考慮最為支配點.不斷的重復(fù)這樣的操作,直到所有的節(jié)點狀態(tài)都是2-被支配或支配節(jié)點狀態(tài);第二步從所有的節(jié)點中,以為滿足3-被支配的節(jié)點對數(shù)目最大作為貪心選擇標(biāo)準(zhǔn)來選擇新的支配點加入到集合S中,直到所有的節(jié)點對狀態(tài)都為3-被支配.下面是相關(guān)的算法描述.

步驟1構(gòu)造節(jié)點2-支配集

1)在圖G中選擇節(jié)點度最大的節(jié)點(若度最大節(jié)點不唯一,則選擇序號最小的節(jié)點)作為初始支配節(jié)點v0,把節(jié)點v0從集合L0中取出,放入集合L1中,按照規(guī)則Ⅰ改變N[v0]的節(jié)點狀態(tài).并且更新集合L0,L2,將狀態(tài)為1-被支配的節(jié)點從集合L0中取出,放入集合L2中.

2)在集合L2中的所有節(jié)點,按照規(guī)則Ⅱ選擇新的支配點,并作為當(dāng)前操作節(jié)點v,按照規(guī)則Ⅰ改變N[v]中所有非支配節(jié)點的狀態(tài).更新集合L0,L1,L2,即將節(jié)點v從L2取出,放入到集合L1中;將狀態(tài)為1-被支配的節(jié)點從L0中取出,放入到集合L2中.

3)若圖G中非支配的節(jié)點均為2-被支配,則算法結(jié)束,否則轉(zhuǎn)2)繼續(xù)執(zhí)行.

步驟2構(gòu)造節(jié)點對3-支配集

1)根據(jù)當(dāng)前圖G中的節(jié)點對的狀態(tài),更新集合P0,P1,P2.

2)在集合L2中的所有節(jié)點,按照規(guī)則Ⅲ選擇新的支配點,并作為當(dāng)前操作的節(jié)點v,將該節(jié)點v從L2L2中取出,放入集合L1中.

3)若圖G中的節(jié)點對狀態(tài)均為3-被支配,則算法結(jié)束,否則,更新集合P0,P1,P2,轉(zhuǎn)2)繼續(xù)執(zhí)行.

定理1:根據(jù)規(guī)則Ⅰ、Ⅱ、Ⅲ經(jīng)過構(gòu)造節(jié)點2-支配集和節(jié)點對3-支配集得到的集合L1就是圖G的一個連通誤報容錯支配集.

證明:首先證明集合的連通性.在構(gòu)造2-支配集時,除了初始節(jié)點,新的支配節(jié)點都是從L2中選取,即被支配的節(jié)點集合.保證新的支配節(jié)點總是與L1中至少一個節(jié)點相連接,因此最后得到的2-支配集就是連通的集合.同樣在構(gòu)造3-支配集時,新的支配點也是從L2中選出,因而得到的節(jié)點對3-支配集即最后得到的集合L1是連通的;其次證明集合L12-支配圖G中所有的節(jié)點,即|N[v]∩L1|≥2,?v∈V(G).在步驟1執(zhí)行后得到的集合L1,其2-支配圖G中所有的非支配集節(jié)點,而對于L1中的節(jié)點,由于連通性的保證,所以有|N[v]∩L1|≥2,?v∈L1.最后證明集合L13-支配圖G中的所有節(jié)點對,即|(N[u]∪N[v])∩L|≥3,?u,v∈V(G)(u≠v).由算法步驟2最后的終止條件可以知道最后得到的L1一定3-支配所有的節(jié)點對;否則算法一直進行下去,因而圖中所有的節(jié)點對的狀態(tài)最后都是3-被支配.

綜上2.2所提出的算法最后得到的就是圖G的一個連通誤報容錯支配集.

3　算法分析及實現(xiàn)

算法的步驟1形成2-支配的節(jié)點集合,按規(guī)則Ⅰ更新支配節(jié)點鄰域內(nèi)鄰接節(jié)點狀態(tài)的時間復(fù)雜度為O(n),更新節(jié)點閉鄰域內(nèi)的節(jié)點狀態(tài)的時間復(fù)雜度為O(n2);按規(guī)則Ⅱ選取的新的節(jié)點的時間復(fù)雜度為O(n),則構(gòu)造2-被支配的節(jié)點結(jié)合的時間復(fù)雜度為O(n3).算法步驟2形成節(jié)點對3-被支配集,更新各節(jié)點閉鄰域的節(jié)點對數(shù)的時間復(fù)雜度為O(n2);按規(guī)則Ⅲ選取新的支配節(jié)點的時間復(fù)雜度為O(n),則構(gòu)造節(jié)點對3-支配集的時間復(fù)雜度O(n3).綜上,2.2提出的啟發(fā)式算法的時間復(fù)雜度為O(n3).

對本文提出的基于貪婪策略的連通誤報容錯支配集啟發(fā)式算法進行仿真實驗,測試所用的無線傳感器網(wǎng)絡(luò)隨機圖通過如下方式產(chǎn)生:在500×500的平面內(nèi),隨機產(chǎn)生n個節(jié)點,假設(shè)這樣的無線傳感器網(wǎng)絡(luò)每個節(jié)點的通信半徑是相同的,記為R,如果兩個節(jié)點的距離不大于R,則認為這兩個節(jié)點是有邊連接的.如果構(gòu)造得到的圖不是連通的,那就重新構(gòu)造,直到構(gòu)造的圖連通為止.現(xiàn)在以節(jié)點數(shù)n為150,節(jié)點之間的通信半徑80為例,用圖來說明構(gòu)造的連通誤報容錯支配集的過程.(如圖1)圖中用藍色節(jié)點表示被支配節(jié)點,紅色節(jié)點表示形成節(jié)點2支配產(chǎn)生的支配節(jié)點,用黑色節(jié)點表示形成節(jié)點對3-支配集產(chǎn)生的支配節(jié)點.從圖中可知,所得到就是圖G的一個連通誤報容錯支配集.

圖1　連通誤報容錯支配集構(gòu)造Figure 1　Construction of connected liar’s dominating set

為體現(xiàn)文中提出的啟發(fā)式算法的計算效率和最終得到連通誤報容錯支配集和最優(yōu)值之間的誤差大小,我們對精確算法和啟發(fā)式算法進行了仿真(表1),仿真的圖也是基于計算機隨機生成的連通圖,圖的生成算法以及具體結(jié)果如下.

實驗所用圖的生成算法:

1)在500×500的平面內(nèi),隨機生成n個頂點.

2)兩個節(jié)點之間的距離小于100,就連接兩個節(jié)點.

3)用深度優(yōu)先搜索判斷生成的圖是否連通,連通則輸出該圖,否則跳到步1)精確算法和啟發(fā)式算法對應(yīng)的結(jié)果如下.

表1　啟發(fā)式算法的相關(guān)實驗結(jié)果

表2　精確算法的相關(guān)實驗結(jié)果

從表2中可知,由于精確算法的復(fù)雜度比較高,因此我們可以得到精確解的網(wǎng)絡(luò)規(guī)模大小比較有限.通過表1和表2比較,我們可以看到啟發(fā)式算法在計算時間和網(wǎng)絡(luò)規(guī)模上具有很大的優(yōu)勢,其結(jié)果和精確解比較差距較小.

仿真實驗所用計算平臺:CPU酷睿i5-7200u,內(nèi)存8 G,硬盤SSD 256G.

4　總結(jié)與展望

本文先是提出了一個連通誤報容錯支配集問題的精確算法,并證明了其計算復(fù)雜度是指數(shù)型.隨后給出了該問題的一個時間復(fù)雜度為O(n3)的啟發(fā)式算法,最后通過計算機模擬實現(xiàn)兩個算法,并從運行時間和準(zhǔn)確度上比較兩個算法.文中給出的算法屬于集中式的算法,此外可以考慮分布式算法,對于局部的信息進行支配集構(gòu)造,最后合并處理,這樣計算的時間復(fù)雜度應(yīng)該能降低.