（计算机软件与理论专业论文）若干图的等全着色及彩虹支配问题的研究.pdf

大连理工大学硕士学位论文 摘要 图的等全着色是图的着色问题中的难题之一。对图的等全着色问题的研究不仅具有 重要的理论意义，而且在安排课表、频率分配等领域有很广泛的应用。图的彩虹支配问 题是图的支配问题中比较活跃的研究领域之一。图的彩虹支配问题的研究在优化理论、 通讯网络设计与分析、网络搜索、模式识别等许多领域有很广泛的应用，对其研究具有 现实意义。 目前国内外已有结果给出对于最大度不超过3 的图的等全着色数小于等于5 的界， 还给出路径、圈、太阳图的2 彩虹支配数的精确值，但未给出广义p e t e r s e n 图尸( 2 ) 和 p ( 2 k + 1 ，k ) 的2 彩虹支配数的精确值。 本文主要通过计算机计算及数学推理相结合的方法，研究了图的等全着色及2 一彩虹 支配问题。对3 正则图如f l o w e rs n a r k 及其相关图、g o l d b e r gs n a r k 及其相关图、t w i s t e d g o l d b e r gs n a r k 及其相关图和b l a n u 誊as n a r k 图的等全着色进行研究。给出这些图的等全 着色数为4 本文还对广义p e t e r s e n 图p ( n ，2 ) 和p ( 2 k + 1 ，k ) 的2 一彩虹支配问题进行研究。给出对 于所有的n ，广义p e t e r s e n 图p ( n ，2 ) 的2 彩虹支配数的精确值为： 以2 ( p ( n ，2 ) ) 当n m o d l 0 = 0 , 3 ，4 ，9 ， 当nm o dl0 = 1 , 2 ，5 ，6 ，7 ，8 而对于任意k 2 时，广义p e t e r s e n 图p ( 2 k - i - 1 ，k ) 的2 一彩虹支配数为： 以2 ( p ( a k + 1 ，七) ) 当k m o d 5 = 1 , 4 ， 1 ，当k m o d 5 = 0 , 2 ，3 还给出广义p e t e r s e n 图尸( ，z ，2 ) 的2 一彩虹支配方式。 关键词：等全着色；f l o w e rs n a r k ；g o l d b e r gs n a r k ；b l a n u 茑as n a r k ；彩虹支配；广 义p e t e r s e n 图 l ， + r_l 1l 锄一5锄一5 ，、j 4 4 一 “一5“一5叭一5眦一5 大连理工大学硕士学位论文 r e s e a r c ho ne q u i t a b l et o t a lc o l o r i n ga n dr a i n b o wd o m i n a t i o no fs o m e g r a p h s a b s t r a c t e q u i t a b l et o t a lc o l o r i n gi so n eo ft h eh a r d e s tp r o b l e m si ng r a p hc o l o r i n g t h er e s e a r c ho n e q u i t a b l et o t a lc o l o r i n gh a sn o to n l yi m p o r t a n tt h e o r e t i c a l ，b u ta l s ov a r i e da p p l i c a t i o n si ns u c h f i e l d sa ss c h e d u a la n dt i m e t a b l e ，c h a n n e la s s i g n m e n tp r o b l e m r a i n b o wd o m i n a t i o ni so n eo f h o tf i e l di nd o m i n a t i o n r e s e a r c ho nr a i n b o wd o m i n a t i o nh a sp r a c t i c a ls i g n i f i c a n c ei nt h e f i e l do fo p t i m i z a t i o n ，d e s i g na n da n a l y s i so fc o m m u n i c a t i o nn e t w o r k s ，n e t w o r ks e a r c ha n d p a t t e mr e c o g n i t i o n a tp r e s e n ts e v e r a la u t h o r sh a v es h o w nt h a tag r a p hw i t hm a x i m u md e g r e en o tm o r et h a n 3h a sa tm o s t5 - e q u i t a b l et o t a lc o l o r i n g ，a n dg i v eo u tt h ee x a c tv a l u eo f2 - r a i n b o wd o m i n a t i o n n u m b e ro fp a t h ，c y c l e ，s u ng r a p h ，w h i l et h ee x a c tv a l u ef o r2 - r a i n b o wd o m i n a t i o nn u m b e ro f g e n e r a l i z e dp e t e r s e ng r a p hp ( n ，2 ) a n dp ( 2 k + 1 ，k ) a r es t i l lo p e n t h i sp a p e rm a i n l yu s e st h em e t h o di n t e g r a t i n gw i t hc o m p u t e ra n dm a t h e m a t i c a la n a l y s i s t os t u d ye q u i t a b l et o t a lc o l o r i n ga n d2 - r a i n b o wd o m i n a t i o np r o b l e m w es t u d yt h ee q u i t a b l e t o t a lc o l o r i n go f3 - r e g u l a rg r a p hs u c ha sf l o w e rs n a r ka n di t sr e l a t e dg r a p h s g o l d b e r gs n a r k a n di t sr e l a t e dg r a p h s ，t w i s t e dg o l d b e r gs n a r ka n di t sr e l a t e dg r a p h ，b l a n u 誊as n a r k ，a n ds h o w t h a tt h ee q u i t a b l et o t a lc o l o r i n go ft h e s eg r a p h sa r e4 w es t u d yt h e2 - r a i n b o wd o m i n a t i o n n u m b e ro fg e n e r a l i z e dp e t e r s e ng r a p hp ( n ，2 ) a n dp ( 2 k + 1 ，后) a sw e l l ，a n ds h o wt h a tt h e2 - r a i n b o wd o m i n a t i o nn u m b e ro f g e n e r a l i z e dp e t e r s e ng r a p h sp ( n ，2 ) i s ： 以坳力，懈。， 当n m o d l 0 = 0 , 3 ，4 ，9 ， 当nm o dl0 = 1 , 2 ，5 ，6 ，7 ，8 a n dt h e2 - r a i n b o wd o m i n a t i o nn u m b e ro fg e n e r a l i z e dp e t e r s e ng r a p hp ( 2 k + 1 ，七) f o rk 2i s ： 当k m o d 5 = 1 , 4 ， 当k m o d 5 = 0 , 2 ，3 w es h o wt h e2 - r a i n b o wd o m i n a t i o no fg e n e r a l i z e dp e t e r s e ng r a p hp ( n ，2 ) a n dp ( 2 k + 1 ，k ) a s i i i 若干图的等全着色及彩虹支配问题的研究 w e l l k e yw o r d s ：e q u i t a b l et o t a lc o l o r i n g ；f l o w e rs n a r k ；g o l d b e r gs n a r k ；b l a n u as n a r k ； r a i n b o wd o m i n a t i o n ；g e n e r a l i z e dp e t e r s e ng r a p h i v 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 蕴土! 至3 鱼堕篮鲻丝翅圣盈隧娅 作者签名：鼍瞄塾一 日期：丝年丝月j 呈日 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题 作者签名： 导师签名： 大连理工大学硕士学位论文 引言 图论是组合数学的一个重要分支，也是离散数学的一个重要组成部分，它在数学领 域和计算科学领域都有着广泛地应用。 1 7 3 6 年，e u l e r 解决了k 6 n i g s b e r g 七桥问题，这是有文字记载的最早的图论研究文 献。因此，这一事件被大家认为是图论作为一门独立的学科出现的标志。到1 9 3 6 年， k 6 n i g 编写了第一本图论专著，总结了图论二百年发展的主要成果。 自二十世纪中期以来，现实世界的需要使得图论领域的研究呈现出蓬勃发展的趋 势。随着计算机技术的广泛应用，图论的研究也注入了新的活力，利用计算机技术解决 图论问题成为一个令人感兴趣的研究方向。1 9 7 6 年，美国的h a n k e r 等人利用计算机用 了1 2 0 0 小时的计算时间，解决了数学家们一百多年来所未能解决的一个著名的图论难 题一四色问题。这一事件表明计算机技术的应用促进了图论的研究与发展。因此，它在 图论的发展历史中占有一个重要的位置。 图论发展至今，已经积累了许多难题，至今仍找不到有效的算法去解决，如求图中 h a m i l t o m 回路，r a m s e y 问题，笼问题以及计算任意图的支配数问题等等。这些问题均 属于n p 完全问题。 自从1 8 5 2 年四色猜想的提出，在着色问题的研究就没有间断过。而且着色的应用 广泛如频率分配、课表安排等。目前国内外对着色的研究集中在以下及个方面： ( 1 ) 全着色、等全着色； ( 2 ) 三一着色； ( 3 ) 循环着色。 图的支配问题是近年来图论中另一个比较活跃的研究领域。 图的支配数是在实际问题中提出的。因此，在现实生活的许多领域都有广泛的应用。 例如，在一个通讯网络的一些节点上放置发射器，要求每个发射器的节点一定和某个发 射器的节点有一个直接的通讯线路。如何选择节点，使得放置的发射器的数目最小。 对支配数的研究，目前国内外的研究集中在以下几个方面： ( 1 ) 支配数； ( 2 ) 完全支配数； ( 3 ) 边支配数； ( 4 ) 彩虹支配。 若干图的等全着色及彩虹支配问题的研究 1基本概念 本文中未定义的术语参见徐俊明图论及其应用【1 1 ，b o n d y 和m u r t y 的( ( g r a p h t h e o r yw i t ha p p l i c a t i o n s ) ) 2 1 ，h a y n e s ，h e d e t n i e m i 和s l a t e r 著的( ( f u n d a m e n t a l so fd o m i n a t i o ni ng r a p h s ) ) 【3 】和( ( d o m i n a t i o nn g r a p h s ：a d v a n c e dt o p i c s ) ) 【4 】 1 1 图 一个无向图g 定义为一个二元组( 矿，e ) ，记作g = ( y ，e ) ，其中v = 矿( g ) 是一个非 空集合，称作无向图g 的顶点集；e = e ( g ) 是由矿( g ) 中元素构成的无序对集合，即 e ( g ) = ( “，1 ，) i “，1 ，矿( g ) ) ，称为无向图g 的边集，简记为( “，v ) 为u v 无向图与有向图统称为图。本文中的图是指无向图。 边u v 的端点u 和v 称为相邻的。称点“，v 和边洲相关联，同时，也称一条边为与它 的端点相关联。若两条不同的边与一个公共的点关联，则称它们是互相邻接的边。 关联同一端点的一条边称为自环。两条或两条以上的边关联一对端点，称为多重边。 既没有环也没有重边的图称为简单图。 p = p ( g ) = | v ( g ) i 表示图g 中的顶点数，称为图g 的阶( o r d e r ) q = q ( g ) = le ( g ) i 表示图g 中的边数，称为图g 的大d 、( s i z e ) 当p = 0 的图称为空图( e m p t yg r a p h ) ，记作a 当p = 1 ，q = 0 时的图称为平凡图( t r i v i a lg r a p h ) ，所有其它的图称为平凡图。 当v ( g ) 和e ( g ) 都是有限集，则称图为有限图；否则称无限图。 本文所涉及的图均为无自回路，无重边，有限的无向图。 1 2 路与图的连通性 g 的一条通路是指一个有限非空序列w = v o e l v l e 2 v 2 e k v k ，它的项交替地为顶点和 边，使得对l f k ，e i 端点是_ 一l 和称w 是从到取的一条通路。顶点和分别 称为w 的起点和终点，而m ，1 ， ，v 称为它的内部顶点。整数k 称为w 的长。在简单图 中，通路可简单地由顶点序列来表示，即w = v o ) v 。，v ：，唯 若通路w 的边e ，e ：，e 。互不相同，则w 称为迹；这时w 的长恰好是边数。又若通 路w 的顶点v o ，v 1 ，v 也互不相同，则w 称为路。 划分是指将一个正整数k 表示为若干正整数的和，或者看作一个无序正整数组，这 些正整数的和是k 大连理工大学硕士学位论文 若一个胛阶简单图g 各点的度为盔，则分正整数k 为刀个部分的划分d ，称为是图 划分。 g 的两个顶点材和v 称为连通的，如果在g 中存在( 甜，v ) 路。规定u 和v 是连通的。 如果对g 中每一对顶点甜，v 都有一条( “，1 ，) 路，则称g 为连通图，否则称为非连通图。连 通是顶点集v ( g ) 上的一个等价关系，于是可将v ( g ) 划分为一些等价类。设v ( g ) 的所有 不同的等价类为k ，k ，圪，这g 【k ，g 吃】，g 圪】为g 的连通分支，简称分支或支。 记g 的分支个数为以g ) 于是g 是连通图当且仅当w ( g ) = 1 连结甜和v 中长度最短的通路的长度，称为u 与v 的距离，记为a ( u ，v ) d ( g ) = m a x d ( u ，1 ，) l “，v ) 为g 的直径。 1 3 正则图与完全二部图 在图g 中，如果顶点“，v 是相邻的，通常称u 是v 的一个邻接点，顶点“的邻域集合 是图g 中所有与u 相邻的顶点的集合，记作n ( u ) ，其中n ( u ) = vu v e ( g ) ) z ，】- u ) u n ( u ) ，称作顶点u 的闭邻域。 设甜v ( g ) ，称a ( u ) 刊n ( u ) i 为甜的度。图g 的顶点的最大度和最小度分别用a ( g ) 和万( g ) 表示。 若图g 的各顶点的度相同，则称图g 为正则图，若任取u v ( g ) ，d ( 甜) = k 则称图g 为k - 正则图，称它的正则度为k ，此时n ( u ) = vi 甜v e ( g ) ) 如图1 1 所示的图为3 一正则 图。 图1 13 一正则图 f i g 1 13 - r e g u l a rg r a p h 完全二部图k m 。是满足以下条件所构成的图类： ( 1 ) 顶点分为二个集合k ，其中lki = m ，l 砭卢n ； ( 2 ) 对于任意甜形，1 ，巧，若f ，则甜，v 相邻( f ，歹) = 1 , 2 若干图的等全着色及彩虹支配问题的研究 如图1 2 所示的图为k 2 。完全二部图。 我们把所= 1 时的完全二部图墨。称为星图。 图l 。2 岛4 完全二部图 f i g 1 2 k 2 ，4c o m p l e t eb i p a r t i t eg r a p h 1 4 子图与生成子图 已知图g = ( v ，e ) 和h = ( v ，e 7 ) ，如果y ( 日) v ( g ) ，e7 ( 日) e ( g ) ，并且日中边 的重数不能超过g 中对应边的重数，则称日是g 的子图( s u b g r a p h ) ，记作h g 如果日是g 的子图，并且h g ，则称h 是g 的真子图( p r o p e rs u b g r a p h ) ，并且记作 hcg 已知图日是g 的子图，并且矿( 日) = v ( g ) ，则称日是g 的生成子图( s p a n n i n g s u b g r a p h ) 如图1 3 所示。 1 5 导出子图与边导出子图 已知图g = ( v ，e ) ，s 是y 的一个非空子集，以s 为顶点集，以两端点均在s 中的边 的的全体为边集所组成的子图，称为由s 导出的g 的子图，记作g s 】或简称g s 】是g 的导出子图( i n d u c e ds u b g r a p h ) 已知图g = ( y ，e ) ，e 是e 的一个非空子集，以e 为边集，以e 中边的全体端点为 顶点集所组成的子图，称为由f 导出的g 的子图，记作g 【e 】或简称g e 】是g 的边 导出子图。 1 6图的同构 设有两个图g 1 和g ：，如果它们的顶点间有一一对应关系，并且在对应的两个顶点连 接的边也一一对应时，称g 1 和g 2 同构( i s o m o r p h i s m ) ，记作g l 兰g 2 如图1 4 所示。 大连理工大学硕士学位论文 ( 1 ) g ( 2 ) s u b g r a p ho fg( 3 ) s p a n n i n gs u b g r a p ho fg 图1 3 子图与生成子图 f i g 1 3s u b g r a p ha n ds p a n n i n gs u b g r a p h 从图g = ( 矿，e ) 中删除顶点集s 是指图g 的y s 导出子图，即从矿中删除所有s 中 所有顶点和所有与s 中顶点相关联的边而得到的子图，记作g s 厂 f 一一一 l ( 1 ) g x( 2 ) g 2 图1 。4g 1 和其同构图g 2 f i g 1 4g r a p hg 1a n di t si s o m o r p h i s mg r a p hg 2 1 7 弦图、矿太阳图 设c 是图g 上的圈，lc | 4 ，如果c 本身又是g 的导出子图，则称c 是g 的无弦圈， 特别称长度为m 的无弦圈为纯m 边形，如果g 上不存在无弦圈，则称g 是弦图。 设图g = ( y ，e ) ，v = x l ，x 2 ，以；i ，e ，k ，玎3 其中g 【x 1 ，x 2 ，以 兰c ”， 仁，e ，艺) 是独立集，且e ( g ) = 亿x t ，z 置+ ，ii = 1 , 2 ，挖) ，( 注：下标对刀取模) ，则称 图g 为n 太阳图。 若干图的等全着色及彩虹支配问题的研究 2 图的等全着色和彩虹支配问题进展 2 1 图的等全着色问题及进展 2 1 1 着色的起源及发展 图的着色问题源于一个图论历史中的一个著名问题四色猜想即四色问题。是世 界近代三大数学难题之一。 四色问题的内容是：“任何一张地图只用四种颜色就能使具有共同边界的国家着上 不同的颜色。”用数学语言表示，即“将平面任意地细分为不相重迭的区域，每一个区域 总可以用1 ，2 ，3 ，4 这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。” 这里所指的相邻区域，是指有一整段边界是公共的。如果两个区域只相遇于一点或 有限多点，就不叫相邻的，因为用相同的颜色给它们着色不会引起混淆。 四色猜想的提出来自英国。1 8 5 2 年，毕业于伦敦大学的弗南西斯格思里来到一家 科研单位搞地图着色工作时，发现了一种有趣的现象：“每幅地图都可以用四种颜色着 色，使得有共同边界的国家都被着上不同的颜色。”这个现象能不能从数学上加以严格 证明呢? 他和在大学读书的弟弟格里斯决心试一试。兄弟二人为证明这一问题而使用的 稿纸已经堆了一大叠，可是研究工作没有进展。 1 8 5 2 年1 0 月2 3 日，他的弟弟就这个问题的证明请教了他的老师、著名数学家德摩 尔根，摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名数学家 汉密尔顿爵士请教。汉密尔顿接到摩尔根的信后，对四色问题进行论证。但直到1 8 6 5 年汉密尔顿逝世为止，问题也没有能够解决。1 8 7 2 年，英国当时最著名的数学家凯利正 式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。世界上 许多一流的数学家都纷纷参加了四色猜想的大会战。1 8 7 8 - - 1 8 8 0 年两年间，著名的律师 兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家 都认为四色猜想从此也就解决了。 肯普【5 】的证明是这样的：首先指出如果没有一个国家包围其他国家，或没有三个以 上的国家相遇于一点，这种地图就说是“正规的”。如为正规地图，否则为非正规地图。 一张地图往往是由正规地图和非正规地图联系在一起，但非正规地图所需颜色种数一般 不超过正规地图所需的颜色，如果有一张需要五种颜色的地图，那就是指它的正规地图 是五色的，要证明四色猜想成立，只要证明不存在一张正规五色地图就足够了。 肯普是用归谬法来证明的，大意是如果有一张正规的五色地图，就会存在一张国数 最少的“极小正规五色地图”，如果极小正规五色地图中有一个国家的邻国数少于六个， 大连理工大学硕士学位论文 就会存在一张国数较少的正规地图仍为五色的，这样一来就不会有极小五色地图的国 数，也就不存在正规五色地图了。这样肯普就认为他已经证明了“四色问题”，但是后来 人们发现他错了。 不过肯普的证明阐明了两个重要的概念，对以后问题的解决提供了途径。第一个概 念是“构形”。他证明了在每一张正规地图中至少有一国具有两个、三个、四个或五个邻 国，不存在每个国家都有六个或更多个邻国的正规地图，也就是说，由两个邻国，三个 邻国、四个或五个邻国组成的一组“构形”是不可避免的，每张地图至少含有这四种构形 中的一个。 肯普提出的另一个概念是“可约”性。“可约”这个词的使用是来自肯普的论证。他证 明了只要五色地图中有一国具有四个邻国，就会有国数减少的五色地图。自从引入“构 形”，“可约”概念后，逐步发展了检查构形以决定是否可约的一些标准方法，能够寻求 可约构形的不可避免组，是证明“四色问题”的重要依据。但要证明大的构形可约，需要 检查大量的细节，这是相当复杂的。 1 1 年后，即1 8 9 0 年，在牛津大学就读的年仅2 9 岁的赫伍德1 6 1 以自己的精确计算指 出了肯普在证明上的漏洞。他指出肯普说没有极小五色地图能有一国具有五个邻国的理 由有破绽。不久，泰勒的证明也被人们否定了。人们发现他们实际上证明了一个较弱的 命题五色定理。就是说对地图着色，用五种颜色就够了。后来，越来越多的数学家 虽然对此绞尽脑汁，但一无所获。于是，人们开始认识到，这个貌似容易的题目，其实 是一个可与费马猜想相媲美的难题。 进入2 0 世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。 1 9 1 3 年，美国著名数学家、哈佛大学的伯克霍夫利用肯普的想法，结合自己新的设想； 证明了某些大的构形可约。后来美国数学家富兰克林于1 9 3 9 年证明了2 2 国以下的地图 都可以用四色着色。1 9 5 0 年，有人从2 2 国推进到3 5 国。1 9 6 0 年，有人又证明了3 9 国 以下的地图可以只用阴种颜色着色；随后又推进到了5 0 国。看来这种推进仍然十分缓 慢。 高速数字计算机的发明，促使更多数学家对“四色问题”的研究。从1 9 3 6 年就开始 研究四色猜想的海克，公开宣称四色猜想可用寻找可约图形的不可避免组来证明。他的 学生丢雷写了一个计算程序，海克不仅能用这程序产生的数据来证明构形可约，而且描 绘可约构形的方法是从改造地图成为数学上称为“对偶”形着手。他把每个国家的首都标 出来，然后把相邻国家的首都用一条越过边界的铁路连接起来，除首都( 称为顶点) 及铁 路( 称为弧或边) 外，擦掉其他所有的线，剩下的称为原图的对偶图。到了六十年代后期， 海克引进一个类似于在电网络中移动电荷的方法来求构形的不可避免组。在海克的研究 若干图的等全着色及彩虹支配问题的研究 中第一次以颇不成熟的形式出现的“放电法”，这对以后关于不可避免组的研究是个关 键，也是证明四色定理的中心要素。 电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了 对四色猜想证明的进程。美国伊利诺大学哈肯在1 9 7 0 年着手改进“放电过程”，后与阿 佩尔合作编制一个很好的程序。就在1 9 7 6 年6 月，他们在美国伊利诺斯大学的两台不 同的电子计算机上，用了1 2 0 0 个小时，作了1 0 0 亿判断，终于完成了四色定理的证明， 轰动了世界【7 1 。 这是一百多年来吸引许多数学家与数学爱好者的大事，当两位数学家将他们的研究 成果发表的时候，当地的邮局在当天发出的所有邮件上都加盖了“四色足够”的特制邮 戳，以庆祝这一难题获得解决。 “四色问题”的被证明仅解决了一个历时1 0 0 多年的难题，而且成为数学史上一系列 新思维的起点。在“四色问题”的研究过程中，不少新的数学理论随之产生，也发展了很 多数学计算技巧。如将地图的着色问题化为图论问题，丰富了图论的内容。不仅如此， “四色问题”在有效地设计航空班机日程表，设计计算机的编码程序上都起到了推动作 用。 不过不少数学家并不满足于计算机取得的成就，他们认为应该有一种简捷明快的书 面证明方法。直到现在，仍由不少数学家和数学爱好者在寻找更简洁的证明方法。 2 1 2 着色的基本概念 给定图g = ( v ，e ) ，称映射万：e 专 1 , 2 9 - - 3 k ) 为g 的一个k 边着色，简称边着色，称 1 ，2 ，k ) 为色集。若7 为g 的边着色且v p7 ，e ”e ，当e 与e 。相邻时，万( p ) 刀( p ”) ，则 称着色是正常的。图g 的正常k 边着色的最小值k 称为g 的边色数记为z 7 ( g ) ，简记为 z 若图g 存在一个正常k 边着色，则称g 是k 边可着色的。 有限集彳的一个划分是指满足如下条件的彳的一个子集族 4 ，彳：，a k ) ： ( 1 ) a j g ，i = 1 , 2 ，k ， ( 2 ) 彳，na j = a “，) ， ( 3 ) 4u 么2u u 4 k = a 若子集族只满足( 2 ) 和( 3 ) 我们称它为分划。 给定图g = ( v ，e ) ，称映射万：v 寸 1 , 2 ，k ) 为图g 的一个k 顶点着色，简称着色， 并且把集合 1 ，2 ，k 称之为色集。若对g 中任意两个相邻顶点u 和v 均满足万 ) 万( v ) ， 那么就称该着色为正常的。图g 的正常k 着色取最小值k 时称为图g 的色数，并且记作 大连理工大学硕士学位论文 为z ( g ) ，简记为z 若图g 存在一个正常k 着色，则称图g 为k 可着色。 给定图g = ( v ，e ) ，称映射万：yue 一 1 ，2 ，k ) 称为图g 的k 全着色。若还满足： ( 1 ) v 洲e ( g ) ，7 r ( u ) 刀( v ) ( “v ) ，z c ( u v ) 刀( v ) ，万( 圳) 万( “) ， ( 2 ) v u v ，圳。e ( g ) ，r ( u v ) l r ( u v ”) ( 圳7 洲。) ， 则称着色y 为正常的。 若图g 的所有正常k 全着色取最小的k 值称这个值为g 的全色数，记为z ”( g ) ，简 记为z 。 若图g 的顶点集矿根据着色情况，被划分为k 个相互独立的集合k ，圪并且满 足当f j 时，i 杉l i | 0 ， 该计算复杂度不接近于”1 仃一目前已知的最好的多项式近似算法是由h a l l d 6 r s s o n l l l j 提 出图的着色计算复杂度为o ( n ( 1 0 9 l o g n ) 2 l 0 9 3 ，z ) 2 1 4 着色的应用 图的着色问题反映了广泛而深刻的实际背景，它的研究带动了整个图论的发展。图 的顶点着色和边的着色为解决网络的故障检验和电路板的印刷及故障检验提供了数学 解决的方法。计算机技术为图论的研究提供有力的支持，图的着色对生物制药和新的化 学物质的生成和化学性质的检验及新的化学分子组合有理论指导意义。 如今图的着色理论在解决安排会议或考试的日程以避免冲突和安排化学品的存储 以避免互相反应等具体问题上得到广泛利用。图的着色问题也是图论中一个经典的组合 优化问题，无论在理论上还是工程应用中均具有良好的应用背景，如发射台的频率分配 问题。由于工作频率相同的发射台之间产生互相干扰的电势，为了消除干扰，给不同的 发射台分配不同的互不干扰的工作频率就是一个经典的着色问题。 若干图的等全着色及彩虹支配问题的研究 2 1 5 等全着色的发展。 自1 9 7 3 年，m e y e r 1 2 1 提出等着色猜想，给出对于任意连通图g ，如果有g k 。且 g c 2 州，贝q l ng 的等着色数是否小于等于图的最大度数。w a n g 13 1 ，l i h l l 4 1 ，y a p i 垮1 钟等 对等着色猜想进行分析，c h e n 1 7 1 ，f u r m a f i c z y k 1 8 1 等对交图的等着色进行分析。以下分别 列出他们给出的结论。 ( 1 ) 设图k 恍以为完全，部图，则以( e 。协，) ( k m 以) ，其中，1 ( 2 ) 如果图g 为线图则以( g ) = z ( g ) ( 3 ) 对于任意图g 都有z ( g ) = z ( g ) ( 4 ) 最大度( g ) 2 的二部图g 是可a ( g ) 等着色当且仅当图g 不同构于图 川砌+ 1 ( 5 ) 完全二部图为可磷着色当且仅当r 南h 例外 ( 6 ) 图g ( x ，y ) 为一个m 条边的连通二部图。设ixl _ ，z l n 2 刊yi 并且边m 满足 m iy ( g ) 一4i 的图 口2 全着色猜想成立；对于( g ) 3 9 1 9 的简单图g 有z 。( g ) 4 , 2r l4 ( 4 ) 星图k l 有等全着色数z ! ( k 。，。) = l a + + 2 il 当当n ，z ：1 1 , ( 5 ) 完伞二部图补等全着色且尼z ( m 其吆( 引= 滋三誊! ( 6 ) 如果丁为一棵树，则t 有k 一等全着色并且后z ”( 丁) ( 7 ) 图g = n k 2 + k 川，其中r 3 则z ”( g ) = 2 n + 1 ，但图g 不n - i 2 n + 1 等全着色。 ( 8 ) 猜想：对于任意图g ，都可k 一等全着色，其中k m a x z ”( g ) ，( g ) + 2 ( 9 ) 设图g 为n 个顶点且最大度a ( g ) = n 一2 ，则图g 满足猜想( 8 ) ( 1 0 ) 图g = k 棚，其中当+ 力2 + + ，的值为奇数时，图g 满足前面的结论猜 想( 8 ) w a n g t m 证明了对于最大度( g ) 3 的图g 至多5 一等全着色的。z h a n g 2 6 1 给出了某些 交图的等全着刍数。 若干图的等全着色及彩虹支配问题的研究 2 2 图的彩虹支配问题及进展 2 2 1 支配的起源及发展 要提到图的彩虹支配问题首先必须了解图的支配问题。在这一节中简要介绍支配问 题。虽然图的支配的相关研究开始于1 9 6 0 年，但这个问题的相关领域的研究最早可以 追溯一百多年前。1 8 6 2 年，j a e n i s c h 3 3 】研究了如下一个问题： 问题2 1 确定覆盖( 或支配) 一个n x ，2 国际象棋棋盘所需王后的最小个数。 在18 9 2 年出版的( ( m a t h e m a t i c a lr e c r e a t i o na n dp r o b l e m so fp a s ta n dp r e s e n tt i m e s 中，r o u s eb a l l 3 4 】总结了1 9 世纪末关于国际象棋棋盘上的组合问题的研究分为如下三 个基本类型的问题： ( 1 ) 覆盖问题 覆盖( 攻击或支配) 一个即刀棋盘上所有格子所需的某种棋子( 王、王后、马、相、车 和卒) 的最小个数。这个问题实质是在以棋盘格子为顶点，以棋子的某种走法为边所产 生的图，在该图上求其元素个数最小的支配集。 ( 2 ) 独立覆盖问题 支配一个刀”棋盘上所有格子所需的彼此互不攻击的某种棋子的最小个数。这个问 题实质是在以棋盘格子为顶点，以棋子的某种走法为边所产生的图，在该图上求其元素 个数最小的独立支配集。 ( 3 ) 最大独立集问题 在棋盘上的格子中放入某种棋子，要求任意两个棋子之间彼此互不攻击( 支配) ，按 这种方法，最多能放多少个棋子。这个问题实质是在以棋盘格子为顶点，以棋子的某种 走法为边所产生的图，在该图上求其元素个数最大的独立集。当我们选用的棋子为王后， 这个问题就是著名的。皇后问题。 1 9 6 4 年左右，y a g l o m 3 5 1 兄弟研究了这三类问题。对于棋子王、马、相和车的情形， 他们对上述问题给出了一个很好的结果。 b e r g e 3 6 1 在他于1 9 6 2 年出版的图论书中，第一次提出了图的支配数的定义( 当 时他称之为t t c o e f f i c i e n to f e x t e r n a ls t a b i l i t y ，) 同年，在o r e 3 7 1 出版的图论书中第一 次使用了图的支配集和图的支配数的概念( 他用d ( g ) 表示一个图g 的支配数) 。同时o r e 也给出了关于图的支配集最早的定理【3 7 】 到了1 9 7 7 年，c o c k a y n e 和h e d e t n i e m i 为到当时为止在支配问题领域的所有结果写 了一篇综述。在这篇综述中，c o c k a y n e 和h e d e t n i e m i 3 8 】第一次y ( g ) 使用表示一个图g 的 支配数，从此以后，支配数的概念和表示符号就固定下来，被人们接受了。 大连理工大学硕士学位论文 c o c k a y n e 和h e d e t n i e m i 的这篇文献综述开启了支配理论现代研究的序幕。到19 9 8 年为止，在这二十年中，有关支配理论的文献超过了1 2 0 0 多篇，并且还在不断地稳步 增长中。利用美国数学评论的搜索引擎，我们检索了1 9 9 8 年 - - 2 0 0 6 年间美国数学评论 收录的文献中，分类号为0 5 c ( 图论问题) 并且题目中带有支配数的文献，得到的结果如 表2 1 所示说明支配问题的研究在现代图论研究中占有一个重要的地位。 表2 11 9 9 8 2 0 0 6 美国数学评论收录的有关支配数的文章统计结果 t a b 2 1d o m i n a t i o np a p e r sf r o mm r i n19 9 8 2 0 0 6 2 2 2 支配的基本概念 文献【3 j 的附录中给出了7 0 多种支配数及相关类型的集合的定义和简单说明。在本节 中给出支配、支配数及彩虹支配的基本定义及它们相关集合的定义。 定义2 1 令集合s 是一个图g 的顶点集的子集，即s y ( g ) 如果对任意顶点 v v ( g ) ，有v n s 】，则称s 是图g 的一个支配集( d o m i n a t i o ns e t ) 如果它的任何真子 集都不是图g 的支配集，我们称s 为图g 的一个极小支配集( m i n i m a ld o m i n a t i n gs e t ) 如 果对任意一个图g 的极小支配集s ，满足is7 剧sl ，则称极小支配集s 为图g 的一个最 小支配集( m i n i m u md o m i n a t i n gs e t ) 最小支配集s 中所含元素个数称为图g 的支配数 ( d o m i n a t i o nn u m b e r ) ，记作，( g ) 定义2 2 令函数厂为图g 上每一个顶点标上一个集合的颜色，这些颜色集为集合 l ，2 ，k 的子集；也就是函数厂为v ( g ) 一尸( 1 ，2 ，尼) ) 的映射。如果图g 上有顶点 v y ( g ) 且其函数厂( v ) = 囝，而且又有u i e ( ，) 厂 ) = l ，2 ，尼 ，那么这样的函数厂就称 为图g 的k - 彩虹支配函数( k - r a i n b o wd o m i n a t i o nf u n c t i o n ) 而函数的权( w e i g h t ) ， w ( 厂) ，定义为w ( 门= ，引g ) i f ( v ) 1 给定图g 的七一彩虹支配函数( 刚凹叼的权的最小值 称为图g 的k 一彩虹支配函数，并记作( g ) 当k = 2 时，即称2 彩虹支配( 数) 。当k = 1 时，该概念就是支配的定义。 2 2 3 支配的计算复杂性 计算任意一个图的支配数是一个很复杂的问题。即使是我们把问题减小到只针对一 类具体的图来计算支配数，也不一定能够得到一个多项式时间的有效算法。 若干图的等全着色及彩虹支配问题的研究 表2 2 给出了上面介绍的两种支配数的对若干类图的计算复杂性，其中n p 表示该 问题是不能用多项式时间的有效算法解决，p 表示问题存在多项式时间的有效算法。 表2 2 支配数的计算复杂性 t a b 2 2 c o m p u t i n gc o m p l e x i t yo fd o m i n a t i o nn u m b e r 显然仅弦图的支配问题就是n p 问题。文献3 9 1 也证明了2 彩虹支配问题也是n p 完 全问题，并给出两个推论。 推论2 1 即使仅限于弦图的2 彩虹支配问题是n p 完全问题。 推论2 2 即使仅限于二部图的2 彩虹支配问题是n p 完全问题。 2 2 4 支配集的应用 在( ( f u n d a m e n t a l so fd o m i n a t i o ni ng r a p h s ) ) 的引言和第一章中，h a y n e s ，h e d e t n i e m i 和s l a t e r 等人给出了几类支配集的应用例子。 支配集和网络设计有很大关系，近年来，传感器网络和移动自组网络的应用中，连 通支配集占有一个很重要的地位。因为这两类网络的拓扑结构是随机的，不断发生变化 的。因此在网络通讯中需要构建一个虚拟的骨干网，而这个问题实质上是在一个图中寻 找连通支配集。这方面的主要讨论见文献【4 0 。4 5 1 。 2 2 5 彩虹支配的发展 b r e 誊a r ，h e n n i n g 和r a l l l 4 6 4 刀在支配的基础上提出了2 彩虹支配的定义。 b r e 誊a r 和 s u m e n j a k 3 9 1 两人对路径、圈、n 太阳图及广义p e t e r s e n 图进行了研究