頂點覆蓋問題在圖論中是一個經(jīng)典的組合優(yōu)化問題,并且在實際問題中有非常廣泛的應用。針對大規(guī)模圖頂點數(shù)目增加、邊數(shù)目增加和頂點與邊數(shù)目均增加3種動態(tài)過程,設(shè)計了能夠在原極小頂點覆蓋集合的基礎(chǔ)上更新增量后圖的極小頂點覆蓋集合的算法。提出的算法考慮了圖結(jié)構(gòu)中頂點與邊的關(guān)系,并采用鄰接矩陣的方法對其進行存儲,在圖結(jié)構(gòu)發(fā)生增量變化后,在原極小點覆蓋集合的基礎(chǔ)上添加或者刪除若干頂點來更新增量后的極小頂點覆蓋集合。實驗結(jié)果驗證了算法的準確性和高效性。 

【文章來源】：北京信息科技大學學報(自然科學版). 2020,35(05)

【文章頁數(shù)】：6 頁

【部分圖文】：

邊增量變化實例

尤攵サ?vp，考慮到需要在原頂點覆蓋集合中刪除不必要的頂點，只需證明刪除的頂點是冗余的。因為vi+1與vp相鄰接，并且?v"p∈V(vp)且v"p∈N0，那么所有和vp相鄰接的并且屬于原極小頂點覆蓋集合N0的頂點即為v"p，而由題意，與v"p相連的若干個頂點都屬于原N0，即對于?e∈E(v"p)，都有e被點覆蓋集合N0中的頂點所覆蓋，那么此時v"p是可以刪去的，即v"p為冗余的得證，否則頂點v"p不能被刪去。例1如圖1所示，已知圖G=＜V，E＞，且它的其中一個極小頂點覆蓋集合為N0={v1，v4，v5}，如果新加入頂點為vi+1，利用上述定理求解更新后的極小頂點覆蓋集合Nnew。由圖可以看出，新加入的頂點vi+1與非頂點覆蓋集合N0中的元素v2、v5相鄰接，求解步驟如下:第一步先在原點覆蓋集合N0中分別加入頂點v2、v5;第二步分別判斷與v2、v5相連的原N0中的頂點中是否存在冗余的頂點。對于和v2相鄰接的頂點有v1、v3，在比較過程中優(yōu)先刪去N0中度數(shù)較少的頂點。對于v1，與v1相連的所有的頂點是v2、v3，它們都屬于N0中的頂點，根據(jù)定理2，此時v1可以刪去。對于v3，與v3相連的所有的頂點為v1、v2、v4、v5，它們都屬于N0中的頂點，而刪去v1后，v3便不能再被刪去。對于v4，與v4相連的所有的頂點為v3、v5，它們都屬于N0中的頂點，因此根據(jù)定理2可以刪去頂點v4。則

【參考文獻】：
期刊論文
[1]一種增量式約簡方法求解最小頂點覆蓋問題[J]. 占善華,謝小軍.  計算機應用研究. 2018(12)
[2]求解最小點覆蓋問題實例的計算成本的一種度量方法[J]. 王麗麗,崔晉川.  數(shù)學的實踐與認識. 2017(23)
[3]增量網(wǎng)絡(luò)監(jiān)測點的增量選取算法[J]. 丁三軍,陶興宇,石祥超,徐蕾.  計算機應用. 2015(12)
[4]基于最短路算法的最小點覆蓋問題[J]. 寇磊,崔笑川,陳京榮.  蘭州交通大學學報. 2015(04)
[5]廣義Petersen圖的最小點覆蓋集[J]. 鄭文萍,郭炳,楊貴.  山西師范大學學報(自然科學版). 2014(01)
[6]圖的最小頂點覆蓋的粘貼DNA計算模型[J]. 聶曉艷,耿俊,湯建鋼.  首都師范大學學報(自然科學版). 2013(01)
[7]一種求解平面圖的最小頂點覆蓋算法[J]. 吳春,朱國魂,謝玉忠,林宏.  計算機系統(tǒng)應用. 2010(09)
[8]最小頂點覆蓋問題的DNA分子算法[J]. 高琳,許進.  系統(tǒng)工程與電子技術(shù). 2004(04)

碩士論文
[1]分布式系統(tǒng)日志數(shù)據(jù)采集關(guān)鍵技術(shù)研究與實現(xiàn)[D]. 陶興宇.沈陽航空航天大學 2016



本文編號：3612504