路和圈的定位控制集問(wèn)題.pdf

1、令G表示一個(gè)圖，V和E分別表示它的點(diǎn)集和邊集，r是一給定的正整數(shù)．定義Nr[X]={Y∈y(G)：d(x,y)≤r}，其中d(x,y）表示x和y在圖G上的距離，對(duì)于V的任何一個(gè)子集D，令Dr(x)=Nr[x]∩D.如果對(duì)于任何x∈V\D，Dr(x)，是非空的，則D是一個(gè)r-控制集，當(dāng)r=1時(shí)，D就是圖G的控制集.
　　 圖的控制集理論在組合優(yōu)化，編碼理論，計(jì)算機(jī)科學(xué)，通信網(wǎng)絡(luò)，監(jiān)視系統(tǒng)和社會(huì)網(wǎng)絡(luò)等領(lǐng)域有著重要的應(yīng)用，它已經(jīng)成為近

2、幾十年來(lái)圖論中發(fā)展最快的領(lǐng)域之一．隨著研究的深入，各種新的控制參數(shù)不斷涌現(xiàn)，其中圖的定位控制集就是在其基礎(chǔ)上被提出來(lái)的．圖的定位控制集已經(jīng)成為編碼理論中較活躍的研究方向，它在通訊網(wǎng)絡(luò)和監(jiān)視系統(tǒng)中有廣泛的應(yīng)用．
　　 如果在控制集的基礎(chǔ)上加入一定限制，對(duì)于任何x∈V\D，Dr(x)是非空的并且互不相同，則D是一個(gè)定位控制集．令表示G中最小定位控制集中的點(diǎn)數(shù)．
　　 對(duì)于圖G，找出它的最小定位控制集是十分困難的，即便是最簡(jiǎn)單