（运筹学与控制论专业论文）关于图的均匀染色理论的继续研究.pdf

0 i 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本 文的研究作出重要贡献的个人和集体，均己在文中以明确方式标 明。本声明的法律责任由本人承担。 论文作者签名：丕白垒玺 日期： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意 学校保留或向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他 复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：鹰逸4 么 导师签名：乏定& 日期：导师签名：垒竺丛日期： 目录 中文摘要1 英文摘要i i l 第一章前言l i 1 基本概念1 1 2 图的染色理论的一些概念和结论3 1 3 研究内容及章节安排7 第二章图中只有一对邻点度数之和为2 r 的均匀染色8 2 1 背景知识8 2 2 定理2 1 的证明8 第三章平面图的均匀树染色1 6 第四章总结2 3 参考文献2 5 致谢2 9 2 3 2 5 2 9 山东大学硕士学位论文 关于图的均匀染色理论的继续研究 李海伦 ( 山东大学数学学院，济南，山东2 5 0 1 0 0 ) 中文摘要 本文考虑的图均为有限、简单、无向图，对于任意一个图g ，的顶点集合，阶( 顶 点数) ，边集合，边数，最大度，最小度，围长，直径和面集，分别用以g ) ，i g i ，( g ) ，i e l ， ( g ) ，6 ( g ) ，烈g ) ，d ( g ) 和尺g ) 来表示在不引起混淆的情况f ，我们把( g ) ，文g ) ， 烈g ) ，钡g ) 简记为a ，6 ，g 和z 图g 的一个正常缸顶点染色是指k 种颜色在以g ) 上的一种分配，使得任意两 个相邻的顶点分配以不同颜色若图g 有一个正常k 顶点染色，就称g 是k 一顶点可 染色的图g 的点色数是指使g 有正常肛顶点染色的数k 的最小值，用名( g ) 表示 设妒是图g 的一个正常的顶点染色，若妒的任何两种不同颜色所染的顶点数目 至多相差1 ，称妒是g 的一个均匀染色如果妒足图g 的一个均匀肛顶点染色，称驴 是g 的一个均匀扣染色图g 可进行均匀k 一染色的最小整数k 称为g 的均匀色 数记为肌( g ) 现在已经有了很多关于图的均匀染色的结论，比较著名的是h a j n a l 和s z e m e r 6 d i 得到的这个结果： h a j n a l s z e m e r 6 d i 定理：给定一个正整数，如果一个图g 最大度不超过，那么 这个图g 存在一个均匀p + 1 ) 染色 关于均匀染色理论，有以下两个猜想 猜想l ：设g 是一个连通图如果g 既不是完全图，奇圈又不是完全二部图 k z 。+ i 2 。+ l a ( g ) = ，那么g 存在均匀一染色 猜想2 ：设r 3 ，如果对于图g 的任一条边妙，都有d c x ) + 彤) 2 r ，并且g 不 能均匀r 染色，那么g 一定含有辟+ l 或者2 ，。沏为奇数) 本文所得到的第一个结论是证明了猜想2 在一种特殊情况下是成立的 山东大学硕士学位论文 定理2 1 当， 3 时，在图g 中只有一对邻点，怕满足吠) + 政) = 2 r , 其余 各对邻点的度数之和都小于2 r , 那么图g 可以均匀，染色 在本文中，我们还定义了一种新的染色一树染色图g 的也k ，d ) 一树染色是指把 图g 的点集分解为n ，圪，圪，即用t 中颜色对图g 的顶点进行染色，使得对每个 巧，( i i 力，它的导出子图g 【k 】的任何一个分支都是直径至多为疋最大度至多为 d 的树，( 七0 d o ) 图g 存在化k d ) 树染色的最小的t 称之为g 的( k ，d ) 一树色 数，记为疋d ( g ) 图的均匀i t ，k ，d ) 一树染色是指g 存在一个( t ，k ，d ) 一树染色，v l ，v 2 ，坼是各个 颜色的顶点集合，并且对于任意的i 和以l i f ) ，都有l 一i v j ll 1 图g 存在 均匀( t ，l 【，d ) 一树染色的最小的t 我们称之为g 的均匀( k ，d ) 树色数，记为成。，( g ) 图的全均匀( t ，l 【，d ) 树染色是指对所有的f ，g 都存在一个均匀( ，k ，们一树 染色，图的全均匀( k ，d ) - 树色数记为戚g ) 若k = + o o ，d = + o o ，我们就把( t ，kd ) 树染色称为t 树染色，把均匀( t ，k ，d ) - 树染色称为均匀t 一树染色最小的t 一树染色称 为点荫度，均匀t 一树染色中最小的t 称之为均匀点荫度，记为v a 2 ( g ) ，全均匀点荫度 记为v a 2 ( g ) 针对均匀树染色，主要得到了下面的两个结论： 定理3 1 设g 为一甲面陶且围长5 则全均匀点荫度阳。( g ) 3 定理3 2 设g 为一甲面图且围长6 若g 为森林，则全均匀点荫度m 5 ( g ) = i ； 否则全均匀点荫度v a 2 ( g ) = 2 关键词：均匀染色；几乎均匀染色；树染色；均匀树染色；全均匀点荫度； i i f 山东大学硕士学位论文 s o m ef u r t h e rr e s e a r c h e so nt h ee q u i t a b l e c o l o r i n go fg r a p h s h a i l u nl i ( s c h o o lo fm a t h e m a t i c s ，s h a n d o n gu n i v e r s i t y , j i n a n ，s h a n d o n g2 5 0 10 0 ，p r c h i n a ) a b s t r a c t a l lg r a p h sc o n s i d e r e di nt h i sp a p e ra r ef i n i t e , s i m p l ea n du n d i r e c t e dg r a p h s f o rag r a p hg ， w eu s e 以g ) ，l g i ，e ( g ) ，陋l ， ( g ) ，6 1 6 3 , 反g ) ，矾g ) a n d f ( 6 3t od e n o t et h ev e r t e xs e t , t h eo r d e r , t h ee d g es e t ，t h es i z e ，t h em a x i m u m ( v e r t e x ) d e g r e e ，t h em i n i m u m ( v e r t e x ) d e g r e e ，t h eg i r t h , t h e d i a m e t e ra n dt h ef a c es e to fg s o m e t i m e s ，w ed e n o t ea f g ) ，6 ( 6 3 ，反g ) ，碳g ) a sa ，坑ga n ddi n s i m p l e ak - v e r t e xc o l o r i n go fgi sa l la s s i g n m e n to fkc o l o r s ，l 2 屯t ot h ev e r t i c e so fg t h e c o l o r i n gi sp r o p e ri fn ot w od i s t i n c ta d j a c e n tv e r t i c e sh a v et h es a m ec o l o r gi sk - v e r t e x c o l o r a b l e i f gh a sap r o p e rk - v e r t e xc o l o r i n g t h ec h r o m a t i cn u m b e r , x ( g ) o f gi st h em i n i m u mkf o rw h i c h gi sk - e o l o r a b l e i f 从g ) = 允gi ss a i dt ob ek - c h r o m a t i c i fgh a sap r o p e rk - v e r t e xc o l o r i n ga n di t sc o l o rc l a s s e sd i f f e rb ya tm o s to n e t h egi ss a i d t ob ee q u i t a b l yc o l o r e dw i t hkc o l o r s t h es m a l l e s ti n t e g e rnf o rw h i c hgc a nb ee q u i t a b l yc o l o r e d w i t hnc o l o r si sc a l l e dt h ee q u i t a b l ec h r o m a t i cn u m b e rx e ( 6 3 t h e r ea r eal o to f c o n c l u s i o n si nt h ea r e ao f e q u i t a b l ec o l o r i n g o n eo f t h ef a m o u sc o n c l u s i o n i sp r o v e db yh a j n a la n ds z e m e r 6 d it h a tf o ra n yi n t e g e r ，i fa ( g ) ， t h e ngh a sa n ( k + 1 ) 一 e q u i t a b l ec o l o r i n g r e c e n tr e s e a r c h e sf o c u so nt h en e x tt w oc o n j e c t u r e s c o n j e c t u r el ：f o ra n yc o n n e c t e dg r a p hg ，e x c e p tt h ec o m p l e t eg r a p h ，t h eo d dc y c l ea n dt h e c o m p l e t eb i p a r t i t eg r a p hk 2 m + i ，2 m + i ，a ( g ) = a ，名e ( g ) ( g ) c o n j e c t u r e2 ：l e t ，3 1 fgi sag r a p hs a t i s 够i n gd ( 曲+ 曲2 rf o re v e r ye d g e 叼略a n d gh a sn oe q u i t a b l er - c o l o r i n g , t h e ngc o n t a i n se i t h e rk r + io r 砀2 r mf o rs o m eo d dm i nt h i sp a p e r , t h en e x tt h e o r e mi sp r o v e dw h i c hi sas p e c i a li n s t a n c eo fc o n j e c t u r e2 t h e o r e m2 1 ：l e t ，3a n dgb eag r a p hs u c ht h a tt h e r ei so n l yo n ep a i ro fv e r t e xv a v b ( g ) ，t h es u m 以屹) + 硪v b ) = 2 r ，a n dt h es u mo f o t h e rp a i ro f v e r t i c e sa r es m a l l e rt h a n2 r , t h e ng h a sa ne q u i t a b l ec o l o r i n gw i t hrc o l o r s i i l ( e q u i t a b l e ，f u l l ye q u i t a b l e ，r e s p e c t i v e l y ) t - t r e ec o l o r i n g t h e ( e q u i t a b l e ，f u l l ye q u i t a b l e ) v e r t e x a r b o r i c i t yi st h es m a l l e s ti n t e g e rtf o rw h i c hgh a sa ( e q u i t a b l e ，f u l l ye q u i t a b l e ，r e s p e c t i v e l y ) t - t r e e c o l o r i n g ，d e n o t e db yv a ( g ) ( v a 。( g ) ，i , a 5 ( g ) ，r e s p e c t i v e l y ) i nc h a p t e r3o ft h i sp a p e r w eg e tt h ef o l l o w i n gt h e o r e m s ： t h e o r e m3 1l e tgb eap l a n n e rg r a p ha n dt h eg i r t hg t g ) 5 t h e nv a 5 ( g ) 3 t h e o r e m3 2l e tgb eap l a n n e rg r a p ha n dt h eg i r t h 双g ) 6 t h e nv a = - ( g ) 2 ，m o r e o v e r m 2 ( g ) = ii f a n do n l yi f gi saf o r e s t _ k e y w o r d s ：c o l o r i n g ；e q u i t a b l ec o l o r i n g ；( t ，后，叻- t r e ec o l o r i n g ；e q u i t a b l e ( ，k ，力一t r e ec o l o r - i n g ；f u l l ye q u i t a b l e ( f ，j i ，一t r e ec o l o r i n g ；e q u i t a b l ev e r t c xa r b o r i c i t y ； i v 山东大学硕士学位论文 第一章前言 图论是一门应用十分广泛且内容非常丰富的数学分支，是近年来较为活跃的数 学分支之一它起源很早，瑞士著名数学家欧拉( l e u l e r ) 在1 7 3 6 年解决了当时颇为 有名的一个数学难题，即哥尼斯城堡七桥问题，从而促进了图论的诞生和发展，成为 了图论和拓扑学的创始人2 0 世纪，图论的发展进入了黄金时代，图论的应用渗透到 许多其他学科领域如物理、化学、信息学、运筹学、博弈论，计算机网络、社会学， 以及集合论、矩阵论等从2 0 世纪5 0 年代始，计算机的迅速发展 也有力的促进了图 论的发展 图的染色理论是图论中的一个重要分支，在现实生活中有很多问题，例如排序问 题、工作分配问题、时间安排问题、无线电频率分配问题、卫星通讯问题、交通控制 问题等最终都可以归结为图的染色问题染色按照点边的不同又分为点染色，边染 色和全染色等 四色猜想足图论染色问题上最著名的问题四色猜想是英国青年学生f r a n c i s g u t h r i e 在1 8 5 2 年提出来的，当他给英国地图染色时发现4 种颜色是必要的于是向他 的哥哥f r e d e r i c kg u t h r i e 提出出如下猜想： 任何地图上的国家只需要4 种颜色来染，使得任何具有共同边界的两个国家 颜色都不相同 f r e d e r i c k 证明不了，转而请教他的老师一当时伦敦大学教授数学家a d em o r g a n 这位教授也无法证明，就写信给爱尔兰的数学家w r h a m i l t o n h a m i l t o n 同样也无法 证明起初这个问题并没有引起数学家的重视，认为是一个不证即明的事实但经过 一些尝试之后，发现并不是那么回事1 8 7 8 年，伦敦数学会负责人a c a y l e y 向伦敦数 学会成员正式宣布了这一问题，引起了数学界的广泛关注，于是形成了著名的四色 猜想在1 8 9 0 年，h e a w o o d 证明出乎面图的色数是不大于5 的，这是在四色定理证明 过程中的一个进步，但是在此后的一个多世纪中都没有人能够彻底解决这个问题 直到1 9 7 6 年美国的a p p e l 和h a k e n 借助于高速电子计算机用了1 2 0 0 多个小时证明了 四色猜想成立但是迄今为止，人们仍然没法在不借助计算机的情况下证明四色定 理 1 1 基本概念 本文考虑的图均为有限、简单图首先我们介绍一些常用的图论术语我们通 常称三元集合g = g ( 以g ) ，e ( g ) ，尺g ) ) 为一个图，在小引起混淆的情况下也可以记为 山东大学硕士学位论文 6 | - g ( k e ，f ) ，其中y ( g ) o 称为图g 的顶点集合，坎g ) 的元素为图g 的顶点，图 g 的顶点个数称为它的阶；以g ) 称为图g 的边集合，e ( g ) 的元素为图g 的边；当 l 玖g ) ue ( g ) i o o 时，称图g 为有限图，否则称图g 为无限图对于图g 中的顶点h 和v ，若边e = w e ( g ) ，则称 和v 相邻，“和v 互为邻点；称“和v 是e 的端点，材和 v 分别与e 关联若g 的边e 和有一个公共端点，则称g 和相邻在图g 中与顶点 材相邻的顶点的全体叫作甜的邻域记作n o ( u ) 称n o ( u ) 为顶点u 的度数记作如( “) 称度数为k 的顶点为“点我们用以g ) ，i g i ，e ( g ) ，“g ) ，( g ) ，烈g ) 和甙g ) 分别表示g 的项点集合，阶( 顶点数) ，边集合，边数，最大度，最小度和围长在不引起混淆的情况 下 ( g ) ，即) 和烈g ) 可分别简记为a ，6 和g 对于图g = ( k e ) 和图h = ( 矿，e ) ，若有形e e ，则称图是图g 的一 个子图对于矿以g ) ，我们把图g 中属于的顶点以及与中的点关联的边 都删除所得到的图记作g 或g 一矿对于h g ) ，我们把由矿作为顶点集， e = e l e = l ，v e ( g ) ，1 1 ) v 作为边集的图叫做g 中由顶点子集矿导出的子图，记作 g 【】 图g 的途径是一个有限非空的点边交替序列t o = v o e lv i e 2 e k v k ，使得对i i 3 时，在图g 中只 有一对邻点，怕满足西) 十矾) = 2 r , 其余各对邻点的度数之和都小于2 ，的情况进 行了分析，并且借用了h a k i e r s t e a d 和a v k o s t o c h k a 在文献【1 4 】所使用的思 想，通过反证法证明出了4 个结论相悖的断言，从而得到了下面的这个结论： 定理2 1 当， 3 时 在图g 中只有一对邻点满足吠) + 烈v b ) = 2 r ，其余各 对邻点的度数之和都小于2 _ 那么图g 可以均匀卜染色 在第三章中，我们主要是对乎面图的树染色进行了研究，得到了5 个引理： 引理3 1 对于一个图g ，若存在t 个顶点v l ，v 2 m ，使得 i n ( 坼) i v i + l 。v t l 2 i 一1( f = 1 2 ，) 若g f m j 存在一个均匀t 树染色，则g 也存在一个均匀t 一树染色 引理3 2 设g 为围长4 的平面图，则烈g ) 3 引理3 3 设g 为围长3 的平面图，则至少有下列结论之一成立 ( 1 ) 烈g ) s1 ，即存在一个度数为l 的点v ； ( 2 ) 存在一条边“v e ( g ) ，使得吠l ，) = 2 ，讲d 6 ； ( 3 ) 一个i 一度点至少相邻i 一1 个2 一度点。( f = 7 ，8 。9 ) ； ( 4 ) 一个3 度点至少相邻2 个3 一度点和一个度4 的点； 引理3 4 设g 为围长6 的甲面图，则d ( g ) s 2 引理3 5 设图g 为围长6 的甲面图，则有下列结论之一成立 6 山东大学硕士学位论文 ( 1 ) g ) 1 ，即存在一个度数为1 的点k ( 2 ) 存在一条边u v ( g ) ，使得硪h ) = 2 ，硬d 4 ； o ) 每个5 一度点“都与5 个2 度点u l , u 2 朋，u 4 ，5 相邻 并且针对图的全均匀点荫度m 5 ( g ) 利用上面的5 个引理得到了下面的这两个主 要结论： 定理3 1 设甲面图g 的围长5 ，则旷( g ) 3 定理3 2 设甲面图g 的围长6 ，则2 ( g ) = 2 ；若g 为森林，则m 5 ( g ) = 1 第四章主要是对全文的总结与概括 7 山东大学硕士学位论文 第二章图中只有一对邻点度数之和为2 r 的均匀染色 2 1 背景知识 随着图论的发展，图的均匀染色理论在我们的现实生活中也有了越来越广泛的 应用，现在的很多学者都对其表现出浓厚的兴趣，并且好多都做了深入的研究，得出了 很多针对图的均匀染色的结果，其中一个影响比较大的理论就是h a j n a l 和s z e m e r 6 d i 在1 9 7 0 年做出的下面这个结论： h a j n a l - s z e m e r d i 定理【7 】：给定一个正整数以如果一个图g 最大度不超过，那 么这个图g 存在一个均匀p + 1 ) - 染色 后来的很多学者都想把这个问题的结论限制得更紧一些，也就足想证明出w m e y e r 1 9 7 3 年在文献【5 】5 中所提出的均匀染色猜想( e c c ) ： 猜想l ：对于任意一个既不是完全图也不是奇圈的连通图g ，有x e ( g ) s ( g ) 但遗憾的是至今为止对这个定理还没有给出一个完美的证明，后来人们尝试从 别的角度去对猜想的条件进行限制，比较流行的一种就足考虑图g 中任意两邻点的 度数之和，h a k i e r s t e a d 和a v k o s t o c h k a 在【1 4 】给出了下面的这个猜想： 猜想3 ：设r 3 ，如果对于图g 的任一条边砂，都有硪工) + m ) 2 r ，并且g 不能均 匀卜染色，那么g 一定含有机i 或者2 ，。伽为奇数) 从这里我们也能看出，其实猜想3 是比猜想1 还要强的，并且在文献【1 4 】中， h a k i e r s t e a d 和a v k o s t o c h k a 还得到了下面的这个结论： 引理2 1 ：在图g 中，如果任意边x y e ( g ) 都满足破x ) + a t y ) 2 r + 1 ，那么图g 可 以均匀( ，+ 1 ) 一染色 在这里我们主要借鉴h a k i e r s t e a d 和a v k o s t o c h k a 在文献【1 4 】中证明 引理2 i 所使用的方法，对猜想3 中的一种特殊情况进行了分析，从而得出了下面的 结果 定理2 1 当， 3 时，在图g 中只有一对邻点v a ，怕满足政) + 碳v b ) = 2 r ，其余各 对邻点的度数之和都小于2 ，时，图g 可以均匀，一染色 2 2 定理2 1 的证明 现在开始对定理2 1 的证明，首先来看，如果图g 中的任何一对邻点工、y ，都有 以j ) + m ) 2 r 一1 ，由引理2 i ，可以很容易得到图g 是可以均匀，染色的 8 山东大学硕士学位论文 现在令，3 ，并且在图g 中仅有一对邻点x 、y 满足谀工) + 心) = 2 r 首先假设igi 是可以被，整除的否则假设igi - 驴一p ，( p 【r l 】) 接下来我们定义g 为g 与 的集厶 其中图g 和图知是不相交的那么ig l 可以被，一整除，并且同时满足igi 原 来的假设条件所以说，如果在图g 7 上存在均匀，染色，那么在同样的染色在g 上 也是均匀的由此可以得出假设igi = r s 对结论的证明是没有影响的 我们利用反证法来证明定理2 1 ，设图g 是一个反例假设v a ，在图g 中满足 ( g ) ，饿v 口) + 硪) = 2 r 并且战) 蹦v h ) 假设点是点v h 的一个邻点，并且v c = 岛由引理2 1 可知图g e 可以均匀， 染色由于是反例，那么也就是说g 足不能均匀严染色的，这也就说明在g e 的均匀 卜染色中，、是在同一个颜色集合v 里由于政叱) + 硪) = 2 r ，硪) 放) 并且在 图g 中至多有一对邻点的度数之和为2 那么可以得到以，一1 ，并且在g e 的均 匀，染色中，至少存在一个颜色的集合，使得在中没有定点与点相邻那么我 们可以把点染一卜集合中的颜色，仍然可以得到g 一个正常点染色，也就足说可 以把点心移到集合中，从而可以得到图g 一个新的r 染色，并且在这种新的染色 中，除了iv t f ) i = v 一1 = s l ( 称这个集合为小集合) ，iv + i = 1w + | _ s + l ( 称这 个集合为大集合) 之外，其余每种颜色的集合中顶点的个数都为量称这种染色为几乎 均匀染色 如果对图g 给出一个几乎均匀染色，在这个染色中有一个小集合v 一( 有可能 不存在大集合v + ) ，现在我们在g 中定义一个有向辅助图q - t = 何：首先何中的顶 点定义为中同色点的集合，当且仅当在u 中存在点x 在中没有邻点时，存在有向 边u w e ( 爿) 在这种情况下我们称x 相对于形中是可移动的如果在图硝中存在 一条由到旷的有向路那么称在图倒是可达的很明显，旷本身在图w 就是 可达的 引理2 , 2f 1 4 1 如果在图g 中存在一个几乎均匀染色，并且v + 是可达的，那么这 个图存在一个相同色数的均匀染色 e l 我们用舅= 贸t f ) 代表几乎均匀染色中所有可达点的集合，用b 代表其余不可 达点的集合，那么可以得到旷贝，由于我们用的是反证法，那么由引理2 2 可以得 到v + 召下面令a ：- - - _ u , 7 1 ，b ：= u 黩所：= 研i ，q ：= i 够i 从而可以得到1 4 1 = m s 一1 ， i b i = q s + 1 由上面的叙述和定义可以得到下面这个结论： 对于任一顶点，口，在贝的任一点集中至少有一个邻点， 从而可以推出a a ( v ) 胁 9 山东大学硕士学位论文 进而还可以得到： s g e b 2 r 一1 2 m = 幻一1 由引理2 1 ，我们可以推出： g 陋】的每一个子图都可以均匀酽染色 ( 2 ) 对于任一可达集u 贝，我们把舅中的集合进行以下的分类，当xe 巩并且 在图纠一u 中存在一条x 旷路时，就把所有的x 组成的集合定义为s u ：= s u ( d ， 其余的定义为t u ：= 7 - u ( f ) ：= q - ! ( s u + ，并且如果s t = 贸一以我们把u 称为终点， 否则称u 为非终点从定义中可以看出，如果u 是非终点，那么7 0 o 按照如下的方式定义一个非空集合舅7 ：= 贸7 舅：如果m = 0 ，令用：= 贝= 旷否则，旷为非终点，并且旷也是存在的，这就表明非终点的集合是非空的选定 一个非终点使得1 7 0 i 最小，并且令贝一7 - v ，a 7 ：= a 7 ：= u 舅，f ：= 们：= 阴1 引理2 3 集合贸7 满足下面两个条件 ( 1 ) 集合贝中的每一个点都足终点 ( 2 ) 对于任一顶点x 爿7 ，都有以( x ) 用一f 一1 证明：如果删= 0 ，那么旷是唯一的可达点，并且还是终点，从而可以得到用= 舅， 这样( 1 ) 式和( 2 ) 式都很容易得出当所 0 时 u 贝是一个非终点，舅，_ 7 - v 假设 x e 死，那么乃c7 - v ，由于选定的。乃是最小的，所以可以得到x 为终点，这样就满足 了条件1 在有向图w 中，对于用7 = q - 中的任一集合，在s ，中都不存在它们的可到达邻 点这也就足说对于贝中的任一点x ，在sl ，的肌一t 一1 个集合中，都至少有一个邻点， 这样就可以得出条件2 口 对于g 中的任何一条边z v ，如果z w 舅7 ，y b ，并且满足n ) = z l ，那么我们 称秒为s o l o 边，s o l o 边的两个端点称为s o l o 点，并且我们把这两个端点互相称作特殊 邻点 引理2 4 设贸，若：足s o l o 点，那么z 在舅一形的每个集合中都有一个 邻点并且幽( 刁所一1 证明我们运用反证法z 足s o l o 点，那么z 在集合b 中有一个特殊邻点_ 但 在某个集合x 贸一w 中不含有邻点由于是终点，那么在甜一形存在一条由x 到 旷的路咒把z 移到x 中，1 ，移剑形中，由假设可得r ：= x + ：是独立集，并且由于砂 足s o l o 边，那么可以得到：= 缈十y z 也是独立集这样我们就可以得到图g a 十纠 的几乎均匀染色厂。矿+ ) = x + ：并且在棚广) 中存在一条由矿( 广) 到旷( 广) 的有 向路矿：= 尹+ v + ( 厂) 一x 由引理1 ，g a + 叫有一个均匀州一染色居l ，由( 2 ) 式g 【明一y 有一个均匀q 染色h 2 那么h - u 办2 就是图g 的均匀卜染色，这与图g 不能均匀，一染 1 0 山东大学硕士学位论文 色的假设矛盾，证毕 如果一个几乎均匀卜染色厂满足下面