設(shè)G=（V,E）為圖.頂點(diǎn)v稱為是區(qū)分元素（頂點(diǎn)和邊）x和y的,如果d（x,v）≠d（y,v）,這里d（x,v）,d（y,v）分別表示元素x,y與頂點(diǎn)v之間的距離.頂點(diǎn)集V的一個(gè)子集W稱為G的一個(gè)混合度量生成集,如果對(duì)G的任意兩個(gè)元素x,y,都存在頂點(diǎn)v∈W使得v區(qū)分x,y.含有最少元素的混合度量生成集的基數(shù)稱為圖G的混合度量維數(shù).圖的混合度量維數(shù)問(wèn)題是圖論與組合優(yōu)化中的一個(gè)重要問(wèn)題.確定圖的混合度量維數(shù)是一個(gè)NP-難問(wèn)題,因此對(duì)大規(guī)模求解混合度量維數(shù)的實(shí)例,我們需要考慮它的有效算法.本文給出了兩種關(guān)于該問(wèn)題的整數(shù)線性規(guī)劃模型,設(shè)計(jì)了混合度量維數(shù)問(wèn)題的變鄰域搜索算法,并利用此算法給出了一些圖的混合度量維數(shù)的界. 

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

【文章頁(yè)數(shù)】：38 頁(yè)

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

【部分圖文】：

圖1

sun圖

4


本文編號(hào)：3257253