發(fā)布時間：2024-05-25 05:13

　　設G=(V,E)是簡單連通圖,Π={S₁,S₂,…,S_k}是對頂點集V的一個劃分.頂點v∈V與非空頂點子集S■V的距離為■.頂點v∈V關于劃分Π的表征是一個k-維距離向量r_G(v|Π)=(d_G(v,S₁),d_G(v,S₂),…,d_G(v,S_k)).若對任意兩個頂點u,v∈V有r_G(u|Π)≠r_G(v|Π)成立,則每個頂點具有唯一的k-維向量表征,并稱Π是V的一個分辨劃分,簡稱圖G的分辨劃分.具有最小劃分數的分辨劃分為圖G的一個劃分基.劃分基所含頂點子集的個數為圖G的劃分度量維數,簡稱劃分維數.圖的分辨劃分及劃分維數問題是由Chartrand提出的一類NP-困難問題.本文基于遺傳算法研究一般圖的劃分維數計算問題,刻畫了圖的分辨劃分內在的拓撲結構;采用個體離散實值編碼技術,個體劃分分裂修補技術,設計了能夠計算圖的劃分維數和分辨劃分...

【文章頁數】：16 頁

【部分圖文】：

圖１爽１格＆與１＾．多胞形??Ｋｈｕｌｌｅｒ闕Ａｎｔｔｅｓｅｎ．關

陣為輸入，通過汁算圖的距離矩陣，首先利用算法３．３汁算網??格圖和凸多胞形的劃分度量維數，并將其對應的最優(yōu)分辨劃分集可視化，其次ｉ十算了??多個二維網格圖和凸多胞形的劃分維數，并提出了一個尚未解決間題．最后，基于翁??法３．３研究了隨機圖的劃分維數和頂點分類間題．算法運行環(huán)境為Ｗ....

圖３?＜３ｉ?（？?＝■?１００，?ｐ?＝?０．１）的分辨劃分??

武建、趙海霞，楊衛(wèi)華：？．翁ｊ遺傳算法的＿ｗ敢劃分度量維數計算??１０２５??６期??表２腐：法３．３＿隨機摩上的計算結潘??ｎ??Ｖ??ｐｄ??ｔｉｍｅ??１００??０．１??９??０．２３２２７??１００??０．２??９??０．３１０５２??１００??０．３??１０??０．２....

圖４?Ｇ２?（ｎ?＝?１００，?ｐ?＝?０．５）的分辨劃分??

１０２６??應用數學學報??４３卷??圖４?Ｇ２?（ｎ?＝?１００，?ｐ?＝?０．５）的分辨劃分??知＝｛Ｖ（Ｇ２）?－?〇氐｝．根據定理２．１，圖Ｇ的度量維數滿足ｄｉｍ（Ｇ３）?＜?９．??ｉ＝ｌ??參考文獻??［１］?Ｂｏｎｄｙ?Ｂ?Ａ，?Ｍｕｒｔｙ?Ｕ?Ｓ?Ｒ．?Ｇｒａｐｈ....

圖1網格圖與凸多胞形

4.1二維網格圖和凸多胞形的劃分維數計算與頂點分類Khuller等[13]和Andersen等[14]分別研究了網格圖的分辨集和最小加權分辨集問題.其中二維網格圖的頂點按照行,列規(guī)則排列.圖1(a)給出了一個6行,8列的二維網格圖.Imran等[15]研究了含有大量圈結構的凸多....

本文編號：3981756