（运筹学与控制论专业论文）块图的2彩虹控制问题算法研究.pdf

d i s s e r t a t i o no f m a s t e r2 011 i i i i i l | i | j | l i | j f 川j i | i i y 19 0 3 0 6 7 s c h o o lc o d e ：1 0 2 6 9 s t u d e mn u m b e r ：5 1 0 8 0 6 0 1 0 8 1 e a s tc h i n an o r m a lu n i v e r s i t y s t u d yo na i g o r i t h mo f2 一r a i n b o w d o m i n a t i o ni nb l o c kg r a p h s d e p a r t l e m ： m 句o r ： s u b j e c t ： s u p e n r i s o r ： d e p a n l m e n to fm a t h e m a t i c s o p e r a t i o n a lr e s e a r c ha n dc y b e m e t i c s g r a p ht h e o 巧a n di t sa 1 9 0 r i t h m s c h a n g h o n gl u ( p r o f e s s o r ) m a s t e rc a n d i d a t e ：y u n i n g 2 011 5 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文块图的2 。彩虹控制问题算法研究，是在华东 师范大学攻读碛左博士( 请勾选) 学位期间，在导师的指导下进行的研究工作及取得的 研究成果除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过的 研究成果对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示 谢意 、 作者签名：! 芝! 主日期：油f 降6 月l 日 华东师范大学学位论文著作权使用声明 块图的2 彩虹控制问题算法研究系本人在华东师范大学攻读学位期间在导 师指导下完成的奶劬博士( 请勾选) 学位论文，本论文的研究成果归华东师范大学所 有本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部门和相关 机构如国家图书馆、中信所和“知网”送交学位论文的印刷版和电子版；允许学位论 文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入全国博 士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采用 影印、缩印或者其它方式合理复制学位论文 本学位论文属于( 请勾选) () 1 经华东师范大学相关部门审查核定的“内部”或“涉密”学位论文+ ，于年 月日解密，解密后适用上述授权 ， ( ) 2 不保密，适用上述授权 导师签名： 本人鼢! 主复 矽f 年易月l 日 率“涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位 论文( 需附获批的华东师范大学研究生申请学位论文“涉密”审批表方为有效) ，未经上述部门 审定的学位论文均为公开学位论文此声明栏不填写的，默认为公开学位论文，均适用上述授权 呵辱硕士学位论文答辩委员会成员名单 姓名职称单位备注 任韩教授华东师范大学数学系主席 郭军伟副教授华东师范大学数学系 杜若霞副教授华东师范大学数学系 华东师范大学块图的2 彩虹控制问题算法研究 摘要 设图g 是一个简单无向连通图，厂：以g ) 一尹( ( 1 ，尼 ) 满足：对任意点 ，以g ) ，若八v ) = o ，则一定有u ” 嵋八z ，) = l ，n 此时称为图g 的肛彩虹控 制函数似r d f ) w = v 啪) 叭v ) i 称为的权重图g 的缸r d f 的最小权重称为g 的肛彩虹控制数，记作( g ) 肛彩虹控制问题就是对任意图，确定它的缸彩虹控制数 和最小权重的肛彩虹控制函数 本文在前人关于树肛彩虹控制问题的研究成果的基础上，探讨了块图的2 彩虹控 制问题的多项式时间算法首先，给出了一个以块为单位遍历块图的方式，其次分析了 一些特殊块的2 彩虹控制标记方法，并证明了块图上的2 彩虹控制问题与2 弱彩虹 控制问题是等价的定义了块图中一种特殊结构交替块列，并给出了一种查找交替 块列的算法一回溯算法并给出了一个块图的2 弱彩虹控制问题的多项式时间算法 ( m 2 - w r d f ) 本文还研究了一类特殊的c a c t u s 图一s c a c t u s 图的2 彩虹控制问题首先，研究 了圈的2 彩虹控制问题，给出两类圈中的i 型圈的最小2 彩虹控制标记方式，并证明 了这种标记方式在考虑对称性的前提下是唯一确定的其次，本文研究了不含i i 型 圈的s c a c t u s 图的最小2 彩虹控制问题，并最终给出了该问题的一个线性时间算法 ( m 2 - r d f c ) 关键词： 彩虹控制；块图；算法；c a c t u s 华东师范大学块图的2 彩虹控制问题算法研究 a b s t r a c t l e tgb eau n d i r e c ts i m p l ec o n l l e c t e d 聊ha n dl e t 厂b ea 如n c t i o nt h a ta s s i g i l st oe a c h v e n e xas e to f c o l o r sc h o o s e n 舶mt h es e tf l ，2 ，后 ；t h a ti s ，厂：以g ) 一双 l ，材) i f f o r e a c hv e r t e x1 ，以g ) t h a t 八d = 0 w eh a v eu 。州八甜) = 1 ，料，也e n 厂i sc a l l e d t h e “r a i n b o wd o m i n a t i n g6 m c t i o n ( 肛r d f ) o fg t h ew e i g h to ft h ef u n c t i o n 厂i sd e 丘n e d 嬲 从) = 炬以g ) 叭吼t h em i n i m u mw e i g h to fa 缸r d fi sc a l l e dm ek f a i n b o wd o m i n a t i o n 肌m b e ro fg ，w h i c hw ed e n o t eb ym ( g ) t h e 缸r a i n b o wd o m i n a t i o n p r o b l e mi st od e t e m i n e t h e k r a i n b o wd o m i m t i o nn u m b e ra n dam i n i m 啪肛r d fo f 狃yg r a p hg i nt h i st h e s i s ，w eb e g i i ln e wr e s e a r c ho f2 一r a 劬o wd o m i n a t i o np r o b l e mi nb l o c k g r 印h s w h i c hi sb a s e do n p r e v i o u sr e s u l t so f k r a i n b o wd o m i n a t i o ni nt r e e s f i r s t l y ，w eg i v eam e t h o d o nt r a v e l i i 培a na m i t m 巧b l o c k 髓巾hb l o c kb yb l o c k s e c o n d l y ，w ea 1 1 a l y s i sw a y so n s i g l l i n g s o m es p e c i a lb l o c b w ba l s op r o v e dm a tt h e2 一r a i n b o wd o m i n a t i o np r o b l e ma 1 1 d2 w e a k r a i n b o wd o m i n a t i o na r ee q u i 砌e n t w ed e n n eas p e c i a js 劬c t u r ei nb l o c k 伊a p l 卜- s e q u e n c e o fa l t e m a t i v eb l o c l 【s ，锄daa l g o r i 恤m ( d e 曲ea l g o r i 岫) t 0 缸da s e q u e n c eo fa j t e m a t i v e b l o c k si nb l o c k 黟a p h ，a n dg i v ea p o l y n o m i a l t i m ea l g o r i t h m ( m 2 - w i f ) f o r2 w e a kr a i n b o wd o m i n a t i o n p r o b l e mi nb l o c k 鲫h w es t u d y 也e2 - r a i n b o wd o m i n a t i o np r o b l e mo fas p e c i a lc a c t l l s 野a p h s - c a c t u s 伊印h f i r s t l 弘w es t u d yt h e2 一m i n b o wd o m i n a t i o np r o b l e mo fc y c l e s w bg i v et h em i n i m u m 2 - r a i n b o wd o m i n a t i o n ss i g n i n gm e t h o d so fo n es 够l ec y c l e s ( ic y c l e s ) ，a n dp r o v et h a t 也i s m e t h o di sd e t e 胁i n e dw h e nc o n s i d e r i n gt h es y m m e t s e c o n d l y ，w ec o n s i d e rt h es c a c t u s 铲a p h sw i t h o u t c y c l e s ，a i l dg i v eal i l l e a u rt i m ea l g o r i t h mt og e tt h em i n i m u m2 i fo f s c a c t u s 鲫h sw i 也o u ti ic y c l e s 丘n a l l y k e y w o r d s ：r a i n b o wd o m i n a t i o n ；b l o c k g r a p h s ；a l g o r i t h m ； c a c t u s i i 华东师范大学块图的2 彩虹控制问题算法研究 目录 第一章引言l 1 1 图论的基本概念l 1 2 特殊图2 1 - 3 控制集和彩虹控制集问题简介3 1 4 研究现状4 第二章块图的2 彩虹控制问题算法研究8 2 1 块图的遍历8 2 2 块图的2 彩虹控制问题的分析8 2 3 算法及其证明1 0 第三章一类特殊c a c t i l s 图的2 一彩虹控制问题2 5 3 1圈的最小2 彩虹控制函数2 5 3 2 不含型圈的s c a c t u s 图的2 彩虹控制问题研究2 9 第四章一些值得深入研究的问题3 4 第五章总结3 5 参考文献3 7 致j 射4 0 i i i 第一章引言弟一早jl 西 图论是一门将现实世界的事物及其相互联系进行抽象而研究事物联系性质的学 科一般地将事物抽象为一个点，事物之间的联系抽象为点与点之间的连线，这些点与 线构成的图形，就是“图”比如著名的握手定理就是通过这样的方式进行抽象，借助对 图的组合性质的研究得到证明的1 7 3 6 年，l e u l e r 首次运用图论作为工具解决了著名 的哥尼斯堡七桥问题，从而开创了图论和拓扑学的先河然而直到上世纪，随着计算机 理论科学的兴起，图论才重新引起数学家的热切关注并取得了长足的发展如今图论学 科已经成为组合数学和计算机理论科学的重要组成部分同时图论学科本身也形成诸 多分支，如图论算法，极值图论，代数图论，随机图论，拓扑图论等本文主要介绍控制集 问题及其衍生问题一彩虹控制问题的一些研究成果，及本人在这方面的一些工作 1 1 图论的基本概念 一般地，我们用g = ( k e ) 表示一个图g ，其中矿表示图的顶点集合，记作坎g ) ， 表示图的边集合，记作e ( g ) 图的顶点个数i h g ) i 称为图的阶，记作刀( g ) 若p e ，且 p 的两个端点为甜，v ，则称p 关联甜和v ，记作p = 鲫，并称甜和1 ，是邻接的若p = z ，v 且 z ，= 1 ，则称e 为一个环若g 中有两条边p l ，勿有相同的端点甜和v ，则称p l ，龟是g 的 重边，并将关联材和v 的重边的数目称为边z l v 的重数既没有环也没有重边的图称为 简单图如无特殊说明，本文中所涉及到的图均为简单图 若图g = ( k e ) 中存在有限顶点和边交替的序列形= 均p 1 1 ，l q v 2 鲰；( 其中 白e ( g ) ，f = l ，2 ，屯v ，h g ) ，= l ，2 ，后且毋= v f - lv f ) ，则称是图g 的一条道 路，顶点，魄称为形的端点，顶点( f = 1 ，2 ，七一1 ) 称为形的内部点，后称为形的 长边不相同的道路称为迹；内部点各不相同的迹称为路；端点重合的路称为圈，长为七 的圈称为肛圈 对图g = ( ke ) ，以是h g ) 的一个子集生成一个新的图g f = ( 巧，e ，) ；其中 甜m e f ，当且仅当蜥e 此时称g f 为以在g 中的诱导子图，记作g 吲 华东师范大学块图的2 彩虹控制问题算法研究 设“，v 是g 的两个顶点，若g 中存在一条“一y 路，则称甜和，是连通的若g 的 任意两个不相同的顶点均是连通的，则称g 为连通图将以g ) 划分为( 巧，圪，l ， 若甜，1 ，是连通的当且仅当“，v 属于同一子集k ，则称g “】，g 【圪】，g 】为g 的连 通分支 设g = ( ke ) 是一个连通图，“坎g ) ，p e ( g ) ，若g 一甜不连通，则称掰是g 的一 个割点，若g e 不连通，则称p 是g 的一条割边 设g = ( ke ) 是一个简单图，对任一顶点v h g ) ，g ( v ) = 川甜v e 称为v 的 开邻域，6 ( du 1 ， 称为其闭邻域图g 中与顶点v 关联的边数称为v 的度记作 如( d = l b ( v ) i 设d 1 和d 2 是两个点不相交的简单图，d l 和忱的笛卡尔积( c a i t e s i a np r o d u c t ) d l 口d 2 是一个简单图，其中以d l 口d 2 ) = 以d i ) 以d 2 ) ；并且对x l ，y l 坎d 1 ) ， 娩，此h d 2 ) ，( ( x l ，j c 2 ) ，( y 1 ，此) ) e ( d l 口d 2 ) 当且仅当或者x l = y l 且( 娩，此) e p 2 ) ， 或者娩= 此且 l ，乃) e 1 ) 1 2 特殊图 本节主要介绍本文中研究的一些特殊图的定义 定义1 2 1 对于图g = ( k e ) ，若矿= hu 圪；hn 圪= 0 ；且对任一条边p = 甜1 ，e 有： 甜巧，v 圪，则称g 是一个二部图 定义1 2 2 一个图被称为弦图，如果该图中任意一个长度大于3 的圈都有一条弦 弦图的提出起源于完美图理论它包含了图论中许多常见的特殊图，比如树，分裂 图，区间图，块图等本文主要涉及树和块图 定义i 2 3 设g 是一个简单图，如果g 是连通图且没有圈，则称g 为树 定义1 2 4 图g 的一个块是指g 的最大连通子图且没有割点若g 的每个块都是完全 图，则称g 为块图 显然每个块都是局的块图就是树因此树是块图的一个子类 2 华东师范大学块图的2 彩虹控制问题算法研究 1 3 控制集和彩虹控制问题简介 本节将引入彩虹控制问题，在此之前有必要给出经典控制集问题的定义和背景 控制集问题是图论及组合优化理论中的重要研究领域，由于应用广泛，控制集问题 的研究也就逐渐得到了深入和扩大，各种新的控制参数也不断涌现图的控制集问题的 研究已经有很长的历史，可回溯到1 9 世纪中期的一种象棋游戏，即著名的五皇后问题 现实生活中类似的问题还有很多比如如何在城市中设置最少的巡逻警察岗哨，使得 每个街道都有警力覆盖这个问题实际上也可以抽象为在图上寻找最小控制集的问题 图论中一个图的控制集定义如下： 定义1 3 1 设图g = ( 形e ) ，s 是y 的一个子集如果矿一s 中每个顶点都有一个邻点 在s 中，则称s 是图g 的一个控制集 定义1 3 2 一个图g = ( ke ) 的控制数y ( g ) = m i n 例峪是图g 的一个控制集 如果 g 的一个控制集正好包含7 ( g ) 个顶点，则称它为g 的一个最小控制集控制集问题就 是对任意一个给定的图，确定它的控制数和最小控制集 彩虹控制问题最早由b o 鲥a nb r e a r 等人于2 0 0 5 年发表的论文p a i r e d d o m i n a t i o n o f c 眦e s i a np r o d u c t so f 聊h sa n dr a i n b o wd o m i n a t i o n 【3 】中提出经典控制集问题实际上 是研究如何用一种“警卫”去控制一个图即图中的点要么是一个“警卫”，要么跟“警 卫”相邻而彩虹控制问题研究多种“警卫”控制的问题，图中的点要么是某一种或几 种“警卫”，要么其相邻的点上的“警卫”中包含了所有种类的“警卫”显然彩虹控制问 题是经典控制集问题的一个推广 下面给出彩虹控制的准确定义 定义1 3 3 设图g = ( k e ) ，厂：坎g ) _ 尹( ( 1 ，后) ) ，满足：对任意点v 以g ) ，若 八d = d ，则 ij 八“) = l ，材 “新v 】 此时称厂为图g 的缸彩虹控制函数( 肛i f ) w = 饨郴) i 八v ) i 称为厂的权重图g 的肛r d f 的最小权重称为g 的缸彩虹控制数，记作( g ) 红彩虹控制问题就是确定 图的缸彩虹控制数和最小权重的肛r d f 3 华东师范大学块图的2 一彩虹控制问题算法研究 1 4 研究现状 本节主要介绍彩虹控制问题的研究现状虽然彩虹控制问题在2 0 0 5 年才最先被人 们研究，但目前也已经取得了一些比较重要的结果本节从三个方面进行介绍： 基本性质 对彩虹控制问题基本性质的研究主要集中在一般图彩虹控制数的界的估计，以及 一些简单图类的彩虹控制数的计算上 b o 蜀a nb r e 吾a r 等人在 2 】中将一般图g 的彩虹控制问题与g 口凰的控制数问题 联系起来设巩缸) = x l ，娩磁 ，则图g 的所有肛r d f 构成的集合与g 口凰的所有 控制集构成的集合之间存在着一一对应关系设厂是g 的一个缸) f ，则 巧= u ( u 而) 1 ) ， ，“g ) f 啾v ) 是g 口瓦的一个控制集反之亦然这就证明了如下性质： 性质1 4 1 2 】对任意图g ，当后1 时，揪( g ) = y ( g 口凰) 通过对g 口厨的控制集问题研究，h 锄e 1 1 和r a n 发现了彩虹控制问题的一系列 重要性质在 2 0 中他们刻画了m ( g ) = ，( g ) 的一类图的许多性质，并证明了对任意 树ly ( 丁) 0 ) 时，对任意的，以g ) ，八v ) f 1 ，2 ； ( 2 ) 当聆= 4 小+ 2 沏0 ) 时，或挖= 3 时，最多存在一个1 ，以g ) ，八v ) = f 1 ，2 ) 证明：( 1 ) 当刀= 4 聊咖 o ) 时，设1 ，以g ) ，但八v ) = 1 ，2 ) 由于厂是g 最小的2 i f ， 因此v 的两个邻居v l ，屹的函数值应均为o 此时删去1 ，v l ，晚，剩余一个长度为4 聊一3 2 5 华东师范大学 块图的2 彩虹控制问题算法研究 的路p 很显然p 的最小标记方式与v ，v l ，v 2 的标记无关而妒) = l ( 4 聊一3 ) 2 j + l = 2 聊一1 + l = 2 聊，故w = ，) ，r 2 ( d + 2 = 2 聊+ 2 而，r 2 ( g ) = 【4 ，z 2 j + r 4 ，押4 卜【4 聊4 j = 2 朋， 故w 忱( g ) 这与厂是最小的2 r d f 矛盾故当，z = 4 聊( 聊 0 ) 时，对任意的 1 ，h g ) ，八1 ，) 1 ，2 ) 同理可证当，z = 4 川+ l ；4 肌+ 3 沏0 ) 时，对任意的v 以g ) ，八d 1 ，2 ( 2 ) 当疗= 3 时，g 为恐完全图的2 一彩虹控制数为2 ，如果出现两个点标记为 1 ，2 ，那么权重至少为4 当”= 4 ，”+ 2 ( ，z 0 ) 时，钯( g ) = l ( 4 聊+ 2 ) 2 j + ( 4 ， + 2 ) 4 1 一【( 4 ，押+ 2 ) 4 j = 2 ，竹+ 1 + 1 = 2 ，竹+ 2 设1 ，h g ) 且八d = 1 ，2 1 同( 1 ) 中的操作，可得w = 2 朋+ 2 = 忱( g ) 因此可 以存在一个点v 以g ) ，使八d = l ，2 ) 设除v 外还有一点矿h g ) 且八v ，) = 1 ，2 1 当v ，v ，相邻时，设，l 屹是w ，的邻点故八1 ，1 ) = 八也) = o 删去y l ，矿，v 2 ，得 到一个长度为4 聊一2 的路尸，且其最小2 彩虹控制标记与v l ，v ，矿，屹的标记无关故 w = 4 + 忱( p 4 脚一2 ) = 2 朋+ 4 忱( g ) 这与厂是最小的2 - i m f 矛盾因此v 的邻点 中不会有点的函数值为 l ，2 ) 当y ，距离为2 时，同可得：w = 4 + 竹2 ( 一3 ) = 2 聊+ 3 忱( g ) 这与厂 是最小的2 r d f 矛盾因此与v 距离为2 的点中不会有点的函数值为f 1 ，2 当，矿距离为3 时，同可得：w = 4 + 竹2 ( - 4 ) = 2 m + 3 忱( g ) 这与 是最小的2 r d f 矛盾因此与，距离为3 的点中不会有点的函数值为 l ，2 当v ，矿的距离超过3 时，将v v ，及其邻居删去，得到两条路p l ，p 2 ，它们的最小 2 彩虹控制标记与v ，v ，及其邻居无关，且其长度和为4 朋+ 2 6 = 4 聊一4 设p l 的长度 为屯则b 的长度为4 m 一4 一七故： w ( 力= 竹2 ( p 1 ) + 忱( 尸2 ) + 4 = 【尼2 j + 1 + 【4 聊一4 一尼2 j + 1 + 4 = 恤2 j + l + 2 m 一2 一【尼2 j + l + 4 = 2 聊+ 4 竹2 ( g ) 这与是最小的2 一r d f 矛盾因此与1 ，距离超过3 的点也不会有点函数值为 l ，2 综合可知，以g ) 中不可能有更多的点函数值为 l ，2 口 2 6 华东师范大学块图的2 彩虹控制问题算法研究 为了记叙方便，我们将引理3 1 1 中满足条件( 1 ) 的圈称为i 型圈，满足条件( 2 ) 块 称为i i 型圈 设g 中的点按照顺序依次为1 ，l ，屹，下面介绍一种圈的2 彩虹标记方式，称 为4 周期标记： 方法1 设圈g 的点按顺序依次为v l ，屹，h ，厂：h c 刀) 一尹( l ，2 ) ： 八+ 1 ) 八+ 2 ) 八v 船3 ) 心堍心 = 1 ) ( 2 ) ) = 0 = 2 ( 1 ) = 0 其中j | 0 下面证明i 型圈可以通过方法l 找到一个最小2 一彩虹控制函数 引理3 1 2i 型圈通过4 周期标记可以找到一个最小2 彩虹控制函数 证明：设g 是i 型圈，厂是g 的点按照方法1 形成的函数 对于位于一个完整周期中的四个点+ l + 2 椭，心t + 4 来说，显然前三个点都已 经满足2 。彩虹控制条件如果该周期后面还有周期，那么按照标记规则，下一周期的第 一个点刚好使“4 满足控制条件因此检查已有标记是否让所有点都满足控制条件， 只需检查的标记即可 一 当疗= 4 优时，最后一个点正好是最后一个周期的最后一个点，而，l 又是第一 个周期第一个点，因此满足控制条件；当，z = 4 聊+ l 时，八m + 1 ) = l l ( 2 ) ，满足控 制条件；当，z = 4 聊+ 3 时，八+ 3 ) = 2 ) ( l ) ，也满足控制条件因此i 型圈g 经过方法 l 标记后形成的函数厂是c 的一个2 r d f 下面证明厂是最小的2 r d f 当万= 4 聊时，y r 2 ( g ) = 2 历，而w = 2 ( 4 聊4 ) = 2 肌= 竹2 ( g ) ； 当聆= 4 m + l 时，y r 2 ( g ) = 2 聊+ 1 ，而w = 2 ( 4 聊4 ) + l = 2 聊+ l = 忱( g ) ； 当，z = 4 m + 3 时，忱( g ) = 2 掰+ 2 ，而以门= 2 ( 4 m 4 ) + 2 = 2 所+ 2 = 忱( g ) 故厂是g 的一个最小2 r d f 口 2 7 华东师范大学块图的2 一彩虹控制问题算法研究 由于i 型圈的特殊结构，可以证明其所有的最小2 r d f 均只能通过选取不同的点 作为v l ，不同方向( 顺时针或逆时针) 对点排序，再通过4 一周期标记得到 定理3 1 1 设g 是i 型圈，则g 的所有最小2 一r d f 对点的标记都是通过4 一周期标记 得到的 证明：设厂是g 的一个最小2 1 m f ，且厂对g 的标记方式满足4 周期标记的规则若 存在一个g 是g 的一个最小2 r d f ，且g 对g 的标记方式不满足4 周期标记的规则， 那么厂通过对点的标记的改变可以得到g 由于w = w ，因此由到g 的置换只能通过标记的移动或标记的变化来实现， 不能通过增加或减少标记实现 由引理3 1 1 知，移动标记只能从标记不为空的点移动到标记为空的点，否则将出 现某个点标记为 l ，2 ，这是矛盾的 当，z = 4 聊时，任意一个标记的移动都会造成两个标记为空的点相邻在没有点标 记为 l ，2 的前提下，这两个点的控制条件都不能被满足 当刀= 4 聊+ 1 时，此时厂中存在两个点标记相同且相邻如果将其中一个点v 的标 记移动到相邻的标记为空的点上，则，不满足控制条件如果将v 移动到其他位置，则 会出现两个标记为空的点相邻若移动其他点的非空标记，也会出现上述情况 当，z = 4 优+ 3 时，此时厂中存在两个标记相异且不为空的点相邻如果将其中一个 点1 ，的标记移动到相邻标记为空的点上，此时整个标记仍满足控制条件，但这种标记方 式仍满足4 周期标记的规则其余移动方式均会出现两个标记为空的点相邻 综上，标记的移动不能将厂置换为g 若将厂中所有标记为 l 的点和标记为 2 的点对换，则得到的标记仍然满足4 周 期标记的规则若只将一部分点的标记改变，则必然会造成某个标记为空的点不满足 控制条件因此标记的变化也不能将厂置换为岳 故g 不存在 口 定理3 1 1 实际上说明了考虑对称性时，i 型圈的最小2 i m f 在结构上是可以唯 一确定的不同之处仅在于“起点”的函数值是( 1 或者 2 ，以及标记的方向是顺时针 还是逆时针 2 8 华东师范大学块图的2 彩虹控制问题算法研究 3 2 不含i i 型圈的s c a c t u s 图的2 彩虹控制问题研究 由于i i 型圈的最小2 彩虹控制标记方式有多种( 有一个点标记为 1 ，2 l 的和没有 点标记为 l ，2 ) 的) ，故含有i i 型圈的s c a c t u s 图的2 彩虹控制问题非常复杂，本文仅 讨论不含型圈的情形 首先介绍一种给s c a c t u s 图中的圈排序的方式 任意选取一个圈，记作c l ，将其相邻的圈依次标记为c 2 ，c 3 ，q ，然后再将与这 些圈相邻的圈依次标记为q + 1 ，2 ，瓯册；重复这个过程，直到所有圈有一个序号， 这就完成了一个s c a c t i l s 图中圈的排序 设g 是一个圈已经排序的s c a c t u s 图寻找g 的最小2 彩虹控制标记的算法设 计思想是：首先找到g 7 = c luc 2 的最小2 彩虹控制标记，再将c 3 加入，按情况讨论 g ，- g ，uc 3 的最小2 彩虹控制标记依此类推，直到所有的圈完成标记，此时g 7 = g ， 且g 7 已经完成最小2 彩虹控制标记 可以看到g 7 是一个不断扩大的图设c 是新进入算法的圈，且它通过点，与g 7 中的圈c ，相邻，则称v 是c 的悬挂点，c 称为的悬挂图 首先，当g 7 只有一个圈c l 时，只要按照上节讨论的方法就能找到c 1 的最小2 彩 虹标记 当g 7 = c 1uc 2 时，设c 2 的悬挂点为v ，则对g 7 进行如下操作： i 操作1 将 ，标记为 1 ) ( 或 2 1 ) ，再按4 一周期标记方式分别对c l 和c 2 进行标记 引理3 2 1 操作l 能够给出g ，- c luc 2 的最小2 彩虹控制标记 证明按操作1 标记完毕后，c l 和c 2 的标记都是最小的，因此c l 或c 2 的权重都不可 能更小又由引理3 1 1 可知，c l 和c 2 的最小标记中不会有点标记为 l ，2 ，因此c l ，c 2 的最小标记可共用的权重最多为1 ，而此时1 ，的权重恰好为l ，因此操作l 给出的标记 方式是最小的 口 当圈g 进入算法时，设c 通过v 悬挂于c ，可能出现以下三种情况： ( 1 ) p 除去v 外在g 7 中只有一个割点； ( 2 ) c 除去v 外在g 7 中有两个或以上割点； ( 3 ) v 恰好是c ，在g 7 中的一个割点 2 9 华东师范大学块图的2 彩虹控制问题算法研究 此时对g 7uq 进行如下操作( 以下c 7 的割点均指c 7 在g 7 中的割点) ： 操作2 ： 当v 的标记不为0 ，则按照1 ，已有的标记对g 进行最小2 彩虹控制标记； 如果v 恰好是c ，的一个割点( 上述情况( 3 ) ) ，且v 标记为0 ，则进行； 如果c 7 除，外还有别的割点( 上述情况( 1 ) ，( 2 ) ) 且1 ，的标记为d ，则进行； 如果将1 ，的标记变为( 1 或f 2 ，再对g 7 重新标记( 除e 的割点外，其余割点的 标记不改变) 后g 的权重未变，则以1 ，的标记对q 进行最小的2 一彩虹控制标记否则 直接以v 标记为d 对g 进行最小的2 彩虹控制标记 如果c ，除y 外只有一个割点z ，( 上述情况( 1 ) ) 若c ，的长度为4 垅+ l 或4 惭+ 3 则只要以甜为定点改变c ，的标记方向即可使v 标记非空，再按照v 的标记对g 进行最小2 彩虹控制标记 若c ，长度为4 研，如果将甜的标记改为其在c ，中相邻点的标记，再对g ，重新标记 ( 除c ，的割点外，其余割点的标记不改变) 后g 7 权重未变，则新的标记中v 的权标记不 是0 ，再以v 的标记对g 进行最小的2 彩虹控制标记若将g 7 按上述方式重新标记后 g 权重增加，则还原g 7 的标记，并将，标记为 l 或f 2 ，对g 进行最小2 彩虹控制标 记 如果c ，除v 外在g 7 中有两个或两个以上割点( 上述情况( 2 ) ) 由圈的排序方法可知，此时c ，中只有一个割点甜连接的圈的序号比c ，的序号小， 且其余割点仅悬挂一个圈或几个圈，这些圈在g ，中都只有一个割点 若c ，的标记为最小2 彩虹控制标记，如果e 的长度为4 埘+ l 或4 肌+ 3 则只要以 z ，为定点改变c ，的标记方向即可使y 标记非空若对g 重新标记后g 权重没有增加， 则按照v 的标记对q 进行最小2 彩虹控制标记若将g 7 按上述方式重新标记后g 7 权 重增加，则还原g 7 的标记，并将v 标记为 l 或 2 ，对g 进行最小2 一彩虹控制标记如 果c 7 的长度为4 聊，若将z ，的标记改为其在c 中相邻点的标记，再对g 7 重新标记( 除 e 的割点外，其余割点的标记不改变) 后g 权重没有增加，则新的标记中v 的权重应 为l ，再以，的标记对q 进行最小的2 一彩虹控制标记若将g 7 按上述方式重新标记后 g 7 权重增加，则还原g ，的标记，并将，标记为 l l 或 2 l ，再对g 进行最小2 彩虹控制 标记 若c ，的标记不是最小2 彩虹控制标记，设与，最近的两个标记为非空的割点为 ，l ，屹若v l v 2 问点的个数为偶数，则v l ，屹中必有一个邻点( 位于v l ，屹之间的一侧) 的标记不是o ，将该点标记为0 并重新对v l ，v 2 之间的点进行标记，则之前标记为o 的 3 0 华东师范大学块图的2 彩虹控制问题算法研究 点的标记不为o ，则1 ，标记不为0 此时以，的标记对q 进行最小2 一彩虹控制标记若 1 ，l ，屹间的点的个数为奇数，将v 标记为 l 或 2 l ，对g 进行最小2 彩虹控制标记 引理3 2 2 设g 7 是一个已经标记为最小2 彩虹控制标记的不含i i 型圈s c a c t u s 图，圈 c 七通过点 ，悬挂于g 7 的一个圈c ，则操作2 能够给出g 7u g 的最小2 一彩虹控制标记 证明设g 的最小权重为w ( g ，) 情形一，当v 已经标记为 l 或 2 1 时按操作2 标记后，g 7 与q 的标记都已经最 小，且g 与g 最多公用权重l ，而，的权重恰好为1 ，故操作2 给出的标记方式是最小 的 情形二，当v 恰好是c 在g 7 中的一个割点时如果将，的标记变为 1 ) 或 2 ，再 对g 7 重新标记( 除c ，的割点外，其余割点的标记不改变) 后g 的权重未变，则按操作 2 标记后，g 与q 的标记都已经最小，且g 7 与q 最多公用权重1 ，而v 的权重恰好为 1 ，故操作2 给出的标记方式是最小的否则，若改变v 的标记会使g 7 的权重至少增加 l ，但至多增加g 7 与q 的公用权重l ，故操作2 给出的标记方式是最小的 情形三，当c ，除v 外在g 7 中还有别的割点，且v 的标记为0 时 子情形一，当c ，除1 ，外在g 7 中仅有一个割点 若e 的长度为4 聊+ l 或4 聊+ 3 则按操作2 操作并标记后，g 7 的权重没有增加， q 的标记是最小的，且公用权重为l ，故操作2 给出的标记方式是最小的 叠 若c ，的长度为4 m 如果“旋转”c ，的标记不改变g 7 的权重，( 这种情况是存在 的，事实上，如果在e 进入算法时，不能通过调整g 7 一p 的标记在不改变其权重的情 况下将c 的悬挂点标记为非空，那么按照操作2 对g 7 进行标记后，c ，就满足这种情 况) 那么就能将，的标记变为非空，按操作2 标记后，g ，的权重没有增加，g 的标记是 最小的，且公用权重为l ，故操作2 给出的标记方式是最小的若不然，v 的标记有两种 可能当，标记为o 时，g ug 的最小权重为w 1 = w ( g 7 ) + 竹2 ( c 七) 当v 标记为 1 或 2 时，不改变c ，其余点的标记就是当前情况下g 7 最小的标记方式，此时g 7 与g 公 用权重l ，故此时g uq 的最小权重为忱= w ( g 7 ) + 1 十竹2 ( q ) 一1 = w 卜虽然这两种 标记方式的权重相同，但操作2 给出的标记方式可能会让之后进行的步骤中权重变得 较小故可见操作2 给出的标记方式是最小的 子情形二，当c ，除，外在g 7 中至少有两个或两个以上割点 当已有的标记方式是最小时，且c ，除v 外割点的标记情况满足相应条件，则 按照操作2 进行操作和标记后，g ，的权重不变，q 的标记是最小的，且公用权重为 3 l 华东师范大学块图的2 彩虹控制问题算法研究 l ，故操作2 给出的标记方式是最小的若不满足相应条件，则改变g 7 的标记会使 g 7 的权重至少增加1 而将q 进行标记后，g 7 与g 的公用权重最多为1 故此时 w ( g ug ) w ( g 7 ) + 忱( q ) 而按操作2 不改变g 7 的标记直接将1 ，标记为1 1 或 2 再对q 进行标记后，w ( g ug ) = w ( g 7 ) + 竹2 ( c 七) 故操作2 给出的标记方式是最小的 当c ，已有标记方式不是最小时，可知，必然在以两个标记不为空的割点1 ，l ，v 2 为 端点的路上当，l ，屹间有偶数个点时，则按照操作2 进行操作和标记后，g 7 的权重 没有增加，q 的标记是最小的，且公用权重为l ，故操作2 给出的标记方式是最小的 当v l ，屹间有奇数个点时，1 ，的标记有两种可能当1 ，标记为0 时，g 7ug 的最小权重 为w i = 以g 7 ) + 竹2 ( g ) 当v 标记为 1 或 2 时，不改变c ，其余点的标记就是当前 情况下g 7 最小的标记方式，此时g 7 与g 公用权重l ，故此时g ，ug 的最小权重为 w 2 = w ( g 7 ) + 1 + y r 2 ( q ) 一l = w 1 虽然这两种标记方式的权重相同，但操作2 给出的标 记方式可能会让之后进行的步骤中权重变得较小故可见操作2 给出的标记方式是最 小的 综上所述，操作2 会给出一个g uq 的最小2 彩虹控制标记 口 以下算法给出了不含i i 型圈的s c a c t u s 图的最小2 彩虹控制标记方式 算法3m 2 i f c 输入：不含型圈的s c a c t u s 图g ； 输出：g 的最小2 彩虹控制标记 初始化：将g 中的圈按规则排序为c 1 ，c 2 ，g ，图g ，- o g = c luc 2 ； 对guc 2 进行操作l ； f o r ( i _ 3 ：k ) 对g ug 进行操作2 ； g 7 = g 7ug ； e n d f o r 下面对算法进行证明： 定理3 2 1 设图g 是一个不含i i 型圈的s c a c t u s 图，刀( g ) = 疗，则算法3m 2 一r d f c 能 在d ( 胛) 时间内给出g 的一个2 彩虹控制标记方式，并且这个标记是权重最小的 3 2 华东师范大学块图的2 彩虹控制问题算法研究 证明：由于算法运行完毕时，g 的每个点都遍历一次，且每个点被重复遍历的次数不会 超过图中圈的个数，故总运行时间应该是d ( 胛) 再证明算法给出的标记方式是g 的权重最小2 彩虹控制标记方式由于每个圈最 终的标记方式要么是该圈的最小标记，要么是在最小标记的基础上将某个标记为o 的 点改为标记不为0 因此每个点都满足2 彩虹控制条件 因此只要证明当最后一个圈执行完算法后，所有己标记的圈所形成的图的标记是 权重最小即可 当c i 和c 2 进入算法时，由引理3 2 1 可知，g ，- c luc 2 的标记是权重最小的 假设当第七个块运行完算法后前尼个块所构成的图g 7 的标记是权重最小的则当 第七+ 1 个圈执行完算法后，由引理3 2 2 可知，g 7uq + l 的标记是权重最小的 由归纳假设知，当最后一个圈执行完算法后，g 的标记是权重最小的 口 3 3 第四章一些值得深入研究的问题 第二章主要叙述了作者关于块图的2 彩虹控制问题的算法研究由于树是块图的 一个子类，因此作者的工作推广了前人关于2 彩虹控制集问题的结果但是遗憾的时 由于块图结构的复杂性，暂时无法将前人关于树的缸彩虹控制问题的算法进行进一步 推广因此下述问题是值得进一步研究的： 问题l 块图的肛彩虹控制问题是否存在多项式时