大規(guī)模圖頂點(diǎn)覆蓋的增量算法研究

喬 龍，陳德剛

(華北電力大學(xué) 數(shù)理學(xué)院，北京 102206)

0 引言

頂點(diǎn)覆蓋問(wèn)題[1]在圖論中是一個(gè)著名的NP完全問(wèn)題，在現(xiàn)實(shí)生活中應(yīng)用非常廣泛。例如，博物館展覽柜設(shè)計(jì)、大型網(wǎng)絡(luò)監(jiān)控節(jié)點(diǎn)的布置、大型交通運(yùn)輸線(xiàn)路網(wǎng)絡(luò)設(shè)計(jì)、集成電路設(shè)計(jì)等等。在人工智能大數(shù)據(jù)時(shí)代背景下，在實(shí)際問(wèn)題中涉及的往往是動(dòng)態(tài)圖，針對(duì)于這種具有增量變化的動(dòng)態(tài)圖設(shè)計(jì)出一種智能化的求解頂點(diǎn)覆蓋算法無(wú)疑具有重要的應(yīng)用價(jià)值。

近年來(lái)，國(guó)內(nèi)外學(xué)者設(shè)計(jì)出了一系列求解極小頂點(diǎn)覆蓋集合的算法，但就其增量問(wèn)題的相關(guān)研究卻很少。求解圖的極小頂點(diǎn)覆蓋集合，其傳統(tǒng)的思想是利用布爾變量的運(yùn)算[1-2]，這是最基本的求解方法。但是其運(yùn)算復(fù)雜度，尤其是面對(duì)大規(guī)模的圖結(jié)構(gòu)模型問(wèn)題時(shí)，達(dá)不到高效性的要求。吳春等[3]基于頂點(diǎn)覆蓋問(wèn)題的理論研究，發(fā)現(xiàn)最小點(diǎn)覆蓋問(wèn)題、最大獨(dú)立集問(wèn)題與最大團(tuán)問(wèn)題三者事實(shí)上是等價(jià)的。對(duì)于網(wǎng)絡(luò)監(jiān)測(cè)點(diǎn)部署，陶星宇[4]針對(duì)原有網(wǎng)絡(luò)中布置的監(jiān)測(cè)點(diǎn)不易變動(dòng)的問(wèn)題，提出了一種增量網(wǎng)絡(luò)監(jiān)測(cè)點(diǎn)的增量選取算法。丁三軍等[5]和Zhou T等[6]基于貪婪算法的思想研究了極小頂點(diǎn)覆蓋的求解與更新問(wèn)題。占善華等[7]提出了一種更新最小頂點(diǎn)覆蓋的增量式屬性約簡(jiǎn)算法。苗董晶等[8]研究了沖突圖中的極小頂點(diǎn)覆蓋算法。Wang L等[9]設(shè)計(jì)出的分支定界算法解決了大量圖的極小權(quán)重覆蓋問(wèn)題。對(duì)于加權(quán)頂點(diǎn)覆蓋，F(xiàn)ukunaga T等[10]求解出了加權(quán)的無(wú)向圖的最小權(quán)重的Steiner樹(shù)。Tang C等[11]利用博弈論的思想把加權(quán)頂點(diǎn)覆蓋問(wèn)題建模為不對(duì)稱(chēng)的博弈?？芾诘萚12]基于Dijkstra 算法,以最短路長(zhǎng)的最大值為標(biāo)準(zhǔn),按照一定原則篩選出點(diǎn)覆蓋集合的頂點(diǎn)。王麗麗等[13]利用線(xiàn)性規(guī)劃松弛的方法實(shí)現(xiàn)對(duì)計(jì)算復(fù)雜度進(jìn)行預(yù)測(cè)，在求一個(gè)圖論模型的點(diǎn)覆蓋集合上取得了不錯(cuò)的效果。聶曉燕等[14]和高琳等[15]研究了DNA計(jì)算標(biāo)簽的最小頂點(diǎn)覆蓋問(wèn)題。鄭少萍[16]和袁啟杰等[17]研究了Petersen圖的極小頂點(diǎn)覆蓋集合的求解問(wèn)題。這些研究進(jìn)一步豐富了極小頂點(diǎn)覆蓋的理論。

在上述研究中，這些算法所面對(duì)的大部分是靜態(tài)圖。在面對(duì)動(dòng)態(tài)圖的時(shí)候沒(méi)有包含快速的更新頂點(diǎn)覆蓋的理論機(jī)制，因而在圖的規(guī)模擴(kuò)張時(shí)需要重新計(jì)算頂點(diǎn)覆蓋，會(huì)占用大量的計(jì)算和存儲(chǔ)資源。本文旨在針對(duì)大規(guī)模圖的增量變化問(wèn)題，找到可以高效更新頂點(diǎn)覆蓋的增量算法。為了研究出一種智能化更新極小頂點(diǎn)覆蓋的算法，并且就其時(shí)間復(fù)雜度而言滿(mǎn)足其高效性，我們從圖的極小頂點(diǎn)覆蓋集合的定義出發(fā)，對(duì)大規(guī)模圖頂點(diǎn)數(shù)目增加、邊數(shù)目增加和頂點(diǎn)與邊數(shù)目均增加3種動(dòng)態(tài)過(guò)程分析了頂點(diǎn)覆蓋的增量機(jī)理。在此基礎(chǔ)上通過(guò)對(duì)圖的存儲(chǔ)矩陣、鄰接矩陣和關(guān)聯(lián)矩陣進(jìn)行更新，設(shè)計(jì)頂點(diǎn)覆蓋的更新迭代算法，使得更新后的極小頂點(diǎn)覆蓋集合能夠覆蓋到更新后圖中的所有的邊，并且能夠剔除圖中的冗余頂點(diǎn)，能夠較快地得出較優(yōu)的解。

1 圖的預(yù)備知識(shí)

圖G由一個(gè)有序的二元組G=組成，其中V為圖G的點(diǎn)集，E為圖G的邊集。對(duì)于?v∈V，e∈E，用V(v)表示頂點(diǎn)v所鄰接的頂點(diǎn)，用V(e)表示邊e連接的一組頂點(diǎn)。對(duì)于圖G中的邊集E={ei|ei∈E,i=1,2,…}中的ei一般可以分為有向邊和無(wú)向邊?；诖颂卣靼褕D分為兩類(lèi)：其邊沒(méi)有方向的圖稱(chēng)為無(wú)向圖，否則稱(chēng)為有向圖。本文僅考慮無(wú)向圖的增量問(wèn)題。對(duì)于一個(gè)傳統(tǒng)的圖，它的邊集滿(mǎn)足E?V×V，否則該圖就被定義為超圖。對(duì)于圖中的2個(gè)頂點(diǎn)vp、vq，如果存在一條邊同時(shí)與vp、vq相連，那么稱(chēng)頂點(diǎn)vp、vq是相鄰接的，若2條邊ep、eq同時(shí)關(guān)聯(lián)于同一個(gè)頂點(diǎn)，稱(chēng)此2條邊ep、eq是相鄰的。沒(méi)有邊關(guān)聯(lián)的頂點(diǎn)被稱(chēng)為孤立點(diǎn)。若一條邊關(guān)聯(lián)的2個(gè)頂點(diǎn)是相同的，那稱(chēng)此邊為環(huán)。

為了把一個(gè)圖結(jié)構(gòu)存儲(chǔ)于計(jì)算機(jī)中，其所具有的特性一般會(huì)通過(guò)圖的鄰接矩陣和關(guān)聯(lián)矩陣的形式來(lái)進(jìn)行計(jì)算機(jī)操作與處理。這兩種表示方法在表示相同圖時(shí)具有唯一性，并且同一個(gè)圖的鄰接矩陣與關(guān)聯(lián)矩陣之間可以進(jìn)行轉(zhuǎn)化。

設(shè)G=是簡(jiǎn)單無(wú)向圖，S為一個(gè)集合，S?V且S≠φ，若E中的每條邊都和S中的某個(gè)頂點(diǎn)相關(guān)聯(lián)，則S是G的頂點(diǎn)覆蓋集。對(duì)于上述的點(diǎn)覆蓋集合S，若對(duì)?vi∈S?V，有S-{vi}都不是點(diǎn)覆蓋集合，那么S就是G的極小頂點(diǎn)覆蓋集合。

對(duì)于求解頂點(diǎn)覆蓋問(wèn)題需要引出獨(dú)立集這個(gè)概念：集合I是V的非空子集，若I中任意兩個(gè)頂點(diǎn)都不相鄰，則I是圖G的獨(dú)立集。

2 極小頂點(diǎn)覆蓋問(wèn)題的增量算法

2.1 頂點(diǎn)覆蓋的增量問(wèn)題

當(dāng)給定圖的頂點(diǎn)或者邊數(shù)目發(fā)生增量變化時(shí)，原圖的極小頂點(diǎn)覆蓋集合是新圖點(diǎn)覆蓋集合的一個(gè)局部最優(yōu)解，因而需要將這個(gè)局部最優(yōu)解擴(kuò)展成為全圖的一個(gè)全局最優(yōu)解?？紤]到以下兩種情況：1)頂點(diǎn)的增加：當(dāng)新增加的頂點(diǎn)只與原頂點(diǎn)覆蓋集合中的頂點(diǎn)相連時(shí)，則更新后的頂點(diǎn)覆蓋集合保持不變；當(dāng)新增加的頂點(diǎn)只與非原點(diǎn)覆蓋集合中的頂點(diǎn)相連時(shí)，那么此時(shí)頂點(diǎn)覆蓋集合也要隨之發(fā)生變化，此時(shí)便需要在原點(diǎn)覆蓋集合的基礎(chǔ)上增加或者刪除若干個(gè)頂點(diǎn)；當(dāng)新增加的頂點(diǎn)既與原點(diǎn)覆蓋集合中的元素又與非原點(diǎn)覆蓋集合中的元素相連，那么可以不考慮新增加的點(diǎn)與原點(diǎn)覆蓋集中的點(diǎn)相連的邊。2)邊的增加：當(dāng)邊新加到原始圖中時(shí)，可以分為兩種情況，其一是該邊與原點(diǎn)覆蓋集合中的點(diǎn)相連，這種情況易知新圖的點(diǎn)覆蓋集合保持不變；其二是該邊只與非原點(diǎn)覆蓋集合中的點(diǎn)相連，這種情況下，則更新后的點(diǎn)覆蓋集合便需要考慮增加必要的頂點(diǎn)和刪除冗余的頂點(diǎn)，冗余的頂點(diǎn)即為不必要的頂點(diǎn)。

定理1設(shè)圖G=，頂點(diǎn)集為V={v1,v2,…,vi}，邊集為E，極小頂點(diǎn)覆蓋集合為N0，新加入頂點(diǎn)vi+1，若對(duì)?em∈E(vi+1)，都存在vm∈N0，使得em與vm相關(guān)聯(lián)，則N0不發(fā)生變化。

證明由題意可知，加入頂點(diǎn)vi+1，對(duì)?em∈E(vi+1)，都存在vm∈N0，使得em與vm相關(guān)聯(lián)，那么則有：當(dāng)m=1時(shí)，e1與頂點(diǎn)vi+1相關(guān)聯(lián)，即為新加入的邊，因?yàn)榇嬖趘1∈N0，使得e1與v1相關(guān)聯(lián)。根據(jù)頂點(diǎn)覆蓋的定義可知，邊e1已經(jīng)被頂點(diǎn)v1所覆蓋，而v1是N0中的頂點(diǎn)，那么可得N0已經(jīng)覆蓋了與vi+1關(guān)聯(lián)的一條邊e1。同理當(dāng)m=2時(shí)，可證N0已經(jīng)覆蓋了與vi+1關(guān)聯(lián)的一條邊e2。假設(shè)當(dāng)m=1，2，…，m時(shí)，N0已經(jīng)覆蓋了與vi+1關(guān)聯(lián)的一條邊em，下證當(dāng)m=m+1時(shí)成立。當(dāng)m=m+1時(shí)，em+1和頂點(diǎn)vi+1相關(guān)聯(lián)，em+1仍為新加入的邊，因?yàn)榇嬖趘m+1∈N0，使得em+1與頂點(diǎn)vm+1相關(guān)聯(lián)，且vm+1∈N0，那么可得N0已經(jīng)覆蓋了與vi+1關(guān)聯(lián)的邊em+1。綜上所述，加入頂點(diǎn)vi+1而導(dǎo)致增加的邊em此時(shí)均被原極小頂點(diǎn)覆蓋集合N0所覆蓋，所以更新后的圖結(jié)構(gòu)模型極小頂點(diǎn)覆蓋集合不發(fā)生變化。定理得證。

例1如圖1所示，已知圖G=，且它的其中一個(gè)極小頂點(diǎn)覆蓋集合為N0={v1,v4,v5}，如果新加入頂點(diǎn)為vi+1，利用上述定理求解更新后的極小頂點(diǎn)覆蓋集合Nnew。

由圖可以看出，新加入的頂點(diǎn)vi+1與非頂點(diǎn)覆蓋集合N0中的元素v2、v5相鄰接，求解步驟如下：

第一步先在原點(diǎn)覆蓋集合N0中分別加入頂點(diǎn)v2、v5；

第二步分別判斷與v2、v5相連的原N0中的頂點(diǎn)中是否存在冗余的頂點(diǎn)。對(duì)于和v2相鄰接的頂點(diǎn)有v1、v3，在比較過(guò)程中優(yōu)先刪去N0中度數(shù)較少的頂點(diǎn)。對(duì)于v1，與v1相連的所有的頂點(diǎn)是v2、v3，它們都屬于N0中的頂點(diǎn)，根據(jù)定理2，此時(shí)v1可以刪去。對(duì)于v3，與v3相連的所有的頂點(diǎn)為v1、v2、v4、v5，它們都屬于N0中的頂點(diǎn)，而刪去v1后，v3便不能再被刪去。對(duì)于v4，與v4相連的所有的頂點(diǎn)為v3、v5，它們都屬于N0中的頂點(diǎn)，因此根據(jù)定理2可以刪去頂點(diǎn)v4。則有Nnew1=N0+{v2}-{v1}+{v5}-{v4}={v2,v3,v5}；

第三步求得頂點(diǎn)覆蓋集合Nnew2=N0+{vi+1}={v1,v3,v4,vi+1}；

第四步計(jì)算并比較Nnew1與Nnew2集合中元素的個(gè)數(shù)，選取元素個(gè)數(shù)較少的集合為更新后的Nnew，更新后的極小頂點(diǎn)覆蓋集合為：Nnew=Nnew1={v2,v3,v5}。

定理3設(shè)圖G=，頂點(diǎn)集是V，邊集為E={e1,e2,…,ei}，極小頂點(diǎn)覆蓋集合是N0，新加入邊為ei+m，若對(duì)?ei+m都有?vm∈N0，使得ei+m與vm相關(guān)聯(lián)，則原極小頂點(diǎn)覆蓋集合N0不變化。

證明由題意知，當(dāng)加入邊ei+m時(shí)，都有?vm∈N0，使得ei+m與vm是相關(guān)聯(lián)的，那么則有：當(dāng)m=1時(shí)，ei+1作為新加入的邊與v1相關(guān)聯(lián)，而v1∈N0，根據(jù)頂點(diǎn)覆蓋的定義可知，邊ei+1已經(jīng)被頂點(diǎn)v1所覆蓋，而v1是N0中的頂點(diǎn)，那么可得N0已經(jīng)覆蓋了邊ei+1。同理當(dāng)m=2時(shí)，可證N0已經(jīng)覆蓋了邊ei+2。假設(shè)當(dāng)m=1,2,…,m時(shí)，N0已經(jīng)覆蓋了邊ei+m，下證當(dāng)m=m+1時(shí)成立。當(dāng)m=m+1時(shí)，邊ei+m+1仍為新加入的邊，已經(jīng)被頂點(diǎn)vm+1所覆蓋，且vm+1∈N0，因此原頂點(diǎn)覆蓋集合N0已經(jīng)覆蓋了圖G中新加入的邊ei+m+1。綜上所述，新加入的邊ei+m均已被原頂點(diǎn)覆蓋集合N0所覆蓋，即更新后的圖結(jié)構(gòu)模型的極小頂點(diǎn)覆蓋集合N0不發(fā)生變化。定理得證。

定理4設(shè)圖G=，頂點(diǎn)集是V，邊集為E={e1,e2,…,ei}，極小頂點(diǎn)覆蓋集合是N0，新加入邊為ei+1，若?vp,vq∈V-N0，使得ei+1與vp、vq同時(shí)相關(guān)聯(lián)，令V(ei+1)={vp,vq}，則有如下結(jié)論：

例2如圖2所示，G=，而且利用屬性約簡(jiǎn)的方法求出它的其中一個(gè)點(diǎn)覆蓋集合為N0={v1,v4,v5}，新加入邊ei+1，與頂點(diǎn)v3、v6相關(guān)聯(lián)，利用定理4求解更新后的頂點(diǎn)覆蓋集合Nnew。

由圖可以看出，新增加的點(diǎn)ei+1與頂點(diǎn)v3、v6建立了新的鄰接關(guān)系，求解步驟如下：

第一步依據(jù)定理4，把v3或者v6分別添加到點(diǎn)覆蓋集合N0中，然后分別考察與v3和v6相連的頂點(diǎn)；

第二步如果考慮把v3加入到點(diǎn)覆蓋集合中，那么與v3相連的頂點(diǎn)是v1、v4。對(duì)于v1，與v1關(guān)聯(lián)的所有頂點(diǎn)為v2、v3，其中v2是非N0中的元素，根據(jù)定理4，v1不能刪去。對(duì)于v4，與v4關(guān)聯(lián)的所有的頂點(diǎn)為v1、v2、v5、v6，其中v2、v6為非N0中的元素，因此v4不能刪去，可得Nnew1=N0+{v3}={v1,v3,v4,v5}；

第三步如果考慮把v6加入到點(diǎn)覆蓋集合中，那么與v3相連的頂點(diǎn)是v4、v5。對(duì)于v4，具上所述v4是不能刪去的。對(duì)于v5，與v5關(guān)聯(lián)的所有的頂點(diǎn)為v4、v6，均是原N0中的元素，因此v5可以刪去，可得Nnew2=N0+{v6}-{v5}={v1,v4,v6}；

第四步比較Nnew1與Nnew2集合中元素的個(gè)數(shù)，選取元素個(gè)數(shù)較少的集合為更新后的Nnew，更新后的頂點(diǎn)覆蓋集合為：Nnew=Nnew2=N0+{v6}-{v5}={v1,v4,v6}。

2.2 求解增量式頂點(diǎn)覆蓋的算法

在這一部分，我們?cè)O(shè)計(jì)了一種新型的求解增量式頂點(diǎn)覆蓋的算法。給定一個(gè)圖G=，它的鄰接矩陣A(G)是一個(gè)|V|×|V|的實(shí)對(duì)稱(chēng)矩陣，由鄰接矩陣相應(yīng)的能求出圖的關(guān)聯(lián)矩陣。它的極小頂點(diǎn)覆蓋集合是N0，從關(guān)聯(lián)矩陣中可以發(fā)現(xiàn)N0中的所有頂點(diǎn)已經(jīng)覆蓋了E中的所有元素。當(dāng)圖結(jié)構(gòu)發(fā)生增量變化時(shí)，它的極小頂點(diǎn)覆蓋集合變化情況分為以下3種情況：原頂點(diǎn)覆蓋集合不發(fā)生變化；原頂點(diǎn)覆蓋集合加入若干個(gè)必要的頂點(diǎn)；原頂點(diǎn)覆蓋集合添加若干個(gè)必要的頂點(diǎn)同時(shí)刪除屬于原頂點(diǎn)覆蓋集合中冗余的頂點(diǎn)。

算法1求解頂點(diǎn)增量變化極小頂點(diǎn)覆蓋集合

輸入：圖G=，極小頂點(diǎn)覆蓋集合為N0，其鄰接矩陣為A(G)；

輸出：新的圖結(jié)構(gòu)的極小頂點(diǎn)覆蓋集合Nnew。

對(duì)于j=1,2,…,m，新加頂點(diǎn)vi+j，令Vj={vi+j|j=1,2,…,m}；

步驟1判斷vi+j是否與N0中的頂點(diǎn)鄰接。如果與N0中的頂點(diǎn)鄰接或者沒(méi)有頂點(diǎn)與vi+j相鄰接，則Nnew1=N0。否則轉(zhuǎn)步驟2；

步驟3取Nnew=min{Nnew1,Nnew2,Nnew3,Nnew4|點(diǎn)覆蓋數(shù)最小}。

算法2求解邊的增量變化極小頂點(diǎn)覆蓋集合

輸入：圖G=，極小頂點(diǎn)覆蓋集合為N0，其鄰接矩陣為A(G)；

輸出：新的圖結(jié)構(gòu)的極小頂點(diǎn)覆蓋集合Nnew。

對(duì)于j=1,2,…,n，新加邊為ei+j；令Ej={ei+j|j=1,2,…,n}；

步驟1判斷ei+j是否與N0中的頂點(diǎn)關(guān)聯(lián)。若?vm∈N0，使得ei+1與vm是相關(guān)聯(lián)的，則Nnew1=N0；

步驟4取Nnew=min{Nnew1,Nnew2,Nnew3|點(diǎn)覆蓋數(shù)最小}。

上述兩個(gè)算法分別展示了與頂點(diǎn)的增量變化和邊的增量變化相對(duì)應(yīng)的算法。當(dāng)圖發(fā)生增量變化時(shí)，要明確區(qū)分是頂點(diǎn)的還是邊的增量變化或者兩者均有，以便調(diào)用相對(duì)應(yīng)的算法。算法1適用于圖結(jié)構(gòu)模型中頂點(diǎn)發(fā)生增量變化時(shí)的情況，算法2適用于圖結(jié)構(gòu)模型中邊發(fā)生增量變化時(shí)的情況。當(dāng)同時(shí)發(fā)生頂點(diǎn)和邊的增量變化時(shí)，把兩種情況拆分開(kāi)來(lái)，先考慮頂點(diǎn)的增量變化，調(diào)用算法1，再考慮邊的增量變化，調(diào)用算法2。本文算法1的時(shí)間復(fù)雜度為o(|Vj|)，算法2的時(shí)間復(fù)雜度為o(|Ej|)，算法的運(yùn)行時(shí)間的變化取決于新加入頂點(diǎn)與邊的數(shù)目，且隨頂點(diǎn)與邊的數(shù)目的增長(zhǎng)呈線(xiàn)性增長(zhǎng)。

3 實(shí)驗(yàn)對(duì)比

算法的仿真分析過(guò)程在Windows 10系統(tǒng)下進(jìn)行。計(jì)算機(jī)硬件配置是Radeon R52.40 GHz，4GRAM，用到的計(jì)算機(jī)處理程序是Matlab 2018a與python3.0。數(shù)據(jù)來(lái)源為計(jì)算機(jī)編碼生成的隨機(jī)無(wú)向圖。實(shí)驗(yàn)比對(duì)結(jié)果如表1、表2所示。

表1 圖的增量實(shí)驗(yàn)比對(duì)

表2 算法時(shí)間復(fù)雜度實(shí)驗(yàn)比對(duì)

表1中數(shù)據(jù)類(lèi)型分為增量前的極小頂點(diǎn)覆蓋數(shù)和增量后的極小頂點(diǎn)覆蓋數(shù)，算法運(yùn)行時(shí)間是在對(duì)各個(gè)數(shù)據(jù)運(yùn)行10次后取的平均運(yùn)行時(shí)間。利用python運(yùn)行算法時(shí)，第一次運(yùn)行會(huì)出現(xiàn)運(yùn)行時(shí)間較長(zhǎng)，故第一次運(yùn)行時(shí)間不取值，之后的運(yùn)行時(shí)間兩者差值基本上在0.5 ms內(nèi)。這里的準(zhǔn)確率代表算法運(yùn)行后所得到的極小頂點(diǎn)覆蓋集合是否有意義，如果所得到的極小頂點(diǎn)覆蓋集合能滿(mǎn)足其定義，可以覆蓋更新后圖結(jié)構(gòu)中的所有的邊，那么所得到的極小頂點(diǎn)覆蓋集合是準(zhǔn)確的。

另外我們通過(guò)實(shí)驗(yàn)數(shù)據(jù)檢驗(yàn)該算法相比非增量的算法是否更具有高效性，實(shí)驗(yàn)結(jié)果如表2所示。對(duì)其算法的時(shí)間復(fù)雜度分析發(fā)現(xiàn)，文獻(xiàn)[3]算法運(yùn)行時(shí)間在頂點(diǎn)數(shù)較少時(shí)會(huì)出現(xiàn)運(yùn)行時(shí)間為0的情況，但是隨著頂點(diǎn)數(shù)目的增加，算法運(yùn)行時(shí)間是明顯增加的，而本文算法運(yùn)行時(shí)間增加的速度更慢，因此本文算法相比文獻(xiàn)[3]算法更具有高效性。

算法首次模擬是對(duì)文章中例子的模擬，然后對(duì)頂點(diǎn)數(shù)和邊數(shù)進(jìn)行遞增實(shí)驗(yàn)，在表1中第3、4、5條數(shù)據(jù)集中采用了控制變量的方法，分別對(duì)只增加頂點(diǎn)、只增加邊、頂點(diǎn)和邊同時(shí)增加的情況進(jìn)行了研究。得到：只增加頂點(diǎn)而邊集不發(fā)生變化對(duì)極小頂點(diǎn)覆蓋集合沒(méi)有影響，只增加邊直接調(diào)用算法2進(jìn)行求解，頂點(diǎn)和邊同時(shí)增加需要調(diào)用算法1和算法2。本節(jié)的實(shí)驗(yàn)驗(yàn)證了本文算法的準(zhǔn)確性是較高的，算法求出的極小頂點(diǎn)覆蓋集合能夠滿(mǎn)足大規(guī)模圖發(fā)生增量變化時(shí)快速求解極小頂點(diǎn)覆蓋集合的需求。

4 結(jié)束語(yǔ)

本文針對(duì)于極小頂點(diǎn)覆蓋問(wèn)題的增量情況，從極小頂點(diǎn)覆蓋集合的定義出發(fā)，設(shè)計(jì)了求解頂點(diǎn)增量變化極小頂點(diǎn)覆蓋集合的算法以及求解邊的增量變化極小頂點(diǎn)覆蓋集合的算法。有效地解決了對(duì)于圖結(jié)構(gòu)發(fā)生增量變化的極小頂點(diǎn)覆蓋集合的更新問(wèn)題。隨著大數(shù)據(jù)時(shí)代的到來(lái)，數(shù)據(jù)的存儲(chǔ)量將是大規(guī)模的，該算法對(duì)于大型網(wǎng)絡(luò)監(jiān)控節(jié)點(diǎn)的動(dòng)態(tài)布置與重新確定圖結(jié)構(gòu)來(lái)求解出點(diǎn)覆蓋集合相比更具有高效性。