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

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

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

【文章目錄】：
摘要
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 預(yù)備知識
    2.2 端點(diǎn)被染色的路的Grundy-值
    2.3 三個(gè)端點(diǎn)被染色的T^n,i的Grundy-值
    2.4 兩個(gè)端點(diǎn)被染色的T^n,i的Grundy-值
    2.5 一個(gè)端點(diǎn)被染色的T^n,i的Grundy-值
    2.6 T^n,i上的正常2-染色游戲
    2.7 本章小結(jié)
第3章 圖上的SOS游戲
    3.1 預(yù)備知識
    3.2 路上的SOS游戲
    3.3 環(huán)上的SOS游戲
    3.4 完全二分圖上的SOS游戲
    3.5 Petersen圖上的SOS游戲
    3.6 本章小結(jié)
第4章 匹配覆蓋圖上的非可行邊集
    4.1 預(yù)備知識
    4.2 若干引理
    4.3 一類非可行邊集的刻畫
    4.4 一些特殊的非可行邊集
    4.5 本章小結(jié)
結(jié)論
參考文獻(xiàn)
攻讀博士學(xué)位期間發(fā)表的論文及其他成果
致謝
個(gè)人簡歷



本文編號：3741857