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

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

【部分圖文】：

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

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

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

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

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

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

圖1網(wǎng)格圖與凸多胞形

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

本文編號(hào)：3981756