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

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

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

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

【部分圖文】：

圖1

sun圖

4


本文編號：3257253