（运筹学与控制论专业论文）图上二人对策着色和对策着色数.pdf

学位论文独创性声明 本人郑重声明： 1 、坚持以t t 求实、创新”的科学精神从事研究工作 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究 成果 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已 经发表或撰写过的研究成果 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示 了谢意 作者签名：应垒 日期：堕：点1 8 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论 文进人学校图书馆被查阅；有权将学位论文的内容编人有关数据库进 行检索；有权将学位论文的标题和摘要汇编出版保密的学位论文在 解密后适用本规定 作者签名：趣鸯：查 日期 町。j 。8 摘要 自从1 9 9 1 年日l b o d l a e n d e r 在关于计算机科学中的图论专题讨论会上做了“关于 某些色策略的计算复杂性”的专题报告，基于图的正常着色概念，首先引入图的对策着 色的概念，所谓图的对策着色，如同两人( a l i c e 和b o b ) 对弈，选手a l i c e 试图给出图的 正常顶点着色，而选手b o b 则设法去阻止该事件的发生设图g = ( ke ) 是扎阶简单 图，t 是一个正的常数，x 是t 种颜色的集合，两个人在图g 上对弈，选手a l i c e 和 b o b 交替易手，最后完成对弈至多移动礼步，每一步包括一名选手挑选一个尚未着色的 顶点u ，且从颜色集x 中给它分配一种颜色，使得。不同于已分配到 的邻点的颜 色，若n 步后图g 被正常着色，则选手a l i c e 获胜；若在该图的全部顶点被着色之前达 成僵局，即对每一个尚未着色的顶点 和x 中的每一种颜色c l ，口都与一个着q 色的 顶点相连，则b o b 获胜，图g 的对策色数，记为x g ( g ) ，是使选手a l i ，e 有获胜策略的 最小的t c h e n ，s c h e l p 和s h r e v e 在此基础上介绍了一种新的对策染色n 和对策色数，它 是由色对策i 发展而来如果对选手b o b 再附加条件，就提出了一种新的对策着色，邵 图g 的对策染色，这个条件是限制选手b o b ，只能利用选手a l i c e 已引入的颜色之一， 除非他为保证图着色是正常的而不得不利用x 中的一种新颜色图g 的对策色数是 选手a l i c e 在色对策染色中有一个获胜策略的最小的t ，记为赡( g ) 色对策染色n 简 称为色对策本文比较了两种色对策之间的差异，讨论了图g 的色对策的性质，对 图的这种新的参数，利用顶点标号的方法，给出了a l i c e 获胜的相应策略，并对几种特 殊的图进行了讨论 本文前两章介绍了一些基本概念以及后面章节中要用到的基本引理第三章给出了 路图，圈图及其补图的对策色数，我们得到了：对n 阶路r 和n 阶圈g 分别有 f2 n ， 则瑶( g ) = x ( g ) = m 引理2 3 设g = ( ke ) 是具有分划k 和坞的连通二部图，则x ：( g ) = 2 ，当且仅 当存在u v ，使得飓m = v ，即对某个口k ，j v ( u ) = k ，其中“j ) = l ，2 ) 证明：易知充分性成立，只需证明必要性 反设不存在口k ，使得n ( v ) = k ，由于g 是连通图，任意两点都有路援连，在a l i c e 选点着色后，不妨设此顶点秒v ，由假设知( o ) k ，存在乱k ，使得u - e n ( v ) ，b o b 选 “着色，这样同一种颜色出现在两个分划中，从而要完成着色，至少引进三种颜色，矛盾， 引理2 4 设g 是完全7 2 - 部图，则( g ) = m 证明：由引理2 , 2 即得 1 4 3 v v ( t ) 使2 f l l = v ( t ) 其他 引理2 6 设g 一( k ，k ，v 二；司是完全m 一部图，i v , i = l i 则焉( e ( g ) ) m a x h ，i = 1 ，2 ，m ) 证明：注意到： c ( a ) = k 。u k t 。u u 垃。， 且y ( 硒。) nv ( k i ，) = 咖，i j ，由引理2 1 与引理2 4 即得证 引理2 7g 于：y - n 阶完全图，有瑶( 甄) = 露， 证明t 由对策着色1 1 的定义直接可得 引理2 8 若d 2 且为整数，则焉( g 掣) ) = 2 ， 证明：注意到：g 尹皇d k 2 由引理2l ，引理2 4 ，引理2 7 - 7 9 羽：x ；( g ) ) = 2 引理2 9 若h 是g 的支撑子图，则( 日) ( g ) 推论2 1 0 若图g 中含有圈g 4 ) ，则艺( g ) 23 证明：设g 4 ) 是图g 的最长圈，若n = 3 ，则结论成立，由此，可设n 5 在对策过程中： ( 1 ) 若a l i c e 首先在圈c k 上选择点盈着i 色，则b o b 为阻碍a l i c e 着色，随即也在圈 g 选择点x i + 3 或x i 一3 着色i ，这样就构成了一个长度为3 的i 色区间； ( 2 ) 若b o b 首先在圈g 上选择点着i 色，则： ( 2 1 ) a l i c e 也在圈上选择点着色i ，这样由( 1 ) 就可得到一个长度为3 的i 色区间； 1 5 ( 2 2 ) a l i c e 不在圈上选择点着色i ，这样b o b 就选择点x i + 3 或z t 一3 着色i ，这样也构 成了一个长度为3 的i 色区间； 注意到这些i 色区间的长度d i = 3 ，其问有两个内点，它们至少需要另外两种颜色着色， 从而略( g ) 3 ， 1 6 第三章与路与圈有关图上的二人对策 3 1 路与圈上的二人对策着色及其对策色数 定理3 1 1 设p n 是1 1 阶路2 ) ，则有 碌咖隹墨 瑶( c ( p n ) ) = f ；1 证明：路p n 是树，由弓l ：g - 2 5 知 奶，= r 墨 下面我们证明x ( g ( p n ) ) = ；1 若n 为偶数， y ( e ( p n ) ) 可划分成2 = 个不相交的极大独立集，且每个极大独 立集中顶点的个数为2 ，由引理2 2 知： x ；( e ( r ) ) = ；= ；1 ；若n 为奇数，y ( e ( r ) ) 可划分成一个单点集和i 罟j 个不相交的极大独立集，且这些极大独立集中顶点的的个数 至多为2 ，由引理2 2 知：( e ( r ) ) = 【；j + i = - i 所以( e ( r ) ) 一f 孙 从而 ( c ( p n ) ) = f 争 1 7 定理3 1 2 设c j 为礼阶圈3 ) ，则有 礤啦r 象 拟g ) ) ： 1 ，”3 ， i 2 2 1 ，n 4 证明：当n = 3 时，风是完全图，x t ( 虬) = 3 当扎= 4 时，不妨设c 4 = z 1 x 2 2 ：3 x 4 x l ，且z l 为i 步点，因为。2 和。4 都与2 l 梗关 联，选手b o b 只能选取乳着色1 ，由于x 2 和z 4 相互独立，故皆可着色2 ，所以赡( q ) = 2 下面证明n25 时，a l i c e 以任何点作为i 步点着色l ，然后选手b o b 和a l i c e 轮流 选择可用1 色正常着色的顶点，并当着色l 的过程结束时，任何1 色区间的长度d l 3 ， 否则不妨设。l x 2 x 3 x 4 2 7 5 构成长度为4 的l 色区间p 1 。l ，3 7 5 1 ，其内点。2 ，z 3 ，x 4 均未着 色，则z 。可着色1 ，矛盾由于g 为圈，所以各个1 色区间耜互独立，我们考虑一个l 色区间，由于任何任何l 色区间的长度d l 冬3 ，每个1 色区间至多含有2 个内点，再引 进两种颜色即可完成色对策，所以n 5 时，砭( c n ) 3 下面证明n 5 时，x ：( c 。) 3 ，不妨设z 1 作为i 步点，即( z 1 ) = 1 ，选手b o b 为阻碍选手a l i c e 的着色可选且令p b ) = 1 ，则z 2 ，x 3 p l 陋1 ，z 4 i 这样必须引 进两种颜色才可使z 2 ，& 着色，所以砭( g ) 3 由上可知； 矧g ) ： 2 1 4 ， 【3 ， 他4 下面证明当n = 3 时，c ( 巳) = 1 ，否则，( c ( g ) ) = ；1 当n = 3 时，c ( c 3 ) = g ( 妫) 是空图，( c 3 ) ) = 1 当n 4 时，若n 为偶数，y ( c ( a ) ) 可射分成； 个不相交的极大独立集，且 每个极大独立集中顶点的个数为2 ，由引理2 2 知：磁( g ( g ) ) = ；1 ；若n 为奇数。 y ( c ( g ) ) 可划分成一个单点集和【割个不相交的独立集，且这些极大独立集中顶点的 的个数至多为2 ，由引理2 2 知：x ：( e ( c ) = 【割+ l = f 1 8 所以x ；( c ( g ) ) = 嘲 从而 矧e ( 2 推论3 1 3 若d 22 且为整数，则x ( g 1 ) ) = 3 证明：注意到g 挚“是一个奇圈 由定理3 1 ，2 ，可知磁( g 炉1 ) ) = 3 推论3 1 。4 若整数盎4 ，则( g ) = f 訇。 证明：注意到g = g ( 仉) ，由定理3 1 2 可知，( g 5 ) = ； 定理3 1 5 设整数啦3 ，( i = 1 ，2 ，一，r ) ，则 x ；c r c k ，= x ；p g ；，= x ：c r c k ，= ；姜i ? 证明：对于瞄( r 巴) 由引理2 , 1 和定理3 1 2 即得 对于x ；( r g 。) 和x ；( r g 。) 开始时只要选手a l i c e 选择所有圈的公共点：g o 作为 i 步点，且妒 ( z o ) = 1 ，以下证明类似于定理3 1 2 的证明方法，故略 定理3 1 6 设g 是有m 个圈g ，i s = ( 1 ，2 ，m ) 组成的链环图，其 中口的阶心4 ，则姘( g ) = 3 证明：开始时无论选手a l i c e 选择何点着色，随后选手b o b 都可以选择一点与之形 成路p 4 ，并于之着相同的颜色，从而e ( g ) 3 现在选手a l i c e 选撂任何一点w v ( g ) 作为i 步点且m ( 口) = 1 ，然后选手b o b 和 选手a l i c e 轮流选择点且着色l ，当这过程结束时，所有的1 色点形成g 的一个极大 独立集s ，此时对任意点让y ( g ) ，中必有一点u 有妒) = 1 ，否则u 可着色1 且 s u u ) 是g 的一个独立集，这于s 的极大性矛盾注意到g 的最大度为4 ，且只有在 圈上的公共点的度是4 ，其他顶点的度为2 ，所以g 中肖来着色的顶点集合的导出子图 1 9 ，j 4 朝 眨 n f c v s 1 的各个连通分支或是孤立点，或是恐或是k i ，2 ，或是k i 3 ，由引理2 1 和弓 理2 2 可知，它们至多需要两种新色，从而( g ) 3 所以x ；( g ) = 3 3 2 路与圈的r 冠圉上的二人对策着色及其对策色数 定理3 2 1 设( r ) 是礼阶路r 的r - 冠图，则 删驯= ：蓦 证明：因为n 阶路最的r - 冠图0 ( r ) 仍然是树，由引理2 5 易知结论成立 定理3 2 2 设( g ) 是n 阶圈g 的r 冠图，则) ( ：( ( g ) ) = 3 证明：当礼= 3 时，对于岛( 即3 阶完全图) 的r 冠图，易证结论成立 以下假设n 4 ，设c k = x l x 2 x 3 x n z l 且x ：，磁，砩是l ( g ) 中相 应于圈上顶点z l ，。2 ，z 。的悬挂点集，色对策开始时，无论选手a l i c e 选择何点 u y ( ( g ) ) 作为i 步点并着色o ，随后选手b o b 都可以选择一点口矿( ( & ) ) 着色 a ，使得o l 色区间p n 阻，”】的长度d 。= 3 从而有( ，r ( g ) ) 3 为证明也( l ( g ) ) 3 ， 只需证明( g ) 至多利用三种颜色即可完成色对策 开始时，选手a l i c e 在圈g 上任取一点，不妨设z l 作为i 步点，( z 1 ) = 1 随 后，选手b o b 和选手a l i c e 交替地选择顶点并着色1 的对策过程如下： ( 1 ) 选手a l i c e 依据选手b o b 对着1 色顶点的挑选：只在圈g 上适当的选择顶点 着色1 且选手a l i c e 不首先对圈上的顶点引入新色 ( 2 ) 当圈q 上的顶点再也不能被着色1 时，选手a l i c e 和选手b o b 交替地挑选悬 挂点并着色1 在( 1 ) 中t 1 1 若选手b o b 选择盈0 l ，2 ，扎) 着色l ，则选手a l i c e 依次考察霸一2 与z 件2 ，当 矗一2 未着色且与已着色的顶点不相邻，则妒a ( x i 一2 ) = 1 i 当戤一2 已着色或甄一2 未着色但 与已着色的顶点相邻时，若x 未着色且与已着色的顶点不相邻，则m ( z 州) = 1 ；当 。；一。与。都已着色或未着色但与已着色的顶点相邻时，则在圈c 二上任取一个可以着 色1 的顶点z j ( j 1 ，2 ，n ，i 士l ，i 土2 ) ，当在圈g 上不存在这样的点时，转入( 2 ) 1 2 若选手b o b 选择u j 0 着色l ，则选手a l i c e 依次考察z 与盈+ l 】当墨一l 未着色且与已着色的顶点不相邻，则m ( 以一1 ) = l ；当。已着色或。件1 未着色但与已 着色的顶点不相邻时，则m ( 。) = 1 ；当孔一l 与z l + l 都已着色或未着色但与已着色的 顶点相邻时，则在圈g 上任取一个可以着色1 的顶点”，当在圈g 上不存在这样的点 时，转入( 2 ) ，记过程( 1 ) 结束后已着色l 的顶点集为s 在( 2 ) 中： 设t = 伽f 。y 饵( g ) ) s 且x 可以着色1 显然，若t ，尉t 中只含有 ( g ) 中的悬挂点，两名选手继续交替地在t 中选择顶点并着色1 直到t = 咖 由以上色对策过程知，当过程( 2 ) 结束时，或有妒( 盈) = 1 或对所有的u 墨，有 妒) = l ，两者必有其一，从而在( c ：) 中的任何l 色区问的长度d l 3 ，于是至多再 需要两种新色即可完成整个色对策，即也( ( g ) ) 曼3 综上，x ( l ( c j ) ) = 3 2 1 第四章与轮图有关图上的二人对策着色 4 1 扇图与轮图上的二人对策着色及箕对策色数 定理4 1 1 设礼3 ，则对任何n + 1 阶扇图r 有 粥，= r 篡 证明：显然x ：( r ) 3 ， 以下的讨论，都假定开始时选手a l i c e 选择矗的中心点z o 作为i 步点，( z o ) = 1 ， 由于与其它所有点都相邻，选手b o b 在开始时不得不引进新色2 ，从而减少对选手a l i c e 的阻碍 当ns5 时，r x o = p n ，选手b o b 不论选择哪个点五，妒日) = 2 ，选手a l i c e 都 选择点。l + 2 或x i 一2 着色2 ，使选手b o b 不再对选手a l i c e 造成阻碍，从而易知赡( 矗) = 3 ； 当他= 6 时，不失一般性，我们候定选手b o b 选择2 l ，。2 ，勖之一着色下面分情况 讨论： ( 1 ) 若b o b 选择z l ，妒b ( x 1 ) = 2 ，则选手a l i c e 选择。5 ，妒a ( x 5 ) = 2 ，则选手b o b 只 能选择z 3 ，( 。3 ) = 2 ； ( 2 ) 若b o b 选择2 c 2 ，妒8 ( 如) = 2 ，则选手a l i c e 选择粕，纵( 岛) = 2 ，则选手b o b 只 能选择0 4 ，( 0 4 ) = 2 ； ( 3 ) 若b o b 选择t , 3 ，o b ( x 3 ) = 2 ，则选手a l i c e 选择。5 ，( z 5 ) = 2 ，则选手b o b 只 能选择x , 1 ，妒 ( z 1 ) = 2 ； 注意到经过以上的着色，剩下的三个点是相互独立的，因此可用同样的颜色3 着色， 有x ：( 咫) 3 ， 所以x ：( 民) = 3 ； 当n = 7 时，只要开始时选手b o b 选择3 7 4 ，妇( 。4 ) = 2 ，则a l i c e 有两种可能的选 择： ( 1 ) 若选手a l i c e 选择z l ，( z 1 ) = 2 ，则选手b o b 选择z 7 ，妒b ( z r ) = 2 ，使得 尸2 p l3 7 4 】的长度为3 ； ( 2 ) 若选手a l i c e 选择t 2 ，妒a ( z 2 ) = 2 ，则选手b o b 选择z 7 ，b ( x 7 ) = 2 ，使得 足b2 7 7 j 的长度为3 ； 总之，总存在长度为3 的2 色区间，其恕点需要2 种颜色才能进行正常着色，因此 赡( f 7 ) 4 ； 易证e ( f 7 ) 4 ，从而x ；( f 7 ) = 4 ； 当n 8 时，选手b o b 和a l i c e 轮流选择一点可正常着色2 ，当这一过程结束时，即 2 色不髓再正常着色，任何2 色区闯的长度d 2 3 置选手b o b 能够保证使图中存在长度 为3 的2 色区间，又由于v t v ( r 一 3 7 0 ) 】= r 为路，所以各个2 色区间相互独立，由 于任何2 色区间的长度d 2 3 ，每个2 色区间至多包含两个内点，引进两种颜色即可完 成色对策，从而需要且只需要再引进两种新色3 和4 ，于是x ( r ) = 4 ； 综上 硪耻r 蓦 定理4 1 2 设n 3 ，则对任何n + 1 阶轮图有 礤岍r 蠹6 证明：当n = 3 时，w 3 ：甄，易证x ( w j ) = 4 以下的讨论，我们总是假定选手a l i c e 选择n + 1 阶轮图，n 的中心o o 作为i 步 点，似( 3 7 0 ) = 1 ，由于匈与其它所有点都相邻选手b o b 在开始时不得不引进新色2 ， 且只能在圈g 上选择一点进行着色，从而减少对选手a l i c e 的阻碍 当n = 4 时，不妨设选手b o b 选择点卫l 着色2 ，妒日( z 1 ) = 2 ，选手a l i c e 只能选择点 蜘着色2 ，妒 ( 铂) = 2 ，剩下的两点为独立点，只需再引入一种颜色3 即可完成色对策 从而x ；( w 4 】= 3 当n = 5 时，不妨设选手b o b 选择点z 1 着色2 ，妒日( 。1 ) = 2 ，选手a l i c e 只能选择点 z 3 ( 或x 4 ) 着色2 ，即妒a ( z 3 ) = 2 ( 或( z 4 ) = 2 ) ，这样就得到一个2 色区间p 2 k 1 ，。3 】( 或 马k - ，z a 】) ，其长度d 2 3 而岛b - ，鼬】( 或p 2 陋l ，x 4 】) 至多含有两个内点，引进两种颜 色即可完成色对策，从而需要且只要再引入两种新色3 和4 ，于是x ；( w 5 ) = 4 当n = 6 时，不妨设选手b o b 选择点士l 着色2 ，蛐( z 1 ) = 2 ，选手a l i c e 选择点。3 着色2 ，即 l 口a ( x 3 ) = 2 ，选手b o b 只能选择点z 5 着色2 ，妒b ( z 5 ) = 2 ，余下的三个点是相 互独立的，故只需在引入一种颜色3 即可完成色对策，从而艺( w 6 ) = 3 当札7 时，由x t ( w n ) x ；( r ) = 4 可知我们只需给出眠的一个只用4 种颜色 的色对策即可 不妨设选手b o b 选择点z l 着色2 ，垆s ( zl ) = 2 ，选手a l i c e 选择点z 3 着色2 ，即 o a ( x 3 ) = 2 ，这时选手b o b 和选手a l i c e 轮流在圈上选择可用色2 进行着色的点，当这 一过程结束时，即2 色不能再正常着色，易涯选手b o b 总髓保证存在一个2 色区间其长 度为3 ，且任何其他2 色区间的长度d 2 s3 ，又每个2 色区间是相互独立的，每个2 色区 间至多含有两个内点，且有一个2 色区间含有两个内点，引进两种颜色3 和4 即可完成 色对策，从而赡( u 乞) s4 综上所述t 球吣r 芝6 ， 4 2 扇图与轮图的剖分图上的二人对策着色及其对策色数 在扇图r 的扇路r 上，每相邻点之间添加一个顶点，我们得到它的一个剖分图， 我们称之为齿轮扇图【w ，记作瓦；同样在轮图k 的轮圈g 上，每相邻点之问添加一 个顶点，我们得到它的一个剖分图，我们称之力齿轮图f 1 5 1 ，记作眨 定理4 2 1 设扎3 ，贝9 对齿轮扇图r 有：x ；( r ) = 2 证明；因为中心点t o 与扇路p n 上所有点均相邻，而扇路p n 经剖分后形成两个独 立集s = 如，z i ，z ；，z ：一l ，和s = 扣。，z 2 ，z 3 ，z 。，即瓦具有射分s 和s ， 且s n s = 砂，存在x o s ，使得n ( x o ) = s 7 ，由引理2 3 知( 瓦) = 2 定理4 2 2 设t t 3 ，则对齿轮图有；x 胄( ) = 2 证明：图鹏：可划分成两个独立集s = x o ，墨，南，z ： ，和s = 扛t ，现，z 3 ，霸) 且s n = 咖，存在s ，使得n ( x o ) = s ，由引理2 3 知x ；( 眠) = 2 在扇图r 的每根幅上添加一个顶点，我们得到它的一个剖分图 1 5 1 ，记作q 。；同 样在轮图i 的每根幅上添加一个顶点，我们得到它的一个剖分图 1 5 1 ，记作g k 定理4 2 3 设n 3 ，则对图q 。有；磁( q 。) = 3 证明：首先我们总是假定选手a l i c e 选择点x o 作为i 步点，m ( 。o ) = 1 ，下面由选 手b o b 选点着色 当n = 3 时，不失一般性，我们假定选手b o b 选择。1 ，。2 之一着色： ( 1 ) 若选手b o b 选择研着色l ，蚀( z 1 ) = 1 ，选手a l i c e 只能选择z 3 ，妒 ( z 3 ) = 1 ， 这时选手b o b 只有引进新色2 ，不妨设选手b o b 选择z 2 ，妒b ( 。2 ) = 2 ( 其他情形可类似证 明) ，选手a l i c e 选择巧，m ( 。i ) = 2 ，选手b o b 选择z j ，妒口( 矗) = 2 ，这时选手a l i c e 只 能引进新色3 ，选取砭，m ( 吐) = 3 ； ( 2 ) 若选手b o b 选择茁2 着色1 ，i p 口( 。2 ) = 1 ，这时就存在1 色区间且1 色区间的长 度d 1 3 ，它们是相互独立的且最长1 色区间含有两个内点，所以只要再引入两种颜色 2 和3 即可完成色对策， 因而砭( q 3 ) = 3 当几= 4 时，不失一般性，我们假定选手b o b 选择o l ，。2 之一着色： ( 1 ) 若选手b d 6 选择z l 着色1 ，妒b ( 。1 ) = 1 ，选手a l i c e 能选择x 3 ，协( 现) = l ，这时 就存在l 色区间且l 色区间的长度d 1 3 ，它们是相互独立的且最长l 色区间禽有两个 内点，所以只要再引入两种颜色2 和3 即可完成色对策， ( 2 ) 若选手b o b 选择z 2 着色1 ，妒b ( z 2 ) = 1 ，则选手a l i c e 选择。4 ，( z 4 ) = 1 ，这时 就存在1 色区间且1 色区闻的长度d l 3 ，它们是相互独立的且最长1 色区间含有两个 内点，所以只要再引入两种颜色2 和3 即可完成色对策， 因而赡( q a ) = 3 当n = 5 时，不失一般性，我们假定选手b o b 选择z l ，x 2 ，石3 之一着色： ( 1 ) 若选手b o b 选择z l 着色1 ，妒日( 。1 ) = l ，则选手a l i c e 选择z 3 ，( z 3 ) = l ，这时 选手b o b 只能选取岛，妒口( 船) = 1 ，这时就存在1 色区间且1 色区问的长度d 1s3 ，它 们是相互独立的且最长1 色区间含有两个内点，所以只要再引入两种颜色2 和3 即可完 成色对策； ( 2 ) 若选手b o b 选择z 2 着色l ，妒丑( 。2 ) = l ，则选手a l i c e 选择缸，m ( 2 4 ) = 1 ，这时 就存在1 色区间且1 色区间的长度d l 3 ，它们是相互独立的且最长1 色区问含有两个 内点，所以只要再引入两种颜色2 和3 即可完成色对策； ( 3 ) 若选手b o b 选择z 3 着色1 ，妒b ( x a ) = 1 ，则选手a l i c e 选择。l ，妒a ( i i ) = 1 ，这时 选手b o b 只能选择2 7 5 ，妒8 ( 奶) = l ，这时就存在1 色区间且1 色区间的长度d l 3 ，它 们是相互独立的且最长1 色区间含有两个内点，所以只要再引入两种颜色2 和3 即可完 成色对策； 因而磁( q s ) = 3 当n 6 时，因为n ( x o ) = x l ，。：，z ： ，所以选手b o b 和选手a l i c e 轮 流在扇路上选择1 可着色点，当这一过程结束对，即1 色不能再正常着色，任何1 色 区间的长度d ts3 且选手b o b 能够保证使图中存在长度为3 的l 色区间又由于 g v ( q 。 x o ，z i ， ) 】= r 为路，所以各个1 色区间相互独立，由于每个l 色区 间的长度d - s3 ，且最长1 色区间含有2 个内点我们采用如下的对策方案： ( 1 ) 对于长度为2 的l 色区间，其内点都着色2 ； ( 2 ) 对于扇路上长度为3 的1 色区间，不妨设为p l k ，x i + 3 】，0 1 ：2 ，n 一3 ) ) 这时选手a l i c e 和b o b 轮流选可2 着色点，若( 。i + 1 ) = 2 ( 或妒日( 盈+ z ) = 2 ) ，则 妒b ( z ：+ 2 ) = 2 ( 或v a ( e , + 2 ) = 2 ) 当色2 不能再用来着色时，剩下的点构成一个独立集，只需用颜色3 即可完成3 种 颜色的色对策 综上：x i ( q 。) = 3 定理4 ，2 ，4 设n 3 ，则对图g 。，有：x t ( g 。) = 3 证明：由推论2 1 0 知：x ：( g 。) 3 下面我们只需给出一个用3 种颜色的色对策即可 首先选手a l i c e 总是选择图g 。中心点x o 作为i 步点，( z o ) = 1 当n = 3 时，选手b o b 只能在圈凸上选择一点，不失一般性，b o b 选择o l 着色 1 ，蛐( z 1 ) = l ，则选手a l i c e 只有引进新色2 ，选择。2 ，妒a ( x 2 ) = 2 ，选手b o b 选择z i ：毛 之一着色2 ，若选手b o b 选择矗( 或z 3 ) 着色2 ，则选手a l i c e 可选择，m ( 矗) = 2 ( 或 选择z i ，( 。i ) = 2 ) 注意到无论选手b o b 怎么选点着色，剩下的两个点构成独立集， 只要引入颜色3 即可完成色对策，从而x ；( v 3 ) = 3 类似可证当礼= 4 ，5 时，x ：( g 。) = 3 当礼6 时，选手b o b 和选手a l i c e 轮流在轮圈上选择可用色1 进行着色的点，当 这一过程结束时，即1 色不能再正常着色，易证选手b o b 总能保证存在长度为3 的1 色 区间且每个1 色区间是相互独立的由于任何l 色区间的长度d l 3 我们采用如下的对策方案：