（应用数学专业论文）概率方法与图的染色问题.pdf

摘要 本文共分四个部分 第一部分主要是引入一些在本文中经常出现的的基本概念和主要性质并对某些概 念给出具体实例 第二：部分介绍了第一矩量原理，m a r k o v 不等式以及四种形式的l o v 血s z 局部引理的内 容：给出了这几种概率方法在超图上的应用，用几种思路找到了超图存在2 一可染色的不 同条件，其中着重对一般形式的l o v g s z n 部引理给山应用实例，即无圈边染色，证明了：当 图g 的围长大于等t - 7 0 0 a l o g 时，图g 的无圈边色数小于等于+ 2 然后用概率论的方 法i 币明t ) l 种形式的l o v g s z n 部引理，并从中发现几种l o v h , x z n 部引理之间的关系，找出 其不同的适用范围 第三部分主要讨论了邻点可区别的边染色这一概念，用第一矩量原理m a r k o v 不等式 以及几种形式的l o v a s z 局部引理分别得到了任一最大度为d 的图g 的邻点可区别的边色 数 第四部分引入了邻点可区别的全染色这一新的概念，并用第一矩量原理，m a r k o v 不等 式以及几种形式的l o v 如z 局部引理分别得到了任一最大度为d 的图g 的邻点日j 区别的全 色数 l l a b s tr a c t t h e r ea r ef o u rp a r t si nt h i sp a p e r i nt h ef i r s tp a r t ，w ei n t r o d u c es o m ef m l d a m e n t a lc o n c e p t sa n di n a i np r o p e r t i e st h a t o f t e nu s e di nt h ep a p e r s o m ee x a m p l e sw h i c ha r ed i r e c t e dt o w a r d ss o m ec o n c e p t s & r e g i v e n i nt h es e c o n dp a r t ，w ei n t r o d u c et i l ef i r s tm o m e n tp r i n c i p l e im a r k o v si n e q u a l i t y a n df o u rk i n d so fl o v 舂s zl o c a ll e m m a ，a n dg i v ed i f f e r e n ta p p l i c a t i o n si nh y p e r g r a p h s w i t ht h e s ep r o b a b i l i s t i cm e t h o d s v ef i n dd i f f e r e n tc o n d i t i o n sf o rah y p e r g r a p h ob e2 c o l o r a b l ew i t hs o m ek i n d so ft h i n k i n g s a m o n gt h e mt h ea p p l i c a t i o n sw i t ht h eg e n e r a l l o c a ll e m m aa r ct h em o s ti m p o r t a n t ，s u c ha sa c y c l i ce d g ec o l o r i n g so fg r a p h sw ep r o v e t h a tt h ea c y c l i ce d g ec h r o m a t i cu u m b e ro fg i sl e s st h a no re q u a lt oa + 2f o ra n yg r a p hg w h o s eg i r t hi sa t , l e a s t7 0 0 g l o g w ep r o v ef o u rk i n d so fl o v a s zl o c a ll e m m aw 让ht h e m e t h o do fp r o b a b i l i t yt h e o r ya n dd i s c u s st h er e l a t i o n s h i pa a n o n gt t m ma u dt h e i rd i f f e r e n t a p p l i c a b l er a u g e s i nt h et h i r dp a r t ，w ed i s c u s s “a d j a c e n t v e r t e xd i s t i n g u i s h i n ge d g ec o l o r i n g s ”w e o b t a i nt h ea d j a c e n t v e r t e xd i s t i n g u i s h i n ge d g ec h r o m a t i cn u l n b e r sw i t ht h ef i r s tm o l n e n t p r i n c i p l e ，m a r k o v si n e q u a l i t ya n ds o m ek i n d so fl o v a s zl o c a ll e m m a ，r e s p e c t i v e l y i nt h el a s tp a r t ，w ed i s c u s san e wc o n c e p t “a d j a c e n t v e r t e xd i s t i n g u i s h i n gt o t a lc o l o r i n g s ”w eo b t a i nt h ea d j a c e n t v e r t e xd i s t i n g u i s h i n gt o t a lc h r o m a t i cn u m b e r sw i t ht h e f i r s tm o m e n tp r i n c i p l e ，m a r k o v si n e q u a l i t ya n ds o l n ek i n d so fl o v 如zl o c a ll e m m a ， r e s p e c t i v e l y u 1 独创性声明 本人声明所旱交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得两北师范大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已存论文中作了明确的说 明并表示谢意。 学位论文作者签名：弛必日期：垫笪 关于论文使用授权的说明 本人完全了解西北师范大学有关保留、 交论文的复印件，允许论文被查阅和借阅； 采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：域 导师签名： 使用学位沦文的规定，即：学校有权保留送 学校可以公布论文的全部或部分内容，可以 趁 日期：) 砩r _ 上- j l 日i j 吾 概率方法是一种用来证明具有某些特定属性的目标的存在性的技巧从1 9 4 7 年p a u l e r d s s 在r a m s e y 数r ( k ，k ) 2 的证明中首次引入概率方法至1 j 2 0 0 2 年国际数学家大会 上n o g aa l o n 作了有关图的概率方法的一小时报告，这个新颖活跃的研究领域正受到国 际数学界的普遍关注 l o v t 氟z 局部引理是证明具有某些特定属性的目标的存在性的一个非常重要的工具 它的优点是我们只需证明具有某些特定属性的目标存在的概率值大于0 即可，即使这个概 率值非常小正凶为如此，我们研究的图类就扩展到了可以很大并且无结构性的随机图 中引理的证明很短，但发挥的作用却非常大有些学者认为，用l o v 缸z 局部引理等概率方法 解决图论中问题的成功，它的作用等同于数论向解析数论的过渡 第一矩量原理和m a r k o v 不等式是概率方法中的一个最基本的工具它用很简单的形 式将概率和数学期望之间建立起了有机的联系，同时也可以容易的过渡到l o v a s z 局部引理 中去 概率方法在很多领域中都发挥着日益重要的作用，尤其足在图的染色方面其中图的 邻点可区别的边染色是针对实际生活中的“局域网中交换机的优化连接”和“手机频率”等 问题而提出的，具有很强的现实意义将这一概念推广到图的邻点町区别的全染色研究这 一新概念需要更多的研究方法，本文在这方面作了有益的尝试用几利，不同的概率方法 得到了图的邻点可区别的边色数和图的邻点可区别的全色数 1 基本概念和性质 定义1 将随机试验e 的所有可b c , - q 果组成的集合称为e 的样本空间，记为n ：n 的 一个子集a 称为事件( e v e n t ) ；有限概率空间( q ，只) 是南一个有限的样本空间q 和概率 函数只：q 一 0 ，l 】，满足以下几点：( 1 ) b ( z ) = 1 ；( 2 ) b ( a ) = 耳( z ) ；( 3 ) 令鼻= n a 则b ( a ) = 1 一尸r ( a ) ：( 4 ) b ( a u b ) = p r ( a ) + 只( b ) 一p r ( a n b ) ；( 5 ) 耳( aub ) sb ( 4 ) + b ( b ) ，更般地，b ( ua 。) 只( 一。) ，称为概率的次可加性 t = lt 2 l 定义2 对于n 的每个z ，有只( z ) = 尚称为均匀分布；q 中的一个均匀元素是一个 随机元素，每个概率均是相等的 定义3 ”如果事件4 发生的概率不受事件b 的影响称事件a 对事件b 是独立 的：对n 个事件a l ，4 2 ，a 。若对v a 。，a ，( i j ，ij = 1 ，2 ，t t ) 有只( 4 ：n a ，) = 只( 月。) b ( a ) 成立，称事件a 1a 2 ，a 。两两独立：对 个事件a 。，月2 ，4 。，若对事件 的任意子集 a 1 a 2 ，a ) ，有耳( a ina ，) = 只( a 1 ) ，称事件4 l ，a 2 ，也互相独立 i = 2 定义4 1 i 在有限的概率空问( b n ) 随机变量是从n 到实数的函数x ( x ：n r ) ；随 机变量x 在n x 的范围内，定义了一个概；簪空间( p r 。、n x ) 、其中概牢函数尸r 。被称为块函 数，满足对每个z q ，b 。( t ) = p r ( “) l “en ，x ( “) = 。) 定义5 ”随机变量x 的期望值是e ( x ) = b ( u ) x ( w ) u 52 ff 期望的线性性e ( x ) 兰e ( 墨) = lf = l ff 证明：e ( x ) = e ( x 。) = 耳( u ) ( x 。) ( 。) = ，只) x ；) i = lu 5 2 = lo i2 ；= l lf = 只) x 。) = e ( 五) i = l u 52i = l 定义6 ”1 令a 1 ，a 2 ，一，a 。为概率空间的r 个事件对事件的集合s t 是s e e 一些事件 ( 或事件的补) 构成的任一子集，如果满足p r ( 。jna ，) = b ( a ) ，则称a 。与事件的 集合s 互相独立；以y ( 日) = 1 2 ，扎) 为顶点的有向图= ( y ( h ) ，e ( ) ) 被称作相关 图乍= 如果对所有 a ：1 i 礼) ，a ，与集合 山：( i ，j ) 仨e ( 厅) ) 中的事件互相独立 定义7 超图是图的概念的推广发y = m ，? j 2 ，t z 。) 是非空集，e = f e 。，如， t n 晶。) 是y 的子集簇_ 蔫足1 ) e i 妒( i = 1 ，2 ，) ，2 ) ue = v ，则称二元组肖= l = 1 2 l 基本概念和性质 ( vf ) 为一个超图，其中y 和e 的元素分别称为的点和边，n 称为h 的阶；如果每条超边有 同样的大小k ，则称超图是一一致的；超图的正常2 一着色是2 种颜色中的一种到每个顶点 的一种分配使得没有超边是单色的( 即边中每个项点的颜色是一样的) 例v = 口1 ，v 2 晚，) e = u 1 ) ， 吨，u 4 ) ， u 2 ，v 4 ， 1 ，吨，u 3 ，, n c 称a = ( v e ) 是一 个4 阶超图 定义8 对图g ( u e ) 映射：y ( g ) 一 1 。2 ，女) 满足对任意相邻的顶 点扎，v ，有，( u ) ，( u ) ，则称，是g 的个一正常点染色简记作一p v c ：g 称x ( c ) = r n i n f 自f g 有k 一正常点染色 为g 的点色数( 见 3 ) 对图g ( u e ) ，映射f ：e ( c ) 一 1 ，2 ，女) 满足对任意相邻的边e - ，9 2 有f ( e 1 ) r ( e 2 ) 则称，是g 的一个k 一正常边染色，简记作一p e c ，且称x 7 ( g ) = r n i n k l c 有一f 常 边染色1 为g 的边色数( 见f 3 ) 对图g ( v e ) ，映射，：v ( g ) u f ( g ) 一 1 ，2 ，* ) 满足1 ) 对任意“u ，1 ， e c g ) ，“硼，有，( w ) ，( u 叫) ；2 ) 对任意一e ( g ) ，有，( u ) l 厂( u ) ，( u ) f ( u v ) ，( u ) r ( l t y ) ，则称，是g 的一个一正常全染色，简记作k p t c ，且称地( g ) = l 伽 ；g 有一正常 全染色 为g 的全色数( 见 4 ) ) 定义9 若对阶至少是2 的连通图g ( u e ) f f t 个k p e c 酐j f ：对任意u y ( g ) ，记c ( “) = f ( u v ) b v e ( g ) ) ，如果对任意的u e ( g ) ，c ( u ) c ( ) ，则 称，为g 的一个卜邻点可区别的边染色，又称为一邻强边染色，简记作k a s e c ，且 称x ：。( g ) = n t 撕 i g 有k 一邻点可区别边染色) 为g 的邻点可区别边色数一个图g 有邻强 边染色钳g 没有孤立边 定义1 0 【6 】若对阶至少是2 的连通图g ( u e ) 的一个一p t c 自g f ，对任意v ( g ) 、 记c ( u ) = ，( u ) ) u j ( 妣，) i u e ( g ) ，w y ( g ) ) 如果对任意的“u e ( g ) 有c ( “) c ( tr ) ，则称，为g 的一个一邻点可区别的全染色简记作一a v d t c 且称) ( m ( g ) = r a i n k t g 有k 一邻点可区别全染色，为g 的邻点可区别全色数 3 2 几种概率方法及应用 一第一矩量原理“如果e ( x ) t , n p , ( x t ) 0 证明：反设只( x t ) 一0 ，即不存在x f 的情况即对所有的i x ，均有i t ，所 以e ) = ip 4 x = i ) - b ( x = i ) = f - 一( x = i ) = - 1 = ，得至u e ( x ) f 与条件矛盾! 应用情况：多应用于x 是正整数值j | e ( x ) 0 另一种说法：p r ( x e ( x ) ) 部分求和) 2 t p d x = g ) = 异( x = z ) = f 只( x ) i tl t 所以e ( x ) c - b ( x f ) 号蚌( x ) s ( x ) 1 应用情况：多应用于x 是正整数值上l e ( x ) 0 ) e ( x ) 定理2 1 ”1 如果h 是超图且i e ( h ) 2 一1 ) 条超边，明 显地第一矩量方法将不适用于这种情况但是对于概率方法来说，目标的实现并不需 4 52 几种概率方法及应用 要很高的概率，只需要存在正概率即可，为此，考虑如下极端情况：选择一个均匀的随 机的顶点2 一染色，对每条超边e ，定义a 。为e 是单色边的事件，假设k 一致超图是由m 条完 全不交的超边组成，在这种情况下，事件a 是互相独立的，则没有这种事件发生的概率 是f 1 2 - ( “一- p 0 ( 无论m 多大) ，因此，超图是2 一可染色的现在考虑一般的超图日，因为 一些超边相交，所以事件 l 。旧e ( ) ) 不是独立的l o v a s z 局部引理就是针对这种情况， 只要充分地限制依赖事件的数量，仍可说目标实现的概率为正值 l o v a s z 局部引理有以下几种形式： 1 最简单形式9 i 考虑( 典型的坏的) 事件的集合s ，使得对每一个a e ，有( 1 ) 只( ，4 ) p l ；( 2 ) a 与m 多d 个事件之外的其它事件的集合互相独立如果4 p d 1 ，则= 中所有事件都不发生的概率 是正的 注：不等式4 p d 1 可被e p ( d + 1 ) l 代替；s h e a r e r i e 明不能用更小的常数代替 “e ”( 见 9 ” 有关该最简单形式的一些应用可参见隙 1 0 ， 1 1 ， 1 2 ，【1 3 1 4 【1 5 】，【1 6 ， 1 7 】，【1 8 】 定理2 2 ”1 如果h 足一个超图，使得每条超边的大小至少是且每条超边至多与2 n 3 条 其它的超边相交，则日是2 可染色的 证明：选择一个均匀的随机的顶点2 一染色对每条超边e 、定义a 。表示e 是单色边 的事件，定义帆表示与e 相交的边的集合由条件有l e l 2 k - 3 我们将应用局部引理 到= = a 。：e e ( h ) ) 的集合( 注：每个事件4 。与事件 a ff 隹帆 的集合互相独立) p r ( a 。) 2 - ( k 1 ) 且4 p d o a j e d i i = 1 对于图g 的女正常边染色，如果g 中无二色的囤，则这种染色称为扣无圈边染色”| 换 言之任取两种颜色，图g 中染这两种颜色的全体边所导出的子图是森用q ( g ) 表示图g 的 无圈边色数，即g 的所有无圈边染色中所用颜色数的最小值g 的围长9 ( g ) 表示g 中最小 圈的长度以下我们将讨论图的围长与无圈边色数之间的关系 6 2 几种概率方法及应用 定理2 5 ”“如果9 ( g ) 7 0 0 a l o g ，那么a 7 ( g ) + 2 ，其中是图g 的最大度 且9 ( g ) 是g 的围长 证明本定理的证明采用概率的方法我们只需证明当9 ( g ) 7 0 0 a l o g 时，g 存 在( + 2 ) 一无圈边染色为了叙述简便，令d 表示图g 的最大度 首先用d + 1 种颜色对g 的边进行正常染色( 根据v i z i n g 定理，这一点可以做到) ，我们用 映射c ：e 一 1 ，2 ，d + 1 ) 表示( d + 1 ) 一正常边染色 其次，用一利t 新的颜色d + 2 v a 概率c 南( c 是个常数) 埘g 的每条边进行随机而且独 立的重新染色，必须保证以下两点成立： ( 1 ) g 的染色仍然是正常的即相邻的边被染成不同的颜色，特别地，没有一对相邻的边 被同时染成第d + 2 种颜色 ( 2 ) 染色是无圈的，即g 的每个圈的边至少用到了三种颜色 下面我们将应用l o v s s z 的一般局部引理来完成本定理的证明为此须作以下几步工 作： 第一步：令a 表示如下事件：存在d + 2 种颜色的无圈边染色需找出a 的对立事件根据 上面的( 1 ) ( 2 ) 可得以下三种类型的对立事件： i ：对丁每对相邻的边b = e 。，e ：) 令冶表示e 1 和e 。同时被染成第d + 2 种颜色的事件 i i 对于每一个用第一种正常染色r 染成的二色圈c ，用，玷表示e 中没有边被重新染成 第d + 2 种颜色的事件 i i i ：对于每个半单色圈d ，用e d 表示d 巾一半的边被重新染成第d + 2 种颜色，使d 成 为二色圈的事件，( 半单色圈：有偶数条边的简单圈d ，如果口中一半的边( 每隔一条 边) 被c 染成同一种颜色) 很明显，如果i ，i i ，i i i 不成立，那么( 1 ) ( 2 ) 就成0 ：即说明g 存在d + 2 种颜色的无圈边染 色 第二步：计算每个对立事件发生的概率 引理2 6 m 1 1 对i 的每个事件e 8 来讲，只陋h j = 是 2 对i i 的每个事件如来讲，c r 的长度为。， b 【岛】= ( 1 一刍严e - c c 2 d 3 对i i i 的每个事件点砀来讲，d i 勺v c 度为2 z ， 只 勖 曼2 ( 刍) 。 2 几种概率方法及应用 第三步：计算与每个对立事件所关联的事件数 引理2 7 口对于任意给定的边e 以下i 条成立： 1 少于2 d 条边与e 相邻 ，2 少于d 个二色圈包含e ， 3 至多2 d k - 1 个长为2 的半单色圈包含e 从引理27 可得对于包含条边的x 来讲，每个事件e x 至多与i 的2 x d 个事件关联至多 与i i 的z d 个事件关联至多与i i i 的2 x d - 1 个事件e d 关联，其中口的k = 为2 ，对所有的k 2 第四步构造常数轧( o 。，我们有。主若蔫d 2 当。：南，可取到。韵最小值z 成立_ 因为1 + 1 6 c 1 0 96 。，我们有z 感当c = 南，可取到。韵最小值z 警等哗 0 下面用归纳法旺明( 1 ) 即只需要证明以下两点： ( i ) 由条件可得p ，( a i ) 研兀( 1 一) 以一对i s l = 0 ，( 1 ) 成立 a j e d i ( i i ) 考虑任一特定的a ，s 假设对每个事件和每个i t s 更小的集合( 1 ) 成立1 我们将需 要以下假设的推论： ( 2 )如果s 和皿不交，则( 1 ) 成立 令s = s n d ；，岛= s s t ( 可知& nd 。= ) ，假设s 。非空应用( 2 ) 又b j 为有事 实只( x y ) = 掰，所以 只( a i b n c ) b ( a n b l 3 c )只( 以n b i e ) 只( c )p r ( | 4 n 口】c ) 利用这个事实，有 只( a “n a ，e s 丐) = p d a 。i 观察分子 只( bn c )只( b i c ) p r ( c ) p , ( a l c ) (n一，es。j)n(n-，es?j丐，=!j；：；：?；i群 只( a 。n ( h a ，s 。丐) ia a ，丐) b ( a 。ln 山岛巧) = 只( a 。) 最后一个等号是因为a ，与d ；中的事件相关，与皿外的事件互相独立，又_ 岛n 皿= 即a ，与岛中的事件山互相独立可得a 。与石也互相独立 为了记号的方便给s 1 中的事件标号b 1 ，b 2 ，b 。，则分母 p , ( n a ，e 最i 山j n 勺e 岛才一) = b ( ( 酉n 百i n - n 瓦) j n 4 ，e 5 2 丐) 尸r ( 两i n 山丐) 只( s 2 l b n ( h a 芦：丐) ) p , ( 一b t i b ln 1 0 砑卜 如 n 耵 n 2 几种概率方法及应用 利用( 2 ) 可知( + ) 兀( 1 一x j ) a j e s l 所以根据条件及假设，有 即一般局部引理得证 有 n ( 1 一) a j e d i i - i ( 1 4 j e d , 2 证明非对称局部引理 对每个i 令研= 2 p , ( a 。) ，只( a 。) ，置2 1 令a = 2 1 n 2 ，将利用事实：对3 1 3 。e 一8 ( 即1 一z 。) x i i - i ( 1 一z ，) q 兀e 一。2 ，= 2 p ，( a ；) e x p ( 一。2 只( a j ) ) a j e d i a j 6 d ， 1 6 d ， 2 p ( a f ) e x p ( 一鸶) = 2 p ，( a ，) e 一学= 2 p ，( a ；) xe i n 1 = 只( a 。) 所以就得到t p , ( a 。) 乱1 - i ( 1 一巧) 接下来就是利用一般局部引理 且，_ d 3 证明局部引理的最简单形式 由条件可知4 埘1 ，所以p 壶 ，目，叫 对每个a ，e ，b ( a ) p ，p ，( a j ) 咖女，满足非对称局部引理中的条件，即知l o v 如z 局部引理的最简单 一l ，i 形式嘉非对称局部引理的特殊情况 4 证明赋权的局部引理 对每个i 令孔= ( 2 j d ) “，0 p i t ；1 令口= 2 1 n 2 ，利用事实对z ( 1 一z ) e 一“， n 兀i ( 1 一。，) = ( 2 p ) “l - i ( 1 一( 2 p ) o ) ( 2 p ) “e x p ( 一q ( 2 p ) o ) 一，d i4 j 6 d ia ，e d ， 所以就得到了p r ( a 。) 以兀( 1 一z j ) 接下来就是利用一般局部引理 a ，6 d i 四。几种l o v f i s z 局部引理之间的关系及适用范围 l 0 v 缸z 局部引理主要用来证明具有某些特定属性的目标的存在性问题在实际遇到的 问题中经常会出现事件之间相互依赖的情况，这时候，如果依赖的数量被充分地限制，我 们仍可断定成功的概率为正 ；f p 2 =。卜三 e 印 f l 印 | | 学 一 p 0 耳 薹、 一 渤矿 一 l l 2 几种概率方法及应用 1l o v a s z 局部引理的最简单形式是非对称的局部引理的特殊形式，它的缺点就是需 要全局约束p 和d 这些约束将使局部引理的应用变得困难例如：坏事件的概率广泛地变 化 2 非对称的局部引理适用于：它允许集合n 的一些差异一它们可以包含一些高概率 事件藏是一些低概率事件，只要概率的和至多是1 4 即可 3 赋权的局部引理适用于：当每一个事件a 。都有“大小”，对应于，使得只( 月，) 指数 的小，与a 相关的事件的数量是线性的：当任意一种类型的事件与另一事件交互影响的数 量没有上界时，选择赋杖的局部引理 4 用p b 代替赋权的局部引理中的条件( b ) 产生出非对称的局部引理的推 1 e d l 论用p ，每，产生出一个4 i 真的陈述 a ，e d i 5 ，一般局部引理是最有用但也是最难处理的，一般局部引理隐含所有其它观点( 非对 称的局部引理与赋权的局部引理1 1 2 3邻点可区别的边染色 下面所考虑的图g 都是无向的简单图用y ( g ) ，e ( g ) 分别表示g 的点，边的集合， ( g ) 表示g 的最大度( 见| 3 1 ) a c b u r r i s 和r h s c h e l pf i - 先研究了点可区别的正常边染色f 见f 2 1 1 ) p n b a l i s t e r ，b b o l l o b a s 和r h s c h e l p 得到了关于a ( a ) = 2 的图g 的点可区别的正常边 染色的一些结果( 见 2 2 0 张忠辅等人在文f 5 】中提出了图的邻强边染色的概念，得到了若 干结果，并提出了有关猜想：对i v ( a ) i 3 且g 不为5 圈的连通图g ，x ：。( g ) ( g ) + 2 明显地，) ( ：，( g ) f ( g ) ( g ) 此外如果g 有两个相邻的最大度顶点则) ( ：。( g ) a ( a ) + 1 对于圈g ；完全图完全二部图瞄。树，单循环图，最大外可平面图， a ( c ) 3 的外可平面图和h a l i n 图的邻强边色数在f 5 】j 【2 3 “2 4 【2 5 ，f 2 6 】中进行了研究，得 到了若干结果 对于标准的图论记号可参看f 2 7 】 2 8 1 ，f 2 9 j 以下我们将用第矩量_ 方法和l o v n s z 局部引理来讨论图的邻点可区别的边染色问题， 叉 一利用第一矩量原理和m a r k o v 不等式 nn 引理3 11 一( 只( 石) ) b ( na 。) z = 1l = 1 证明：由概率的次可加性可知 异( 酉u 忑ut u 石) 只( 一a j 十耳( 瓦) + + p r ( 瓦) ( ) 只( 石u 再i u u 万：) = p r ( 刁了万了e 了丁_ _ 亓了) = 1 一只( a lna 2n n a 。) ( + ) 式即为： t l 1 一、只( n a 。) p r ( 石) ， 1 = 1 = 1 ( b ( 忑) ) s 只( n a t ) t = 1t = 1 定理3 2 对任一育，。个顶点的最大度为d ( d 2 ) 的图g ，x ：。( g ) n d ( d 一1 ) 证明：令f2 n d ( d 一1 ) ，从颜色集合 l ，2 ，f ) 中给图g 的每条边随机地均匀地分配 一种颜色，使每条边的颜色的选择与所有其它边的颜色的选择独立，为了保证邻点可区 1 3 3 邻点可区别的边染色 别的边染色，必须使以f 两点成立( 1 ) 正常边染色，( 2 ) 邻点可防别为此，定义如下指标变 量： ( ) 对每两条相邻的边e 凰令x 。= i 薯翥? 1 9 颜色一样；，并令x = 。，蟊研鼍。 注意到x 即是不满足【e 常边染色的相邻边对的数量 ( i i ) 对每条边伽，令k ，= 5 l ：薯盖? 和诚毒足d = d ；，并令y = 。量g ，k 。注 意到y 即是不满足邻点可区别的边的数量 现只要证b ( x = o 且y = 0 ) 0 又根据引理可得只( x = 0 且y = 0 ) 1 一 只( x o ) + p r ( y o ) 0 ( 令a l = x = o ) ，a 2 = y = o ) ，则石= x o ) ，瓦= y o ) ) ，即只须证只( x 0 ) + 只( y 0 ) 0 ) e ( x ) ，所以只须证e ( x ) + z ( y ) l 即可 首先计算- e ( x ) e ( 也9 ) = 只( 也，9 ) = 丰，通过期望的线性性， 即，2 蔷取j 如( 辩= 掣= 粼1 1 e ( x ) 可1 其次计算e ( y ) 一e ( k ”) 2 西可万i i ：而巧 口 研( 当f 2 4 2 时成立) 通过期 望的线性性 刚) = e ( 讫 字南= 盯# = 志j ， u v e ( g ) 、 1 f ( y ) e ( x ) + e ( y ) l ， 至此完成了定理3 2 的证明 二。利用l o v f i s z 局部引理的最简单形式 定理3 3 对仟一最大度为d 的图g ，x ：，( g ) 4 ( 6 d 2 8 d + 4 ) 证明：令f = 4 ( 6 d 2 8 d + 4 ) ，令，：e 一 1 ，2 ，f ) 表示g 的边的随机染色，并对任 意e e ( g ) ，( e ) 是从 1 ，2 ，j ) 中随机地均匀地选择的为了保证邻点可区别的边染 色需满足两个条件： ( a ) 正常边染色一没有两条相邻的边染成同一种颜色 ( b ) 邻点可区别没有一对相邻的顶点关联同样的颜色集合 为此，定义如下坏事件： ( i ) 对每一对相邻的边a = e - ，e 2 ) ，令b 表示e 和e 2 整染成同种颜色的事件 ( i i ) 对每一条边e = “w 令e 口。表示c ( u ) = c ( v ) n 事件( 注：对任一边e = u u ，由 边 u z e ( g ) ：。v ( g ) ) u 。萝i f ：e ( g ) ：y ( g ) ) 导出的予图被称作关于e 的双星 4 53 邻点可区别的边染色 圈，用b 。表示) 注意到如果( i ) 和( i i ) 都不发生，则，是g 的邻点可区别的边染色 ( 1 】计算坏事件发生的概率 只( 玩) = _ ，只( e 肌) = u f 砑钿 啊 可( 当2 2 d 一2 ) 根据l o v 矗s z 局部 引理的最简单形式中的要求，取p = _ 1 ( 2 ) 计算相关事件数 构造相关图日，日中的结点就是两种类型的所有事件其中两个结 点瞰和印( x 和y 要么表示一对关联的边，要么表示一条边的双星图) 相邻当且仅 当x 和y 含条公共边，因为每个事件e x 的存在仅依赖于x 的边 由相关图的构造可得，每一个事件e a 弓至多4 d 一5 个e _ 相关( 因为和一条边e 相交的 边数至多是2 d 一2 ( 除去e 本身) ，事件毋中包含两条边e ，和e 2 ，所以分别和e l ，e 2 相交的 边数至多是2 ( 2 d 一2 ) = 4 d 一4 ，又因为和e - 相交的边中有e 2 和e 2 相交的边中有e 1 ，所 以丑= 一l ，e 2 被计算了两遍，应减1 ) ，与至多3 d 一2 个f b 。相关( 设下图 。! ! 。工 u 1 u u 2 ( 1 ) 首先考虑e 1 e 2 的公共端点札，和让相邻的顶点至多有d 个这其中包含e 。的另1 端点u 1 和e z 的另一端点n 2 ；( 2 ) 其次考虑“，平| l u 。相邻的顶点至多是d 一1 个( f u u ) 已在( 1 ) 中计算 过一次) ；( 3 ) 最后考虑“2 ，和u 2 相邻的顶点至多是d 1 个( “2 ，u ) 己在( 1 ) 中计算过一次) ，所 以d + ( d 一1 ) + ( d 1 ) = 3 d 一2 ) 每一个事件魄与至多( 2 d 一1 ) ( 2 d 一2 ) 个玩相关( 因为和一条边e 相交的边数至多 是2 d 一2 ( 除去e 本身) ，事件e 毋中至多包含2 d l 条边) ，与至多( 2 d 一2 ) d + l = 2 d 2 2 d + 1 个e 8 。相关( 原因如前1 为了应用l o v 出s z 局部引理的最简单形式，令相关事件数= ( 2 d 一1 ) ( 2 d 一2 ) + ( 2 d 2 2 d + 1 ) = 6 d 2 8 d + 3 1 所以4x ( 6 肛蚺3 ) = 箍黜 p g 存 在4 ( 6 d 2 8 d + 4 ) 一邻点可区别的边染色 三利用非对称的局部引理 定理3 4 对任一最大度为d 的图g ，：。( g ) 4 ( 6 d 2 8 d + 3 ) 证明：令f = 4 ( 6 d 2 8 d + 3 ) ，f 1 a 和冶。的定义及每个事件的相关事件数如上p r ( e a ) = p r ( e b 。) = 可可万 碡士研( 当f 2 d 一2 ) 为了使用非对称的局部引理，需有 以下成立： 1 5 3 邻点可区别的边染色 4 d 一53 d 一27 d 一7 t + t 2 t 2 ( 2 ) p d e a o ) 2 丽西1 可习 砖 ( f 矗) 且 4 ( 6 d u - 8 d + 3 ) i ( 2 d 一1 ) ( 2 d 一2 ) + ( 2 d 2 2 d + 1 ) 可南 0 ) + b ( y 0 ) + 只( z 0 ) + 只( u o ) 1 0 ，即只 须证只( x 0 ) + p r ( y 0 ) + 只( z 0 ) 4 - 片( 矿 0 ) 0 ) e ( x ) ，所以只须证f ( 叉) + e ( y ) + e ( z ) + e ( u ) 1 即司 计算e ( x ) ，e ( 噩，) = 只( 五。) = ，通过期望的线性性， 即) 一二。( 孙= 掣= 端1 1 e ( x ) 计算e ( y ) 7 ，f ( k 。) = p r ( k 。) = ，通过期望的线性性， 刚) = e ( ) s 警- = 丽n d i 1 e ( y ) 4 1 计算e ( z ) ，e ( 磊( 。) ) = 斥( 乙( 。) ) = 呈每 f 2 l = 通过期望的线性性， 即= 、e ( z 川) 萼；= 赢= 志1 u v 6 e ( g 、 、 e ( z ) ； 计算e ( 矿) _ e ( g 一) = b ( 巩，”) = 珂可渤 南( 当f 2 d 时成立) - 通过期望的 e ( u ) e ( ) 了d r t f e ( g ) e ( 4 1 综上，e ( x ) + e ( y ) + e ( z ) + e ( u ) 1 ，得证 11 面而 一4 二利用l o v i s z 局部引理的最简单形式 定理4 2 对任一最大度为d 的图g ，x m ( g ) 8 ( 6 d 2 2 d ) + 1 证明：令f = 8 ( 6 d 2 2 d ) + 1 ，令，：v u e 一 l ：2 ，z 表示g 的随机全染色