图上二人对策着色和对策着色数

图上二人对策着色和对策着色数

论文摘要

自从1991年H.L.Bodlaender在关于计算机科学中的图论专题讨论会上做了“关于某些色策略的计算复杂性”的专题报告,基于图的正常着色概念,首先引入图的对策着色的概念。所谓图的对策着色,如同两人(Alice和Bob)对弈,选手Alice试图给出图的正常顶点着色,而选手Bob则设法去阻止该事件的发生。设图G=(V,E)是n阶简单图,t是一个正的常数,X是t种颜色的集合,两个人在图G上对弈,选手Alice和Bob交替易手,最后完成对弈至多移动n步,每一步包括一名选手挑选一个尚未着色的顶点v,且从颜色集X中给它分配一种颜色α,使得α不同于已分配到v的邻点的颜色,若n步后图G被正常着色,则选手Alice获胜;若在该图的全部顶点被着色之前达成僵局,即对每一个尚未着色的顶点v和X中的每一种颜色α,v都与一个着α色的顶点相连,则Bob获胜。图G的对策色数,记为Xg(G),是使选手Alice有获胜策略的最小的t。 Chen,Schelp和Shreve在此基础上介绍了一种新的对策染色Ⅱ和对策色数Ⅱ,它是由色对策Ⅰ发展而来。如果对选手Bob再附加条件,就提出了一种新的对策着色,即图G的对策染色Ⅱ,这个条件是限制选手Bob,只能利用选手Alice已引入的颜色之一,除非他为保证图着色是正常的而不得不利用X中的一种新颜色。图G的对策色数Ⅱ是选手Alice在色对策染色Ⅱ中有一个获胜策略的最小的t,记为Xg*(G)。色对策染色Ⅱ简称为色对策Ⅱ。本文比较了两种色对策之间的差异,讨论了图G的色对策Ⅱ的性质,对图的这种新的参数,利用顶点标号的方法,给出了Alice获胜的相应策略,并对几种特殊的图进行了讨论。 本文前两章介绍了一些基本概念以及后面章节中要用到的基本引理.第三章给出了路图,圈图及其补图的对策色数Ⅱ,我们得到了:对n阶路Pn和n阶圈Cn分别有第四章主要讨论了与圈有关图的对策色数Ⅱ,给出了轮图,扇图和它的剖分图及其r-冠图的对策色数Ⅱ,我们得到:设n≥3,则对任何n+1阶扇图Fn和n+1阶轮图Wn分

论文目录

  • 目录
  • 摘要
  • Abstract
  • 绪论
  • 第一章:图论的基础知识
  • §1.1 图、子图和树
  • §1.2 同构、顶点着色
  • §1.3 轮图、扇图和冠图、Mycielski图
  • 第二章:基本引理及其证明
  • 第三章:与路与圈有关图上的二人对策着色
  • §3.1 路与圈上的二人对策着色及其对策色数
  • §3.2 路与圈的γ-冠图上的二人对策着色及其对策色数
  • 第四章:与轮图有关图上的二人对策着色
  • §4.1 扇图与轮图上的二入对策着色及其对策色数
  • §4.2 扇图与轮图的剖分图上的二人对策着色及其对策色数
  • §4.3 扇图与轮图的γ-冠图上的二人对策着色及其对策色数
  • 第五章:Mycielski图上的二人对策着色
  • §5.1 完全图的Mycielski图上的二人对策着色及其对策色数
  • §5.2 路与圈的Mycielski图上的二人对策着色及其对策色数
  • 参考文献
  • 致谢
  • 相关论文文献

    • [1].关于Kneser图的一个分数染色性质[J]. 甘肃高师学报 2016(12)
    • [2].图的点可区别的分数边染色数[J]. 数学的实践与认识 2017(19)
    • [3].站在多维的角度看世界[J]. 数字印刷 2018(07)
    • [4].伪-海临图的群色数[J]. 赤峰学院学报(自然科学版) 2016(17)
    • [5].扇、轮和完全图的r(2)点色数[J]. 甘肃联合大学学报(自然科学版) 2011(02)
    • [6].两类循环图的均匀色数[J]. 嘉兴学院学报 2011(03)
    • [7].图乘积的分数色数[J]. 泰山学院学报 2011(03)
    • [8].边共色数下图的分类问题[J]. 长春工业大学学报(自然科学版) 2011(06)
    • [9].联图的星色数[J]. 黑龙江科技学院学报 2011(06)
    • [10].图的b-边染色数及b-边连续性研究[J]. 吉林化工学院学报 2010(04)
    • [11].θ-图的对策着色和对策色数[J]. 中北大学学报(自然科学版) 2009(01)
    • [12].两种特殊冠图的相关分数色数研究[J]. 西安文理学院学报(自然科学版) 2009(01)
    • [13].升级手机的四大误区[J]. 广西质量监督导报 2009(05)
    • [14].循环图的均匀色数[J]. 吉林师范大学学报(自然科学版) 2009(03)
    • [15].单圈图的2-距离色数[J]. 甘肃科学学报 2009(03)
    • [16].弱直积图的2-距离色数[J]. 兰州理工大学学报 2009(05)
    • [17].几种特殊图形的分数色数研究[J]. 山西师范大学学报(自然科学版) 2008(04)
    • [18].两类特殊超图的分数色数[J]. 昆明学院学报 2008(04)
    • [19].与图的顶点染色数有关的几个问题[J]. 高师理科学刊 2016(03)
    • [20].几类特殊图的条件色数[J]. 山东科学 2012(04)
    • [21].球面经纬线图的分数色数[J]. 山西大同大学学报(自然科学版) 2010(01)
    • [22].完全立方Halin图的2-距离着色[J]. 重庆工商大学学报(自然科学版) 2010(02)
    • [23].广义θ-图的分数关联色数[J]. 重庆师范大学学报(自然科学版) 2010(06)
    • [24].图的星色数的两个结果[J]. 天津科技大学学报 2010(05)
    • [25].图的圆色数的一些结果(英文)[J]. Journal of Southeast University(English Edition) 2008(02)
    • [26].竞赛图弧色数的上界[J]. 运筹学学报 2015(02)
    • [27].Thomas数组的再发现[J]. 数学学习与研究 2019(20)
    • [28].几类平面图的集合色数[J]. 西昌学院学报(自然科学版) 2011(02)
    • [29].特殊平面图的集合色数[J]. 科技信息 2011(22)
    • [30].两类齿轮图的分数色数[J]. 青岛理工大学学报 2011(04)

    标签:;  ;  ;  ;  ;  

    图上二人对策着色和对策着色数
    下载Doc文档

    猜你喜欢