圖論是計算機與組合數(shù)學的重要組成部分,它以圖為研究對象,在計算機理論、運籌學和機器學習等方面有著重要的研究價值�，F(xiàn)在,計算機的發(fā)展已經(jīng)成為推動各個學科發(fā)展的重要動力,由此,計算機的出現(xiàn)也大大推動了圖論的發(fā)展。圖標號起源于Rosa提出的優(yōu)美猜想,是圖論中的一個重要分支,并且具有廣泛的使用價值�，F(xiàn)實生活中的許多問題都可以抽象為圖標號問題,通過對圖標號進行理論分析,從而解決相關(guān)的問題。圖標號種類較多,其中研究較為廣泛的標號問題有優(yōu)美標號、幻類型標號、幸福標號�；妙愋蜆颂栔羞吇煤腿珮颂柡忘c幻和全標號研究較多,但是傳統(tǒng)的研究方法多采用組合構(gòu)造法,只能對結(jié)構(gòu)確定、有規(guī)律的圖進行證明。由于傳統(tǒng)的組合構(gòu)造法的局限性,并不能給出隨機圖的相關(guān)結(jié)論,為了對圖的邊幻和性進行全面研究,本文借助計算機的高運算能力以及優(yōu)化邊幻和全標號的傳統(tǒng)解空間的措施,采用了遞歸回溯的方法,設計了邊幻和全標號算法。對9個點內(nèi)的所有簡單連通圖進行了邊幻和全標號驗證,得到了9個點以內(nèi)所有連通圖的邊幻和全標號情況。由于隨著點數(shù)和邊數(shù)的增加,連通圖的數(shù)量呈指數(shù)級增長,并且由于解空間較為龐大,故選取17個點以內(nèi)的所有樹圖、16個點以內(nèi)的所有... 

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

【學位級別】：碩士

【文章目錄】：
摘要
Abstract
1 緒論
    1.1 選題背景及意義
    1.2 國內(nèi)外研究現(xiàn)狀
    1.3 主要研究內(nèi)容
    1.4 論文組織結(jié)構(gòu)
2 圖基礎理論概述
    2.1 圖的基礎理論
    2.2 圖標號相關(guān)概念
    2.3 標號研究現(xiàn)狀
    2.4 本章小結(jié)
3 邊幻和全標號
    3.1 算法設計
        3.1.1 邊幻和全標號的傳統(tǒng)空間
        3.1.2 邊幻和全標號的優(yōu)化空間
        3.1.3 邊幻和全標號空間對比
        3.1.4 邊幻和全標號的預判函數(shù)
        3.1.5 邊幻和全標號算法描述
    3.2 算法示例
    3.3 算法分析
    3.4 算法結(jié)果與猜想
        3.4.1 9個點以內(nèi)所有非同構(gòu)圖
        3.4.2 17個點以內(nèi)所有樹圖
        3.4.3 16個點以內(nèi)所有單圈圖
        3.4.4 15個點以內(nèi)所有雙圈圖
    3.5 本章小結(jié)
4 邊幻和全標號的公開問題解決
    4.1 邊幻和全標號全解算法
    4.2 邊幻和全標號模糊匹配算法
        4.2.1 預測序列預處理
        4.2.2 邊幻和全標號模糊匹配算法描述
    4.3 算法示例
    4.4 公開問題討論
    4.5 一些聯(lián)圖的證明
    4.6 本章小結(jié)
5 a,d-邊反幻和全標號
    5.1 a,d-邊反幻和全標號解空間
    5.2 算法設計
    5.3 算法示例
    5.4 算法分析
    5.5 算法結(jié)果
        5.5.1 有限點以內(nèi)的(a,d)-邊反幻全標號算法結(jié)果
        5.5.2 特殊圖的(a,d)-邊反幻全標號
    5.6 本章小結(jié)
結(jié)論
致謝
參考文獻
攻讀學位期間的研究成果
附錄A 各程序運行截圖及說明



本文編號：3659812