图上的游戏及匹配问题的研究

发布时间：2023-02-13 10:25

　　图上的游戏和匹配问题是图论研究的两个重要内容,它们不仅对认识图的性质和结构有重要作用,而且在计算机科学、组合最优化和信息论等方面有着广泛的应用.本文首先借助传统的组合博弈理论研究了两类图上的游戏,分别给出了这两类游戏的博弈结果和最优策略.然后,根据匹配覆盖图的性质和耳分解定理,对匹配覆盖图上的非可行边集进行分析,得到了关于匹配覆盖图上非可行边集的相关结论.主要研究内容如下:首先,研究了一类毛毛虫树上的正常2-染色游戏.基于Sprague-Grundy函数的基本理论,通过将较大图上的正常2-染色游戏分解成若干个较小图上的正常2-染色游戏,对一类毛毛虫树上的正常2-染色游戏进行分析.计算得到该游戏中所有游戏位置的Sprague-Grundy函数值,并且给出了这一类毛毛虫树上的正常2-染色游戏的最优策略.其次,分析了图上可能产生平局的SOS游戏.基于位置游戏的基本理论,通过对游戏参与者所作决策的分析,分别得到路和环上的SOS游戏的博弈结果和最优策略.之后,研究了完全二分图上的SOS游戏,得到该游戏的博弈结果是平局,并给出了最优策略.最后,根据路和环上的SOS游戏的结论,得到Petersen图...

【文章页数】：91 页

【学位级别】：博士

【文章目录】：
摘要
ABSTRACT
第1章 绪论
    1.1 课题背景及意义
    1.2 研究现状
        1.2.1 正常2-染色游戏
        1.2.2 SOS游戏
        1.2.3 匹配覆盖图
    1.3 主要内容
第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 环上的SOS游戏
    3.4 完全二分图上的SOS游戏
    3.5 Petersen图上的SOS游戏
    3.6 本章小结
第4章 匹配覆盖图上的非可行边集
    4.1 预备知识
    4.2 若干引理
    4.3 一类非可行边集的刻画
    4.4 一些特殊的非可行边集
    4.5 本章小结
结论
参考文献
攻读博士学位期间发表的论文及其他成果
致谢
个人简历



本文编号：3741857