圖的邊度量維數(shù)問題是圖論和組合優(yōu)化研究的重要問題之一,越來越多的領(lǐng)域涉及此問題,包括網(wǎng)絡(luò)發(fā)現(xiàn)與核實、機(jī)器人導(dǎo)航和化學(xué)等.設(shè)G＝（V,E）是一個簡單連通圖,頂點子集B（?）V,如果圖G的任意兩條邊被B中某些頂點區(qū)分,則稱B是圖G的邊度量生成集.圖G中基數(shù)最小的邊度量生成集稱為邊度量基;邊度量基的基數(shù)稱為邊度量維數(shù).求解圖的邊度量維數(shù)問題在一般情況下是NP-難問題.本文研究了圖的邊度量維數(shù)問題,給出了整數(shù)線性規(guī)劃模型,設(shè)計了變鄰域搜索算法,得到了變鄰域搜索算法在Hamming圖、超立方體圖和默比烏斯梯圖上的應(yīng)用結(jié)果. 

【文章來源】：河北師范大學(xué)河北省

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

【學(xué)位級別】：碩士

【部分圖文】：

基本變鄰域搜索算法

必要性如果∑1=1∑=+1=0,則=0,對任意的1<.由于∑=1(,),·1,存在至少一個使得(,)=(,),則由定義知′是一個邊度量生成集.限制條件(2.6)保證了|′|=,定理即證.2.2算法流程和實現(xiàn)本節(jié)介紹求解問題的具體算法.根據(jù)1.3.4節(jié)給出的一般變鄰域搜索算法的基本步驟,先給出求解問題的算法流程圖,然后對算法進(jìn)一步分析.我們給出邊度量維數(shù)問題的變鄰域搜索算法的流程圖(見圖2.2).下面進(jìn)一步分析算法.(1)初始解構(gòu)造.一般初始解的生成可以通過隨機(jī)生成或者由經(jīng)驗和其他算法得到,對于邊度量維數(shù)問題的初始解的構(gòu)造,從空集開始,依次隨機(jī)選取中的一個頂點添加到中,直到為邊度量生成集.(2)鄰域結(jié)構(gòu).由事實可知不同的鄰域結(jié)構(gòu)會得到不同的可行解,一個鄰域結(jié)構(gòu)內(nèi)的最優(yōu)解不一定是另一個鄰域結(jié)構(gòu)的最優(yōu)解,為了使得到的解更接近于最優(yōu)解,因此依據(jù)不同的問題要設(shè)計不同的鄰域結(jié)構(gòu).對于邊度量維數(shù)問題,我們可以通過交換集合中的個元素得到需要的鄰域.例如,當(dāng)=1,={1,2,3,4,5},={1,2,3},={4,5},1()={{4,2,3},{1,4,3},{1,2,4},{5,2,3},{1,5,3},{1,2,5}},即1()為用中的一個元素替換中的一個元素得到的新集合所構(gòu)成的一個集合.=1時鄰域構(gòu)造可以用圖2.1表示.圖2.1:鄰域構(gòu)造(=1時)顯然,小于或等于||.不難發(fā)現(xiàn),隨著的增大鄰域結(jié)構(gòu)的基數(shù)不斷增大,即||=()·()<(+1)·(+1)=|+1|,<21+2.13

3.2超立方體圖本節(jié)首先介紹超立方體圖,接著給出由變鄰域搜索算法得到的一些結(jié)果.當(dāng)Hamming圖,中=2時即為超立方體圖,中兩個頂點的距離是對應(yīng)不同坐標(biāo)分量的個數(shù).顯然有2個頂點,·21條邊.圖3.1:超立方體圖引理3.1[24]對于-正則圖,dim()1+log2.利用第二章設(shè)計的變鄰域搜索算法,求解超立方體圖的邊度量維數(shù)得到一些結(jié)果,見表3.2,其中表3.2的構(gòu)造與表3.1相同.表3.2:超立方體圖的算法結(jié)果||||()38123,5,830.372416326,13,1630.674532806,16,23,3042.9196641929,18,34,58,62520.65671284484,33,65,98,114,1226244.106825610241,7,27,150,169,2536328.794由表3.2,我們可以知道dim(3)3,因為3為三正則圖,由引理3.1可知dim(3)1+log23,又log23=2,所以有dim(3)=3,即算法得到的邊度量生成集就是邊度量基.3.3默比烏斯梯梯圖本節(jié)首先應(yīng)用算法得到默比烏斯梯圖的一些結(jié)果,然后應(yīng)用組合方法給出默比烏斯梯圖的邊度量維數(shù)的界,并與算法得到的結(jié)果進(jìn)行對比.定義3.2[17]設(shè)圈=(,),5.默比烏斯梯梯圖的頂點集為,兩個頂點與之間有邊當(dāng)且僅當(dāng)兩個頂點,在圈中的距離等于圈的直徑.22

【參考文獻(xiàn)】：
期刊論文
[1]變鄰域搜索算法綜述[J]. 董紅宇,黃敏,王興偉,鄭秉霖.  控制工程. 2009(S2)



本文編號：3608552