学位论文 > 优秀研究生学位论文题录展示

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

作　者: 戚志如
导　师: 孙志人
学　校: 南京师范大学
专　业: 运筹学与控制论
关键词: 顶点着色色对策对策色数Ⅱ 轮图冠图 Mycielski图
分类号: O157.5
类　型: 硕士论文
年　份: 2005年
下　载: 62次
引　用: 0次
阅　读: 论文下载

内容摘要

自从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的对策色数,记为X_g(G),是使选手Alice有获胜策略的最小的t。 Chen,Schelp和Shreve在此基础上介绍了一种新的对策染色Ⅱ和对策色数Ⅱ,它是由色对策Ⅰ发展而来。如果对选手Bob再附加条件,就提出了一种新的对策着色,即图G的对策染色Ⅱ,这个条件是限制选手Bob,只能利用选手Alice已引入的颜色之一,除非他为保证图着色是正常的而不得不利用X中的一种新颜色。图G的对策色数Ⅱ是选手Alice在色对策染色Ⅱ中有一个获胜策略的最小的t,记为X_g~*(G)。色对策染色Ⅱ简称为色对策Ⅱ。本文比较了两种色对策之间的差异,讨论了图G的色对策Ⅱ的性质,对图的这种新的参数,利用顶点标号的方法,给出了Alice获胜的相应策略,并对几种特殊的图进行了讨论。本文前两章介绍了一些基本概念以及后面章节中要用到的基本引理.第三章给出了路图,圈图及其补图的对策色数Ⅱ,我们得到了:对n阶路P_n和n阶圈C_n分别有第四章主要讨论了与圈有关图的对策色数Ⅱ,给出了轮图,扇图和它的剖分图及其r-冠图的对策色数Ⅱ,我们得到:设n≥3,则对任何n+1阶扇图F_n和n+1阶轮图W_n分

全文目录

目录  3-4
摘要  4-6
Abstract  6-8
绪论  8-11
第一章：图论的基础知识  11-16
  §1．1 图、子图和树  11-12
  §1．2 同构、顶点着色  12-13
  §1．3 轮图、扇图和冠图、Mycielski图  13-16
第二章：基本引理及其证明  16-19
第三章：与路与圈有关图上的二人对策着色  19-24
  §3．1 路与圈上的二人对策着色及其对策色数  19-22
  §3．2 路与圈的γ-冠图上的二人对策着色及其对策色数  22-24
第四章：与轮图有关图上的二人对策着色  24-34
  §4．1 扇图与轮图上的二入对策着色及其对策色数  24-26
  §4．2 扇图与轮图的剖分图上的二人对策着色及其对策色数  26-30
  §4．3 扇图与轮图的γ-冠图上的二人对策着色及其对策色数  30-34
第五章：Mycielski图上的二人对策着色  34-39
  §5．1 完全图的Mycielski图上的二人对策着色及其对策色数  34-35
  §5．2 路与圈的Mycielski图上的二人对策着色及其对策色数  35-39
参考文献  39-41
致谢  41

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

内容摘要

全文目录

相似论文