發(fā)布時間：2022-01-27 12:38

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

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

【文章頁數】：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中度數較少的頂點。對于v1，與v1相連的所有的頂點是v2、v3，它們都屬于N0中的頂點，根據定理2，此時v1可以刪去。對于v3，與v3相連的所有的頂點為v1、v2、v4、v5，它們都屬于N0中的頂點，而刪去v1后，v3便不能再被刪去。對于v4，與v4相連的所有的頂點為v3、v5，它們都屬于N0中的頂點，因此根據定理2可以刪去頂點v4。則

【參考文獻】：
期刊論文
[1]一種增量式約簡方法求解最小頂點覆蓋問題[J]. 占善華,謝小軍.  計算機應用研究. 2018(12)
[2]求解最小點覆蓋問題實例的計算成本的一種度量方法[J]. 王麗麗,崔晉川.  數學的實踐與認識. 2017(23)
[3]增量網絡監(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)工程與電子技術. 2004(04)

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



本文編號：3612504