圖上的游戲和匹配問題是圖論研究的兩個重要內(nèi)容,它們不僅對認識圖的性質(zhì)和結構有重要作用,而且在計算機科學、組合最優(yōu)化和信息論等方面有著廣泛的應用.本文首先借助傳統(tǒng)的組合博弈理論研究了兩類圖上的游戲,分別給出了這兩類游戲的博弈結果和最優(yōu)策略.然后,根據(jù)匹配覆蓋圖的性質(zhì)和耳分解定理,對匹配覆蓋圖上的非可行邊集進行分析,得到了關于匹配覆蓋圖上非可行邊集的相關結論.主要研究內(nèi)容如下:首先,研究了一類毛毛蟲樹上的正常2-染色游戲.基于Sprague-Grundy函數(shù)的基本理論,通過將較大圖上的正常2-染色游戲分解成若干個較小圖上的正常2-染色游戲,對一類毛毛蟲樹上的正常2-染色游戲進行分析.計算得到該游戲中所有游戲位置的Sprague-Grundy函數(shù)值,并且給出了這一類毛毛蟲樹上的正常2-染色游戲的最優(yōu)策略.其次,分析了圖上可能產(chǎn)生平局的SOS游戲.基于位置游戲的基本理論,通過對游戲參與者所作決策的分析,分別得到路和環(huán)上的SOS游戲的博弈結果和最優(yōu)策略.之后,研究了完全二分圖上的SOS游戲,得到該游戲的博弈結果是平局,并給出了最優(yōu)策略.最后,根據(jù)路和環(huán)上的SOS游戲的結論,得到Petersen圖...

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

【學位級別】：博士

【文章目錄】：
摘要
ABSTRACT
第1章 緒論
    1.1 課題背景及意義
    1.2 研究現(xiàn)狀
        1.2.1 正常2-染色游戲
        1.2.2 SOS游戲
        1.2.3 匹配覆蓋圖
    1.3 主要內(nèi)容
第2章 樹上的正常2-染色游戲
    2.1 預備知識
    2.2 端點被染色的路的Grundy-值
    2.3 三個端點被染色的T^n,i的Grundy-值
    2.4 兩個端點被染色的T^n,i的Grundy-值
    2.5 一個端點被染色的T^n,i的Grundy-值
    2.6 T^n,i上的正常2-染色游戲
    2.7 本章小結
第3章 圖上的SOS游戲
    3.1 預備知識
    3.2 路上的SOS游戲
    3.3 環(huán)上的SOS游戲
    3.4 完全二分圖上的SOS游戲
    3.5 Petersen圖上的SOS游戲
    3.6 本章小結
第4章 匹配覆蓋圖上的非可行邊集
    4.1 預備知識
    4.2 若干引理
    4.3 一類非可行邊集的刻畫
    4.4 一些特殊的非可行邊集
    4.5 本章小結
結論
參考文獻
攻讀博士學位期間發(fā)表的論文及其他成果
致謝
個人簡歷



本文編號：3741857