（运筹学与控制论专业论文）几类特殊平面图上的二人对策着色.pdf

学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 y 6 4 2 5 3 6 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已经发表或 撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了谢意。 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版；有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅；有 权将学位论文的内容编入有关数据库进行检索；有权将学位论文的标题和摘要 汇编出版。保密的学位论文在解密后适用本规定。 摘要 这篇文章讨论在图上的二人对策着色：设t ，d 是正整数，x 是t 种颜色的集合 由a l i c e 开始，a l i c e 和b o b 两个人轮流选取x 中的颜色对图g 的顶点进行着色， 每次每人着一个顶点如果图g 的顶点z 着颜色c 后，由图g 着颜色c 的顶点导 出的子图的顶点最大度至多是d ，则称颜色c 对顶点z 来说是可行色每次a l i c e 和 b o b 必须用可行色对图g 的未被着色的顶点进行着色如果图g 的所有顶点都被着 色或者还有顶点没有可行色去着色，则着色结束a l i c e 的目标是实现对图g 的所 有顶点进行可行着色，而b o b 的目标就是要破坏a l i c e 实现她的目标这篇文章主 要运用分裂已着色顶点的方法证明了如果图g 是二叉树，且d 兰2 ，则x ( g ) s 2 如果图g 是树且d 3 ，则x ( g ) 2 设g 是外部平面图且d 2 ，g 是g 的2 一连 通的三角剖分若一是一条路，则) ( ( g ) 曼5 设g 是外部平面图且d 3 ，g 是g 的2 连通的三角剖分，d 是，的最小控制集若，【d 是一条路，则x ；d j ( g ) 5 另外还讨论轮图与扇图的对策着色 关键词 对策着色；放松对策着色；可行色；放松对策色数；二叉树；树；外部平面图；三 角剖分；拟对偶图；最小控制集；轮图；扇图 中图分类号： 0 1 5 7 5 2 a b s t r a c t t h i sp a p e rd i s c u s s e st h ef o l l o w i n gt w o 。p e r s o ng a m eo i l g r a p h s l e tt ，db ep o s i t i v ei n t e g e r s a n dxas e to fc o l o r sw i t hl x i = t t w op e r s o n s a l i c ea n db o b t a k et u r n s c o l o r i n gt h ev e r t i c e so f gw i t hc o l o r sf r o mx ，w i t ha l i c eh a v i n gt h ef i r s tm o v eac o l o rci sf e a s i b l ef o ra nu n c o l o r e dv e r t e x oi fb yc o l o r i n gzw i t hc o l o rc ，t h es u b g r a p ho fgi n d u c e db yt h o s ev e r t i c e so fc o l o rch a sm a x i m u m d e g r e ea tm o s td e a c hm o v eo fa l i c eo rb o b c o l o r sa nu n c o l o r e dv e r t e xw i t haf e a s i b l ec o l o r t h e g a m e i so v e ri fe i t h e ra i lv e r t i c e so fga t ec o l o r e d o rn om o r ev e r t i c e sc a l lb ec o l o r e dw i t haf e a s i b l e c o l o r a l i c e sg o a li st op r o d u c eaf e a s i b l ec o l o r i n gt oc o l o ra l lt h ev e r t i c e so fg a n db o b sg o a li s t op r e v e n tt h i sf r o mh a p p e n i n g b ys p l i t t i n gt h ec o l o r e dv e r t i c e so fg r a p h s t h i sp a p e rp r o v e st h a t i f gi sab i n a r yt r e ea n dd2 2 ，t h e nx 铲( g ) s2 ；i fg i sa f o r e s ta n dd 3 ，t h e n ) ( 扩( g ) s2 l e t gi sa no u t e r p l a n a rg r a p ha n dd 2 ，g i sa2 - c o n n e c t e dt r i a n g u l a t i o no fg ，i ft o ，i sap a t h ，t h e n x 妒( g ) 5 l e tg i sa no u t e r p l a n a rg r a p ha n dd 3 ，g 7i sa2 - c o n n e c t e dt r i a n g u l a t i o no fga n d di sam i n i m u m d o m i n a t i n gs e to f t o ，i f t g , d i sap a t h ，t h e nx 铲( g ) 5 m o r e o v e r ，t h i sp a p e r a l s od i s c u s s e st h eg a m ec o l o r i n go fw h e e l sa n df a n s k e y w o r d s g a m ec o l o r i n g ；r e l a x e dg a m ec o l o r i n g ；f e a s i b l ec o l o r ；r e l a x e dg a m ec h r o m a t i cn u m b e r ；, b i n a r yt r e e ； t r e e ；o u t e r p l a n a rg r a p h ；t r i a n g u l a t i o n ；i m i t a t i v ed u a lg r a p h ；m i n i m u md o m i n a t i n gs e t ；w h e e l ；如n c l cn u m b e r ：0 1 5 7 5 3 1前言 1 1基本概念 下面介绍本文所要用到的基本概念 图g = ( y ( g ) ，e ( g ) ) ，其中y ( g ) ，e ( o ) 分别是图g 的顶点集和边集，且e ( g ) = “”h y ( g ) ) 在不致混淆时，把y ( g ) ，e ( o ) 简记为k e 设u y ( g ) ，如果存在e = ? i v e ( g ) ， 则称u ，u 相邻，称e 与u 或”关联，u ，”称为e 的端点两个端点相同的边称为环若两个 顶点间有多于一条边，则称这样的边为多重边 本文所讨论的图都是有限简单图，即i y ( g ) l i s l ，则称s 为g 的极大团g 的极大团所含的顶点数称为g 的 团数，记为u ( g ) 设g = ( k e ) 是图，u v 从u 连到”的互不相同的顶点与边的交替序列称为从u 到u 的路，记为p u 。r 。上的边数称为r 。的长度g 中连接u ，u 的最短路的长度称为u 和”的距离，记为d g ( u ，”) 或d ( u ，”) 若路p u ，的起点和终点相同，则称r 。为圈圈上的边 数称为圈的长度长度为的圈称为r 一圈g 中最短圈的长度称为g 的围长，记为g ( g ) 设g = ( k e ) 是图，若对v t v ，都存在从u 到”的路，则称图g 是连通的设 ”u g 一”表示从图g 中删去”以及与u 关联的所有边后所得到的图若g 连通，且对 v v v ，g 一 都连通，则称g 是2 一连通的 定义1 3 如果图g 中不合有圈，则称g 是无圈图连通的无圈图称为树树中度为l 的顶 点称为树叶有一个顶点度为2 且除树叶外其他顶点似- 果还有的话，的度都为3 的树称为 二又树其中度为2 的顶点称为二叉树的根根的两侧部分称为二又树的两个分枝 定义1 4 设g = ( k e ) 是图，如果能把图g 画在平面上，使得它的所有边只在顶点处相 交，则称图g 为可平面图图g 的这种平面表示称为g 的平面图设g 7 为平面图，g 的 每个连通区域称为图g 的面 g 的顶点集，边集和面集分别记为v ( v ) ，e ( c 飞f ( g 气如 果g 的顶点都在g 的外部无界面，0 的边界上，则称图g 、匐外部平面图如果除了外部 无界面外，g 的每个面都是三角形面，则称g 7 为三角剖分外部平面甲如果外部平面图 g 不是三角剖分外部平面图，通过对g 进行加边而得到的图g ”是三角剖分外部平面图， 则称g ”是g 的三角剖分 容易证明，任一外部平面图都存在2 一连通的三角剖分 定义1 5 设g = ( k e ) 是图，eee ，边e 的剖分是从g 中删去e ，并添加一条连接e 的两 个端点的长度至少为2 的路设g 【，g 2 是两个图，若g 2 可由g l 通过一系列边的剖分而得 到，则称g 2 与g l 同胚 定义1 6 设圈g = ( g ) ，e ( g ) ) ，图g 的线图记作l ( g ) ，定义如下； 矿( l ( g ) ) = e ( g ) i 2 对v 。，y e ( g ) ，。，y 在l ( g ) 中相邻锌。，y 在g 中与同一个顶点关联 文中没有定义的概念和术语均可在文 3 】中找到 5 1 2图的着色与对策着色 设g = ( k e ) 是有限图，设t ，d 是正整数，x 是t 种颜色的集合图g 的顶点着色是从 图g 的顶点集y 到颜色集合x 的一个映射c ：v _ x 如果对图g 的任意一条边u ”e ， 顶点u 和”都着不同颜色，则称图g 的这种顶点着色为图g 的正常顶点着色图g 的色数 x ( c ) 是图g 的正常顶点着色所需的最少颜色数如果由图g 的着相同颜色的顶点导出的 子图中顶点的度都不超过d ，则称图g 的这种顶点着色为图g 的放松度为d 的顶点着色 图g 的放松为d 的色数x ( d ) ( g ) 是图g 的放松度为d 的顶点着色所需的最少颜色数 1 9 9 0 年b o d l a e n d e r 在关于计算机科学中的图理论专题讨论会上做了“关于某些着色策 略的计算复杂性”的专题报告，基于图的正常顶点着色的概念，首先引入了图的对策着色的 概念随后uf a i g l e ，u k e r n ，h a k i e r s t e a d 和w t t r o t t e r 做了拓展，并研究了一些特殊 图类的对策色数图的对策着色是根据两个人( a l i c e 和b o b ) 在图上做顶点着色提出的即 图的对策着色是由a l i c e 开始，a l i c e 和b o b 两个人轮流选取x 中的颜色对图g 的顶点进 行着色，每次每人着一个顶点a l i c e 试图给图g 一个正常顶点着色，而b o b 则设法阻止 该事件发生每一步都包括一个人选取一个未被着色的顶点，并从x 中选取颜色来对它 进行着色，使得它的颜色不同于它邻点的颜色若n = l y ( g ) 1 步后，g 被正常顶点着色， 则a l i c e 获胜若在图g 全部顶点被着色之前出现僵局，即在一个尚未着色的顶点的邻点上 出现了x 中的所有颜色，则b o b 获胜图g 的这种顶点对策着色称为图g 的正常顶点对 策着色图g 的对策色数x 口( g ) 是图g 的正常顶点对策着色所需的最少颜色数 c h o u ，w a n g 和z h u 在 8 中介绍了图的放松对策着色和图的放松对策色数图的放松对 策着色是图的对策着色的变形，放松度为d 的对策着色是由a l i c e 开始，a l i c e 和b o b 两个 人轮流选取x 中的颜色对图g 的顶点进行着色，每次每人着一个顶点如果图g 的顶点 z 着颜色c 后，由图g 着颜色e 的顶点导出的子图的顶点最大度至多是d ，则称颜色c 对顶 点。来说是可行色每次a l i c e 和b o b 必须用可行色对图g 的未被着色的顶点进行着色 a l i c e 的目标是实现对图g 的所有顶点进行可行着色，而b o b 的目标就是要破坏a l o e 实现 她的目标如果图g 的所有顶点都被着色或者还有顶点没有可行色去着色，则着色结束 如果经过n = i y ( g ) 1 次着色，图g 的所有顶点被可行着色了，则称a l i c e 是获胜者如果在 图g 的所有顶点未全部被可行着色之前出现了僵局，即图g 还有顶点没有可行色去着色， 则称b o b 是获胜者为了方便，称图g 上的放松度为d 的对策着色为g 上的( t ，d ) 一对策着 色，其中t = i x i 放松度为0 的对策着色就是一般的对策着色，在【1 ，1 2 ，1 5 】中有所论述图g 的放松 度为d 的对策色数x 铲( g ) 就是在图g 上的放松度为d 的对策着色过程中a l l c e 能获胜所需 的最少颜色数，即集合x 的最小基数) ( 护( g ) 就是b o d l a e n d e r 在 1 】中所引入的对策色数 均( g ) 图族r 的放松度为d 的对策色数定义为： x ! j d ) ( r ) ：“a x ( x 妒( g ) ：g r 若拶( g ) 皆是有限值， “ i o 。 否则 在 5 1 中，c a i 和z h u 又介绍了图的边对策着色，即在对策着色过程中a l i c e 和b o b 是对 图的边进行着色而不是对顶点进行着色其实，图g 上的边对策着色就是图g 的线图l ( a ) 上的顶点对策着色图g 的边对策色数也( g ) 是在对图g 上进行对策着色中a l i c e 能获胜 所需的最少颜色数，且有a 兄2 a 一1 在对策着色的基础上，c h e n ，s c h e l p 和s h r e v e 7 对b o b 再附加条件，提出了一种新的对 策着色，l i p x 十策着色u 这个附加条件是限制b o b 只能使用a l i c e 已使用过的颜色之一，除非 他为保证图的正常着色而不得不使用x 中的一种新颜色图g 的对策色数，记为瑞( g ) ， 是a l i c e 在对策着色中能获胜所需的最少颜色数 图族r 的对策色数定义为； 碌r ) 一 坩唧篱，脯触 由x ( g ) ，( g ) 和) ( ；( g ) 的定义可知 x ( a ) ；( g ) sx 9 ( g ) + 1 c h e n ，s c h e l p 和s h r e v e 在 7 】中证明了x ；( t ) 3 ，其中t 是树，确定了x ；( g ) = ) ( ( g ) 的一些 图类 7 1 3已有的相关结论 设g = ( v e ) 是有限图，f v i = n 上是顶点集y 上的线性序列，设为三：，。 对v v i v ，定义顶点v 。相对于序列l 的后向度为： d b ( v z ) = i 勘v e ， 2 ，则a l i c e 就选路民。上与n b 一点的距离为2 的顶点来着色， 3 如果上述两种情况都不出现，而且t 有一个树干互有两个树叶( 设为2 ，y ) 被着色且有 不止一条边若d ( x ，y ) = 2 ，则a l i c e 就选路b ，上未被着色的顶点来着色( 如果有多个 这样的树予，a l i c e 可任选其一) ，如果树? 的所有有两个树叶被着色鲍树于中两个已被 着色的树叶之间的距离大于2 ，则a l i c e 就任选其中一个树干中连接两个已被着色的树叶 的路上与n a 一点距离为2 的顶点来着色 4 如果树? 的所有树干都只有一个树叶被着色，则a l i c e 可任选一个未放着色的顶点来着 色 这样我们就证明了断言1 假设利用上述对策a l i c e 选取了树干置的一个顶点“为了a l i c e 麓为顶点“选到可行 色，我们先证明 断言2a l i c e 能避免部分着色二叉树t 出现如图j 的结构 分下面三静情形来证明： 情形一如果顶点3 和5 都是b 一点不失一般性，设顶点5 在顶点3 之前被b o b 着 色由断言l 的证明可知，顶点1 和2 不可能都在顶点3 被( b o b ) 着色之前被着色否则， 在b o b 选点之前，亦即a l i c e 选点之后，部分着色二叉树? 有一个树干包含有三个已设着 色的树叶，与断言l 矛盾由断言l 的证明可知，在b o b 给顶点3 着色之后，a l i c e 必然会 1 2 毛卢一? 图1 ：断言2 中图的结构示总图 图1 中数字是顶点的名称，。，b 是两种颜色顶点标 有a 或b 表明该顶点被着颜色a 或b 4 是未被着色的顶点， 立即选顶点4 来着色 情形二如果顶点3 和5 中有一个( 不妨设是顶点3 ) 是a 一点，另一个顶点( 顶点5 ) 是 b 点i 1 如果顶点5 在顶点3 之前被着色由断言l 的证明和上述a l i c e 为自己选的顶点选色的 方法可知，顶点1 和2 不可能都在顶点3 被( a l i c e ) 着色之前被( a l i c e 或b o b ) 选且被着 颜色。否则，如果顶点l 和2 都在顶点3 被着色之前被选且被着颜色m 由上述a l i c e 为自己选的顶点选色的方法可知，顶点3 应被着颜色b 若顶点1 ，2 中有一个顶点( 不妨 设点1 ) 在顶点3 被着色之前被着颜色a ，由断言l 的证明和上述a l i c e 为自己选的顶点 选色的方法可知，点3 应被着颜色b ，或顶点4 在顶点3 被着色之前已经被着色 2 如果顶点3 在顶点5 之前被着色由断言1 的证明可知，顶点6 和7 不可能都在顶点5 被( b o b ) 着色之前被着色否则，顶点5 就成了a 点了，矛盾而且b o b 给顶点5 着 色后部分着色二叉树t 中没有含顶点6 或7 且有三个树叶已被着色的树干因此a l i c e 可在b o b 给顶点5 着色后立即选顶点4 来着色 情形三如果顶点3 和5 都是a 一点不失一般性，设顶点5 在顶点3 之前被着色由 断言1 的证明和上述a l i c e 为自己选的顶点选色的方法可知，顶点1 和2 不可能都在顶点3 被着色之前被着颜色o 否则，如果顶点1 和2 都在顶点3 被着色之前被着颜色。，由上述 a l i c e 为自己选的顶点选色的方法可知，顶点3 应被着颜色b 若顶点l ，2 中有一个顶点( 不 妨设顶点1 ) 在顶点3 被着色之前被着颜色a ，由断言l 的证明和上述a l i c e 为自己选的顶点 选色的方法可知，顶点3 应被着颜色b ，或顶点4 在顶点3 被着色之前已经被着色这样我 们就证明了断言2 利用断言2 ，a l i c e 可通过下述方法为顶点u 选色： 1 3 1 如果露只有两个或三个树叶被着相同颜色，而且u 的邻点都没被着色，则a l i c e 也给u 着同榉的颜色否则，a l i c e 就给u 着另一种颜色 2 如果置有三个树叶( 设为。，y ，z ) 被着不同的颜色，则一定有两个 ；i ； 叶( 设为。：v ) 著相 同的颜色如果d ( x ，u ) 1 ，d ( ”，“) l ，但是d ( z ，u ) = 1 ，那么a l i c e 给u 着。的颜色 如果d ( 。，u ) = d ( y ，“) = 1 而d ( z ，u ) 1 ，或d ( z ，u ) 1 ，d ( 。，“) 1 但是d ( 1 ，u ) = 1 ，或 d ( z ，u ) 1 , d ( y ，) 1 且d ( z ，口) 1 ，那么a l i c e 绘u 着# 的颜色 3 如果五只有两个树叶( 设为”，w ) 被着不同颜色且这两个树叶都是b 点不失一般性， 设”是n b 一点如果d ( v ，) 1 ，d ( w ，u ) l ，那么a l i c e 给“着w 的颜色 4 如果曩只有两个树叶( 设为。，y ) 被着不同颜色，d ( 。，y ) 2 且至少有一个树叶是a 一 点不失一般性，设z 是n a 一点如果d ( 。，) l ，d ( y ，u ) 1 ，那么a l i c e 给u 着y 的颜 色 5 如果上述四种情形都不出现，根据断言2 ，a l i c e 能为顶点u 选到可行色， 因此在这个对策着色中，a l i c e 有一个获胜对策 推论2 1 设t 是树，若t 中3 点与4 点的距离都不等于2 且d 2 ，则x ( t ) 2 ，即 对? 上的( 2 ，d ) 一对策着色，a l i c e 有一个获胜对策 证明；因为t 中三3 点与4 点的距离都不等于2 ，所以在t 中与24 点的距离为等于 2 的顶点只可能是 3 点根据断言2 的证明知，部分着色树t 中不可能出现如图1 的结 构，因此对t 上的( 2 ，d ) 一对策着色，a l i c e 有一个获胜对策 推论2 2 设t 是树且d 2 ，若a ( t ) s3 ，则) ( 扩( ? ) 2 图2 ：n 4 ，n 为偶数 图2 中数字和他是顶点的名称o 是颜色顶点标有a 表明 该顶点被着颜色口- 顶点标有。表明滚顶点被着颜色o ，b 或e 1 4 由定理1 1 和定理1 1 5 知，树族的对策色数和放松度为l 的对策色数分别为4 和3 二叉 树族作为具有特殊性质的树族，它的对策色数和放松度为1 的对策色数是否会小一些呢? 下面两个定理回答了这个问题 定理2 2 存在二又树t ，使得) = 4 ，即对t 上的( 3 ，0 ) - 对策着色，b o b 有一个获胜对 燕 证明：设a l i c e 和b o b 在t 上进行( 3 ，o ) 对策着色如果在a l i c e 选点着色之后，部分着色 二叉树t 中出现如图2 的结构则b o b 有一个获胜对策 首先我们考虑礼= 4 的情况如果z o ( 不妨没z = 6 ) ，b o b 给顶点2 着颜色c 这就使 得a l i c e 必须着顶点。t 及其邻点或及其邻点( 不防设a l i c e 着顶点u 【及其邻点) ，则b o b 给顶点如着颜色n 于是b o b 获胜如果。= a ，则b o b 给顶点2 着颜色6 或c ( 不防设为b ) 同样a l i c e 必须着顶点”l 及其邻点或w 3 及其邻点( 不防设a l i c e 着顶点。l 及其邻点) ，则b o b 给顶点如着颜色c 于是b o b 获胜 设n26 ，b o b 给顶点2 着颜色b 或c 则a l i c e 必须着顶点u - 及其邻点由归纳法可 知，b o b 获胜 接下来只要证明b o b 能使得在a l i c e 选点着色之后，部分着色二叉树t 中出现如图2 的结构即可 设二叉树t 充分大且t 的两个分枝关于根对称不妨设b o b 与a l i c e 在t 的同一分枝 中取点着色设开始a l i c e 给顶点“l 着色，然后b o b 给顶点u 2 着色，使得d ( u t ，u 2 ) 充分大 且为偶数设接下来a l i c e 给顶点u 3 着色，不管u 3 如何选，u ，u 2 ，u 3 中必有两个顶点的距 离很大，且连接这两个顶点的路上没有顶点被着色 1 若顶点u 3 在p u 。，上且d ( 札u 3 ) 为偶数，或顶点, u t 在p u 上，或顶点毗在r 。 上，则部分着色二叉树t 中出现了如图2 的结构 2 若上述情况不出现且d ( u 1 ，u 3 ) 为偶数，则部分着色二叉树t 中出现了如图2 的结 构 若上述两种情况都不出现，不妨设d ( 虬u 3 ) 很大，且r 上没有顶点被着色则b o b 选取 r ，。r m ，r m 外的顶点u 4 来着色，使得d ( u t ，u ) ，d ( u 3 ， ) ，d ( u 4 ，w ) 都很大且d ( u 3 ， ) ，d ( u 4 ，w ) 为偶数，其中, t z 为r 。，r 。，r 。的交点设接下来a l i c e 给顶点5 着色 1 0 若u 5 在r 。p u 。，p u 。r 。这四条路上，则部分着色二叉树t 中出现了如图2 的 1 5 结构 2 0 若1 , 5 不在p u 。，r 。r 。r ：。这四条路上设”为r ，。上的顶点，r 。与r 。 或r 。或r 。相交的第一个交点为 ( 1 ) 若w 在r ，。或只。，l ，这时可取r 。为p o 。，则部分着色- y 树t 中出现 了如图2 的结构 ( 2 ) 若。i 7 在只。上，这时可取r 。为p u ，。则部分着色二叉树丁中出现了如图2 的结构 ( 3 ) 若w 在r 。上，这时可取r 。为娲。，则部分着色- - y 树t 中出现了如图2 的结构 因此，对t 上的( 3 ，o ) 一对策着色，b o b 有一个获胜对策 0 图3 ：n 5 图3 中数字和”：是顶点的名称o 是颜色顶点标有a 表明 该顶点被着颜色n 顶点标有z 表明该顶点被着颜色o ，b 或c 定理2 3 存在二又树t ，使得x ( t ) = 3 ，即对t 上的( 2 ，1 ) 一对策着色，b o b 有一个获胜对 策 证明：这个结论的证明方法与【8 中定理1 1 6 的证明方法相类似 设a l i c e 和b o b 在t 上进行( 2 ，1 ) 一对策着色如果在a l i c e 选点着色之后，部分着色二 叉树t 中出现如图3 的结构则b o b 有一个获胜对策 首先我们考虑n = 4 的情况如果z = a ，则b o b 给顶点奶着颜色6 ；这使得a l i c e 必须 给顶点3 着颜色6 ( 否则，b o b 给顶点u 或”着颜色b ，从而使得顶点3 选不到可行色) 然 后，b o b 给顶点”5 着颜色n 这使得顶点4 选不到可行色因此b o b 获胜若z = b ，则b o b 给顶点4 着颜色b ，这使得顶点3 选不到可行色因此b o b 获胜 16 若n 6 ，b o b 给顶点? 3 3 着颜色b ，这使得a l i c e 必须给顶点3 着颜色b 由归纳法知， b o b 获胜 接下来只要证明b o b 能使得在a l i c e 选点着色之后，部分着色二叉树t 中出现如图3 的结构即可 设二叉树t 充分大且丁l 的两个分枝关于根对称不妨设b o b 与a l i c e 在t 的同一分枝 中选点着色设开始a l i c e 给顶点叭着色，然后b o b 给顶点u 2 着色，并使得d ( u i ，u 2 ) 充分 大接下来，设a l i c e 给顶点均着色不管顶点u 3 如何选，u l ，u 2 ，u 3 中必有两个顶点的距 离很大，且连接这两个顶点的路上没有顶点被着色不妨设这两个顶点为虬u 3 现在b o b 选顶点i f , 4 着色，并使r 。r 。，p u 。有唯一得交点w ，且d ( u i ，) ，d ( u 3 ， ) ，d ( u 4 ，w ) 都很 大接下来轮到a l i c e 选点着色，设a l i c e 选顶点u 5 着色 1 0 若 5 在r 。r 。，r 。这三条路上，且d ( “5 ， ) 不大则b o b 选顶点u 5 在这三条 路上的一个邻点并着与u 5 同样的颜色从而不管下面a l i c e 如何选点着色，部分着色二叉 树丁中出现如图3 的结构即可 2 0 若u 5 在r 。，r 。r 。这三条路上，且d ( u 5 ，w ) 很大，或若u 5 不在这三条路上 则b o b 选顶点w 着色不管下面a l i c e 如何选点着色，b o b 都能使部分着色二叉树? 中出 现如图3 的结构即可 因此，对t 上的( 2 ，1 ) 一对策着色，b o b 有一个获胜对策 r0 6 b l2345 图4 ：推论23 中图的结构示意图 图4 中数字是顶点的名称n ，bc 是3 种颜色顶点标 有a ，b 或c 表明该顶点被着颜色a ，b 或c 3 是未被着色的顶点 利用断言l 中a l i c e 的选点方法可得： 推论2 3 ( 定理1 1 5 ) 如果t 是树且d 1 ，则x ( t ) 3 1 7 证明：在着色过程中，a l i c e 仍然利用断言l 中选点方法来选点设在着色过程中，t 已被 部分着色，t - ，乃，z h 为丁的树干在a l i c e 选点着色之后，部分着色树t 每个树干至 多有两个已被着色的树叶，从而在b o b 选点着色之后，部分着色树丁每个树干至多有两个 已被着色的树叶如果a l i c e 选取了树干正的一个未被着色的顶点“，则a l i c e 可通过下述 方法为顶点u 选色； 1 若“的已被着色的邻点少于三个，或“有三个邻点已被着色，但是只用了两种颜色 易知a l i c e 能为顶点“选到可行色 2 若u 有三个邻点被着不同颜色只要证明部分着色树t 中不会出现如图4 的结构就 可以了不妨设顶点2 ，4 ，6 中顶点2 是最后一个被着色的顶点，则顶点2 一定是b 一点且顶 点l 在顶点2 被着色之前一定未被着色( 否则顶点3 应在顶点2 之前被着色) 这样a l i c e 会 在b o b 着顶点2 之后立即着顶点3 1 8 2 2树上放松度为3 的对策色数 定理2 , 4 ( s h e n ，z h o u 2 b ) 如果t 是树且d 3 ，则) ( 妒( t ) s2 即对t 上的( 2 ，d ) 一对策着 色，a l i c e 有一个获胜对策 证明：对策着色中a l i c e 所采取的对策和定理2 1 中a l i c e 所采取的对策很相似不同之处 是a l i c e 所要避免的部分着色树t 中出现的结构与图1 中不同 在着色进行过程中，a l i c e 仍利用断言1 中的选点方法来选点设t 已被部分着色， 正，噩，了k 为部分着色树t 树干在a l i c e 选取下一个顶点着色之后，我们有 断言3 在a l i c e 选点着色之后，部分着色树t 每个树干至多有两个已被着色的树叶而且 如果存在正m 且互有不止一条边，则置q ，其中m ，印的定义同断言中m ，0 的定 ； 义j 断言3 的证明与断言1 的证明相同 2 8 图5 ：断言4 中图的结构示意图 图5 中数字是顶点的名称a ，b 是两种颜色顶点标 有a 或b 表明该顶点被着颜色口或b 5 是未被着色的顶点 假设利用上述策略a l i c e 选取了树干五的一个顶点u 为了a l i c e 能为顶点u 选到可行 色，我们先证明 断言4a l i c e 能避免部分着色树t 出现如图5 的结构 分下面三种情形来证明： 情形一如果顶点4 和6 都是b 一点不失一般性，设顶点6 在顶点4 之前被b o b 着 色由断言3 的证明可知，顶点i ，2 ，3 不可能都在顶点4 被( b o b ) 着色之前被着色否则， 在b o b 选点之前，亦即a l i c e 选点之后，部分着色树t 有一个树干包含有三个已被着色的 1 9 树叶，与断言3 矛盾由断言3 的证明可知，在b o b 给顶点4 着色之后，a l i c e 必然会立即 选顶点5 来着色 情形二如果顶点4 和6 中有一个( 不妨设是顶点4 ) 是a 一点，另一个顶点( 顶点6 ) 是 b 一点 1 如果顶点6 在顶点4 被着色之前被昔色由断舀3 的证明和上述a l i c e 为自己选的顶点 选色的方法可知，顶点1 ，2 ，3 至多有一个在顶点4 被( a t i c e ) 着色之前被着颜色。否 则，由上述a l i c e 为自己选的顶点选色的方法可知，顶点4 应被着颜色b 如果顶点1 ，2 ， 3 都不在顶点4 被着色之前被着色如果在顶点4 未被着色之前，部分着色树t 中的含 有顶点4 和顶点。6 的树干只有一个已被着色的树叶，即顶点6 ，别a l i c e 可先选顶点5 来 着色如果在顶点4 未被着色之前，部分着色树t 中的含有顶点4 和顶点6 的树干只有 两个或有三个已被着色的树叶，由上述a l i c e 为自己选的顶点选色的方法可知，顶点4 应被着颜色b 若顶点1 ，2 ，3 中恰有一个顶点( 不妨设点1 ) 在顶点4 被着色之前被着n ， 若顶点4 无其它邻点在顶点4 被着色之前被着色，由断言3 的证明和上述a l i c e 为自己 选的顶点选色的方法可知，点4 应被着颜色b ，或顶点5 在顶点4 被着色之前已经被着 色若顶点4 有其它邻点( 设为顶点2 ) 在顶点4 被着色之前被着色，由前面的论证知， 顶点2 只能着颜色b 且顶点4 被着色后部分着色树t 中不含顶点1 或2 或6 但含顶点 4 的树干中没有两个或三个树叶被着色因此a l i c e 可在顶点4 再有两个邻点被着颜色 a 之前先给顶点5 着色 2 如果顶点4 在顶点6 着色之前被着色由断言3 的证明可知，顶点7 ，8 ，9 中至多有一个 在顶点6 被( b o b ) 着色之前被着色而且b o b 给顶点6 着色后部分着色树t 中没有含 顶点6 且含顶点7 或8 或9 且有三个树叶已被着色的树干否则，顶点6 就成了a 一点 了，矛盾因此a l i c e 可在b o b 给顶点6 着色后立即选顶点5 来着色 情形兰如果顶点4 和6 都是a 一点不失一般性，设顶点6 在顶点4 被着色之前被着 色由断言3 的证明和上述a l i c e 为自己选的顶点选色的方法可知，顶点1 ，2 ，3 至多有一个 在顶点4 被( a l i c e ) 着色之前被着颜色o ，否则，由上述a l i c e 为自己选的顶点选色的方法可 知，顶点4 应被着颜色b 如果顶点1 ，2 ，3 都不在顶点4 被着色之前被着色如果在顶点4 未被着色之前，部分着色树t 中的含有顶点4 和顶点6 的树干只有一个已被着色的树叶， 即顶点6 ，则a l i c e 可先选顶点5 来着色，如果在顶点4 未被着色之前，部分着色树t 中的含 有顶点4 和顶点6 的树干只有两个或有三个已被着色的树叶，由上述a l i c e 为自己选的顶点 选色的方法可知，顶点4 应被着颜色b 若顶点l ，2 ，3 中恰有一个顶点( 不妨设点1 ) 在顶点 4 被着色之前被着a ，若顶点4 无其它邻点在顶点4 被着色之前被着色，由断言3 的证明和 上述a l i c e 为自己选的顶点选色的方法可知，点4 应被着颜色b ，或顶点5 在顶点4 被着色之 前已经被着色若顶点4 有其它邻点( 设为顶点2 ) 在顶点4 被着色之前被着色，由前面的 论证知，顶点2 只能着颜色b 且顶点4 被着色后部分着色树? 中不含顶点l 或2 或6 但含 顶点4 的树干中没有两个或三个树叶被着色因此a l i c e 可在顶点4 再有两个邻点被着颜色 d 之前先给顶点5 着色 这样我们就证明了断言4 利用断言4 及定理21 中a l i c e 给未着色的顶点u 选可行色的方法可得，a l i c e 能为顶 点u 选到可行色 因此对t 上的( 2 ，( f ) 一对策着色，a l i c e 有一个获胜对策 2 1 外部平面图上的对策着色 设g 是外部平面图，g 是g 的三角剖分 0 1 1 ， 。是g ，的顶点序列，使得 u l 与v 2 相邻，并且对任意的i2 3 ，在叭前有两个顶点与蚍相邻( 设为如m 2 ) ，且边饥啦与 外部无界面相关联这样可得到下面两个性质： 1 在g 中陇l 与2 相邻； 2 如果i j ，贝0 i t ，i 2 ) u l ，j 2 ) 引理3 1 ( a u a n ，z 7 l “肛5 ) 对g 的任一顶点，至多存在两个顶点饥与v i , 使得i 2 ：j 2 ：k 设s = v | i m 2l i 3 ，t ( 0 7 ) = 一s 因为任一顶点咙“兰2 ) 在t 中只有一个邻点 u ，( j ) ，从而t ( a ) 是一个树，也是g 的生成树，称为g 的扩展生成树根据引理3 i ，s 中至多有三条边与g 的顶点地关联，其中一条边为优靴，另两条边为v 3 u i 2 ( j 2 = ) 定义3 1 设g 是外部平面图，从a 的对偶图中删去外部无界面对应的那个顶点所得到的图 记为死，称为g 的拟对偶图，即 y ( ) = f l f ( f ( o ) ( ，o ) ) ) ； e ( t a ) = ，l ，2 l ，1 ， ( f ( g ) ，o ) ) ，且f 与，2 相邻) 引理3 2 ( c h e r t ，w u ，w o n g 旧) 设殆是2 一连通外部平面图g 的拟对偶图，则是一个 树 容易证明，的每个树叶所对应的g 的面的边界上至少有一个2 一点 定义3 2 设g = ( k e ) ，d v 若帆v d ，j u d ，使得“u e ，则称d 为g 的，个控制 集若对g 的任一控制集d ，都有j d j j d i ，则称d 为g 的最小控制集 推论3 1 设g 是外部平面图且d 2 ，g 是g 的2 连通的三角剖分若? 1 g ，是一条路，则 x 铲( g ) s5 7 证明：在着色过程中，a l i c e 只根据t ( g ) 的结构利用断言l 中选点方法来选点，而不考虑 e ( a ) ns 中的边，只在选色时才考虑这些边 设在着色过程中，t ( g ) 已被部分着色，丑，乃，1 1 m 为t ( a ) 的树干如果a l i c e 选 取了树干正的一个未被着色的顶点u ，则a l i c e 可通过下述方法为顶点u 选色； 55 | 生| 6 ：推论3 1 中图的结构示意图 图6 中u 2 是顶点的名称，数字是颜色，顶点标有数字 表明该顶点被着该数字的颜色，u 是未被着色的顶点 1 若在g 7 中，u 的已被着色的邻点只用了4 种颜色，则a l i c e 给“着第五种颜色 2 若在g 中，“的已被着色的邻点用了5 种颜色，只要证明部分着色的g ，中没有如 图6 的结构就可以了 因为“最多只有6 个已被着色的邻点，因此图6 中“的已被着色的邻点中至多只有一 个邻点( 不妨设为吨，i = 3 ，4 ，5 ) ，它的已被着色的邻点中有一个与u 相邻设( 见图6 ) w l 为z 匆中与g 中边界上含有边u u l ，且在边m 1 1u “2 之间的面相对应的顶点 w 2 为，中与g 中边界上含有边2 ，且在边2 ，幻之间的面相对应的顶点 w 3 为殆，中与g 中边界上含有边”且在边u u 。，“u t 之间的面相对应的顶点 w 4 为2 扫中与g 中边界上含有边| a d 2 吨的面( 不妨设这个面在边u u 。，u 2 ”：之间) 相对应 的顶点 因为v 2 与u 不相邻，且g 是g 的2 一连通的三角剖分所以w 2 与 c o 。不是，中同 一个顶点从而在殆，中，顶点w 1 ， 2 ，w 3 ，讪不在同一条路上这与，是一条路矛盾因 此g 中不可能含有如图6 的结构于是a l i c e 能为顶点选到可行色 i 推论3 2 设g 是外部平面图且d 3 , g ，是g 的2 连通的三角剖分，d 是t o , 的最小控制 集若吐驯是一条路，则) ( 铲( g ) s5 证明：在着色过程中，a l i c e 只根据t ( c ) 的结构利用断言l 中选点方法来选点，而不考虑 e ( c ) ns 中的边，只在选色时才考虑这些边 3 3 、 2 f 残麓一 。飞警 口i 呐 图7 ：推论3 2 中图的结构示意图 图7 中u ，u ，仉是顶点的名称，数字是颜色，顶点标有数字 表明该顶点被着该数字的颜色，u 是未被着色的顶点 设在着色过程中，t ( g ) 已被部分着色，丑，噩，了k 为t ( g 7 ) 的树干如果a l i c e 选 取了树干蜀的一个未被着色的顶点u ，则a l i c e 可通过下述方法为顶点u 选色： 1 若在g 中，u 的已被着色的邻点只用了4 种颜色，则a l i c e 给着第五种颜色 2 若在g 中，“的已被着