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

摘要

自从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，记为X★a(G).色对策染色Ⅱ简称为色对策Ⅱ.本文比较了两种色对策之间的差异，讨论了图G的色对策Ⅱ的性质，对图的这种新的参数，利用顶点标号的方法，给出了Alice获胜的相应策略，并对几种特殊的图进行了讨论. 本文前两章介绍了一些基本概念以及后面章节中要用到的基本引理.第三章给出了路图，圈图及其补图的对策色数Ⅱ，我们得到了：对n阶路Pn和n阶圈Cn分别有X★g(P)={2,n≤53,n≥6x★g(Cn)=={2,n=43,n≠4第四章主要讨论了与圈有关图的对策色数Ⅱ，给出了轮图，扇图和它的剖分图及其r-冠图的对策色数Ⅱ，我们得到：设n≥3，则对任何n+1阶扇图Fn和n+1阶轮图Wn分别有对扇图剖分图Qn和轮图剖分图Gn分别有x★g(Qn)=3；x★g(Gn)=3；对n+1阶轮图Wn的r-冠图Ir(Wn)和n+l阶扇图R的r-冠图Ir(R)分别有第五章讨论了Mycielski图上的二人对策着色，并且给出了Alice获胜的相应策略.我们给出了n阶完全图的对策色数Ⅱ为n+1；完全二部图的对策色数Ⅱ为3；对n阶路Pn的Mycielski图，我们有 最后给出了n阶圈Cn的Mycielski图的对策色数Ⅱ的猜想，对于n≥5时，圈Cn的Mycielski图的对策色数Ⅱ为4.

目录

学位论文独创性声明和使用授权声明

摘要

绪论

第一章 图论的基础知识

§1.1图、子图和树

§1.2同构、顶点着色

§1.3轮图、扇图和冠图、Mycielski图

第二章 主要的引理及其证明

第三章 与路与圈有关图上的二人对策着色

§3.1路与圈上的二人对策着色及其对策色数

§3.2路与圈的r-冠图上的二人对策着色及其对策色数

第四章 与轮图有关图上的二人对策着色

§4.1扇图与轮图上的二人对策着色及其对策色数

§4.2扇图与轮图的剖分图上的二人对策着色及其对策色数

§4.3扇图与轮图的r-冠图上的二人对策着色及其对策色数

第五章 Mycielski图上的二人对策着色

§5.1完全图的Mycielski图上的二人对策着色及其对策色数

§5.2路与圈的Mycielski图上的二人对策着色及其对策色数

参考文献

致谢