圖的度量維數(shù)、邊度量維數(shù)和混合度量維數(shù)問題是圖論和組合優(yōu)化研究的重要問題,在貨幣稱重,網(wǎng)絡(luò)發(fā)現(xiàn)和驗(yàn)證,機(jī)器人導(dǎo)航,聲吶,藥物化學(xué)等領(lǐng)域有廣泛的應(yīng)用.設(shè)G＝（V,E）是一個(gè)圖,S是頂點(diǎn)集合V的一個(gè)非空子集.如果圖G中任意兩個(gè)元素（頂點(diǎn)或邊）可以被S中某個(gè)頂點(diǎn)區(qū)分,那么S稱為圖G的一個(gè)混合度量生成集.含有頂點(diǎn)最少的混合度量生成集的基數(shù)稱為圖G的混合度量維數(shù).求解圖的混合度量維數(shù)問題在一般情況下是NP-難問題.本文研究簡單連通圖的混合度量維數(shù)問題,設(shè)計(jì)了遺傳算法（GA）,給出了遺傳算法在Hamming圖、超立方體圖和圖G□Pm上的應(yīng)用結(jié)果,并分析指出在有些情況下得到的結(jié)果就是其混合度量維數(shù). 

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

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

【文章目錄】：
中文摘要
英文摘要
引言
第一章 預(yù)備知識
    1.1 圖的基本概念
    1.2 圖的度量維數(shù),邊度量維數(shù)和混合度量維數(shù)
    1.3 遺傳算法的基本原理
        1.3.1 編碼
        1.3.2 適應(yīng)度函數(shù)
        1.3.3 遺傳算子
        1.3.4 參數(shù)設(shè)定
第二章 圖的混合度量維數(shù)
    2.1 圖的混合度量維數(shù)問題
    2.2 遺傳算法流程圖
    2.3 遺傳算法的實(shí)現(xiàn)
第三章 一些特殊圖的混合度量維數(shù)
    3.1 Hamming圖的混合度量維數(shù)
    3.2 超立方體圖的混合度量維數(shù)
    3.3 圖G□P_m的混合度量維數(shù)
結(jié)論
參考文獻(xiàn)
致謝


【參考文獻(xiàn)】：
期刊論文
[1]應(yīng)用遺傳算法設(shè)計(jì)自動交會控制器[J]. 陳根社，陳新海.  西北工業(yè)大學(xué)學(xué)報(bào). 1994(02)



本文編號：3709114