三維覆蓋控制及其在無線AD HOC網(wǎng)絡(luò)中的應(yīng)用研究.pdf

1、頂點覆蓋問題是圖論中的經(jīng)典組合優(yōu)化問題。已被證明是NP完備的,具有較高的計算復(fù)雜性。本文主要研究無權(quán)圖與加權(quán)圖的最大獨立集,目的是為了求解最小加權(quán)頂點覆蓋。論文主要研究工作和成果包括以下幾個方面:
　　首先,對無權(quán)圖的頂點覆蓋和獨立集進行了深入研究,在基于兩者關(guān)系的基礎(chǔ)上,得出結(jié)論,即在無權(quán)圖中,對于任意一個頂點判斷屬于獨立集比頂點覆蓋簡單。接著,在鄰接矩陣與獨立集自身特性的基礎(chǔ)上,設(shè)計了一種基于鄰接矩陣求解最大獨立集的算法,進而

2、解決最小頂點覆蓋。通過實驗驗證算法的時間復(fù)雜度和正確性。
　　其次,利用上述求解無權(quán)圖的方法,同樣從鄰接矩陣與獨立集自身特性入手,對加權(quán)圖進行分析,并結(jié)合改進傳統(tǒng)的貪婪算法,提出兩個概念集合,即鄰接集合和非鄰接集合,設(shè)計一種基于貪婪算法求解最大加權(quán)獨立集,進而求解最小加權(quán)頂點覆蓋。同樣通過實驗驗證算法的正確性和可行性。
　　最后,文中對最大加權(quán)獨立集在無線Ad hoc網(wǎng)絡(luò)分簇算法方面的應(yīng)用進行了研究。通過實驗,將最大加權(quán)獨立