(运筹学与控制论专业论文)图的均匀染色.pdf_第1页
(运筹学与控制论专业论文)图的均匀染色.pdf_第2页
(运筹学与控制论专业论文)图的均匀染色.pdf_第3页
(运筹学与控制论专业论文)图的均匀染色.pdf_第4页
(运筹学与控制论专业论文)图的均匀染色.pdf_第5页
已阅读5页,还剩47页未读, 继续免费阅读

(运筹学与控制论专业论文)图的均匀染色.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

摘要 图的均匀染色 摘要 图染色问题是图论研究中的重要问题之一和热点之一,有重大 的理论价值和应用背景图的均匀染色理论是图的染色理论的一种推 广,但到目前为止,关于这一理论的很多问题还有待解决本论文主要 讨论图的均匀染色问题 论文由四章组成第一章是对本论文涉及到的问题的背景,定义 及进展等各方面的综述 在第二章中,我们主要研究了图的( 点) 均匀染色,目的是证明著 名的均匀染色猜想对于一些图是成立的我们利用权转移的方法找出 了不含特定长度圈的平面图所必须含有的一系列特殊结构从而证明 了对于不含3 一圈,4 一圈和5 一圈的平面图和不含4 圈( 或5 一圈) t n 6 一圈的平 面图g ( a ( g ) 26 ) ,均匀染色猜想是成立的 在第三章中我们主要研究图的均匀列表染色k o s t o c h k a ,p e l s m a j e r 和w e s t 研究了图的均匀列表染色,他们猜想:对于k ( g ) ,每 个图g 都是均匀k 一可选择的而我们则把第二章中平面图的结果平行 地推到图的均匀列表染色中来从而得出不含3 一圈,4 一圈和5 圈的平面 图和不含4 一圈( 或5 一圈) 和6 一圈的平面图g ( a ( g ) 6 ) 均有一个( g ) 一均 匀列表染色 在第四章中主要计算了一些特殊图的均匀全色数,对于一些平 面图计算出了它的( 点边面) 均匀全色数 关键词:均匀染色,均匀全染色,平面图,圈 a b s t r a c t e q u i t a b l ec o l o r l n g so fg r a p h s t h e c o l o r i n go fg r a p h s ,o n eo f t h em o s ti n t e r e s t i n ga n d r a p i d l yg r o w - i n ga r e a so fr e s e a r c h e si ng r a p ht h e o r y , h a sg r e a tt h e o r e t i c a lv a l u ea n da p - p l i e db a c k g r o u n d e q u i t a b l ec o l o r i n go fg r a p h se x t e n d st h et h e o r ya b o u t c o l o r i n gg r a p h s ag r e a tn u m b e ro fp r o b l e m sa b o u tt h ee q u i t a b l ec o l o r i n g t h e o r y a r eu n s o l v e ds of a r t h i sd i s s e r t a t i o nm a i n l yd i s c u s s e st h ee q u i t a b l e c o l o r i n go fg r a p h s t h i st h e s i sc o n s i s t so ff o u rc h a p t e r s c h a p t e r1i s a ni n t r o d u c t i o nt o t h eb a c k g r o u n do ft h er e s e a r c hp r e s e n t e di nt h et h e s i s c h a p t e r2d e a l sw i t ht h ee q u i t a b l ec o l o r i n go f g r a p h s t h ep u r p o s ei s t oc o n f i r mt h ee q u i t a b l ea - c o l o r i n gc o n j e c t u r ef o rs o m e g r a p h s w em a i n l ys t u d yt h ep l a n eg r a p h s w ev e r i f yt h i sc o n j e c t u r ef o r ap l a n eg r a p hw i t h o u ti - c y c l e s ,3 i 5 ,o r ap l a n eg r a p hw i t h o u t4 - c y c l e s ( o r5 - c y c l e s ) a n d6 - c y c l e s c h a p t e r3i s ,d e v o t e d ,t oe q u i t a b l el i s tc o l o r i n go fg r a p h s k o s t o c h k a p e l s m a j e ra n dw e s tc o n j e c t u r e dt h a tf o rk ( g ) ,e v e r yg r a p hg i se q u i t a b l yk - c h o o s a b l e w ea p p l yt h er e s u l t si nc h a p t e r 2t ot h ee q u i t a b l el i s t c o l o r i n go fg r a p h sa n dp r o v et h a tag r a p hgi se q u i t a b l y ( g ) 一c h o o s a b l e i fgi sa p l a n eg r a p hw i t h o u ti - c y c l e s ,3 i 5 ,o rap l a n eg r a p hw i t h o u t 4 - c y c l e s ( o r5 - c y c l e s ) a n d6 - c y c l e s i nc h a p t e r4 ,w ec a l c u l a t et h ee q u i t a b l et o t a lc h r o m a t i cn u m b e ro f s o m es p e c i f i cg r a p h s f o rs o m ep l a n eg r a p h ,w ea l s oc a l c u l a t et h ev e r t e x e d g e - f a c ee q u i t a b l et o t a lc h r o m a t i cn u m b e r k e yw o r d s :e q u i t a b l ec o l o r i n g ,e q u i t a b l et o t a lc o l o r i n g ,p l a n eg r a p h , c y c l e i i 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外,不包含其他人或其他机 构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在 论文中作了明确的声明并表示了谢意。 研究生签名:杏苞交 日期:伽6 ,p 、2 刀 学位论文使用授权声明 本人完全了解浙江师范大学有关保留、使用学位论文的规定,即:学校有权 保留送交论文的复印件和电子文档,允许论文被查阅和借阅,可以采用影印、缩 印或扫描等手段保存、汇编学位论文。同意浙江师范大学可以用不同方式在不同 媒体上发表、传播论文的全部或部分内容。保密的学位论文在解密后遵守此协议。 研究生签名:杏谤二 导师签名: 日期:上胂6 、1 0 、2 0 、绪论 一、绪论 本学位论文主要考虑图的均匀染色的各类问题在本章里,我们先给出与本 文有关的一些问题的背景、定义和进展在给出综述之前,我们首先将引进一些 符号和概念,这些符号和概念将贯穿全文对本章没给出的符号和概念,我们会在 后面适当的地方给出对于那些文中未给出的符号和概念,可以在中找到 ( 一) 、基本概念与符号 对于图g ,用y ( g ) ,e ( g ) ,f ( g ) ,( g ) ,6 ( g ) ;f l :l d a ( v ) 分别表示g 的顶点集,边 集,面集,最大度,最小度和顶点口在图g 中的度数( 在不引起混淆的情况下简记 为ve ,f ,仝,6 ,d ( ) ) n g ( v ) 表示顶点u 在g 中所有邻点的集合n v 】= n ( v ) t j a 用iz 表示不大于z 的最大整数用陋 表示不小于。的最小整数用k ;表示凡阶完 全图,致。表示完全二部图 下面我们介绍一些本文需要用到的关于图的一些基本概念,我们这里考虑的 都是无向、简单图 定义1 1 1 对图g ( ke ) ,m ( g ) 称为g 的m y c i e l s k i ,其中 y ( m ( g ) ) = y ( g ) u v 7u 叫) , e ( m ( g ) ) = e ( g ) u u 7 l “1 旷( g ) ,u 7 v 7 且乱u e ( g ) ) u t u 7 i u v ) , 其中伽管y ( g ) ,v 7 = 7 i 口y ( g ) ) 定义1 1 2 没有割点的连通图叫做块 定义i i 3 如果图g 的任意子图日中都存在一个顶点u ,使得d 日 ) d ,则 称图g 为d 退化图 如果一个陶g 能够画到平面上使得它的边互相不交( 交点仅在边的端点处) , 我们就称这个图是可以嵌入到平面的,或称其为平面图显然,对简单平面图而 言,每个外平面是2 退化的,每个平面图是5 退化的我们称面,与它的周界上的 顶点和边是关联的,面厂的度数d ( ,) 是指与它关联的边的条数其中割边被计算两 次关于平面图的理论是欧拉在他对多面体的探讨中发现的欧拉公式是数学的 经典结果之一 定理1 1 4 ( 欧拉公式) 对任何一个有l y l 个顶点,f e l 条边和i f j 个面的连通平 一1 一 绪论 面图g 有i y i i ej + l f l = 2 ( - - ) 、关于均匀染色的简介 图的均匀染色是图的一般染色的推广图的均匀染色具有很强的应用背景, 例如在安排工作时,在同一时刻进行的工作数会被加工者的数量所限制这种对 色类大小的限制就产生了图的有界染色图g 的一个正常顶点染色,如果满足 在厂f ,每个色类中的顶点数至多为m ,则称,为图g 的一个m 界染色如果要求进 步加强,每两个色类中的顶点数至多相差l ,这样就产生了图的均匀染色显然 图的一个均匀染色也是图的一个f 世譬1 界染色 下面我们给出关于均匀染色的一些定义、相关猜想及进展 。定义1 2 1 图g = ( y ( g ) ,e ( g ) ) ,如果y ( g ) 能被剖分成k 个独立集,k , ,且对所有的i ,歹( i i ,j 七) i 有| j k i i k | | 1 ( i ,j = 1 ,2 ,七) ,则称g 有 一个k 一均匀染色图g 的均匀色数托( g ) = m i n k t g 有一个k 均匀染色 图的均匀染色与图的正常染色的不同之处在于:图g 是k 一均匀可染的,但不 一定是七+ 1 - 均匀可染的例如 ( g ) ,每个图g 都有个均匀七列表染色 给定一个图g ,我们不断的去掉图中的悬挂点直到不再有悬挂点,这样得 到的子图g 7 被称为原图g 的核一个口图足指一个块它有两个度为3 的不相邻的 点,而所有其它点的度均为2 于是,我们可以看出一个p 图由两个度为3 的点和连 接它们的三条不相交路组成,我们不妨用o k , 8 , t 表示三条不交的路,其长度分别 为k ,8 ,珀g p 图 定理1 2 1 8 2 0 】一个连通图g 有一个均匀2 列表染色当且仅当g 是个二部 图且满足下面两个条件 ( i ) g 的核为蜀或一个偶图或一个0 2 ,2 2 r 一图( r 1 ) ( i i ) g 的2 部分点集x 和y 满足i i xj 一 y | | 1 定理1 2 1 9 1 2 0 】设k ( g ) ,则任意a ( a ) 3 的图g 有一个均匀k 一列表染 一4 一 一、绪论 色 定理1 2 2 0 【2 1 】 设七垒【剑譬堡l 坐- f2 ,则任意( g ) 3 的图g 有一个均 匀k 列表染色 定理1 2 2 1 口2 】 设七之m a x a ( g ) ,l y ( g ) i 2 ) ,如果g 中不含甄,k ( 七为奇数) 及耳0 1 ,则g 有一个均匀七列表染色 本文主要证明了对于不含3 一圈,4 - 圈和5 - 圈的平面图和不含4 圈( 或5 圈) 和6 一 圈的平面图g ( ( g ) 6 ) ,有x 。( g ) ( g ) 同时计算了两类m y c i e l s k i 的均匀全 色数及圈、轮图和扇形的( 点、边、面) 均匀全色数 一5 一 二、图的( 点) 均匀染色 二、图的( 点) 均匀染色 在本章,我们t 要考虑不含短圈的平面图的均匀染色 对于图g 的顶点v ,如果d ( v ) = 七( 或d ( v ) 七) ,则称顶点v 为k 点( 或七+ - 点) 类似地可定义k 一面和k + - 面用1 9 , 3 ( 口) 表示相邻于顶点v 的3 点的个数类似地可定 义竹2 ( ) m 3 ( ) 表示与顶点 关联的3 一面的个数m 3 ( ,) 表示与面,相邻的3 面的公 共边的总数类似地可定义m 4 ( f ) 我们用( d l ,d 2 ,d 3 ) 表示一个3 面,且与其关联 的3 个顶点的度分别为d l ,d 2 和d 3 如果u 1 ,u 2 ,是依顺时针方向为面,的所有 边界顶点,则简记f = 阻1 2 】g 的子图u 称为一个丛,如果u 由非空极d , 3 一面 组成,且没有其它3 面相邻于u 中的3 面用t ( u ) 表示u 中的3 面数,如果t ( u ) = k , 则“,称为k 一丛用m ( u ) 表示与顶点口关联的2 个相邻3 面的个数用m g ( u ) 表示与 顶点 关联且不再与3 面( 与顶点t ,关联的3 。面) 相邻的3 面的个数g 。为g 的一个 子图,它由2 个相邻3 一i 面 u y l 纠和阻抛蜘j 构成,且d ( v 1 ) 一d ( y 3 ) = 3 ( 一) 、2 一退化图的均匀染色 引理2 1 1 令s = v l ,吨, ) 为v ( c ) 的一个k 顶点子集,满足i n g ( v ) 一 s isk i ( 1 i 七) ,若g s 有一个k 均匀染色,则g 有一个k 均匀染色 证明:令g o = g s ,g = g ( g 一1 ) u 仇( 1 i 七) ,易见g = g k 假 设,0 是g o 的一个k 一均匀染色,色集记为c = 1 ,2 ,j 屉) 因为j b ( u 1 ) - s i k - 1 , 则至少存在一种颜色口1 ,使得在如下口1 不与染颜色为口1 的顶点相邻,则用颜 色血1 染v 1 ,从而将g o 的一个正常染色矗延拓成g 1 的一个正常染色 又i n c 池) 一 s i k 一2 ,则至少存在一种颜色o l 2 c 一缸1 ) ,使得 下 2 不与染颜色为口2 的顶 点相邻,然后用颜色0 2 染v 2 ,从而将g 1 的一个正常染色 延拓到g 2 的一个正常染 色,2 如此下去,直到把s 中的每一个顶点均染上一种颜色,这样就得到了g 的一 个k 正常染色,显然,s 中的k 个顶点所染的颜色均不相同,从而,为g 的一个k 一均 匀染色 下面我们称2 退化图中度数不大于2 的顶点为较小点 引理2 1 2 2 2 】如果g 是一个2 退化图,则g 至少包含下列子图之一: ( a ) 一个孤立点 ( b ) 有两个相邻的较小点 一6 一 ( c ) 两个较小点z ,y 有。个公芡的邻点z ( d ) 路尸= x y z ( x ,y ,z y ( g ) ) ,其中。是较小点,d a ( y ) = 如( z ) = 3 ( e ) 迹t = x y z w ( x ,y ,z ,叫y ( g ) ) ,其中z 和 均为较小点,d g ( y ) = 3 ( f ) 迹t x y z w u ( x ,y ,。,叫,u y ( g ) ) ,其中z 和“均为较小点,d g ( 耖) = d g ( w ) = 3 定理2 1 3 若g 是一个2 一退化图,对于任意k m a x 5 ,a ( g ) ) ,g 有一个七一均 匀染色 证明:采用反证法,假设存在一些2 ,退化图g ,对于某一个k m a x 5 ,( g ) ) , g 不是k 一均匀可染的,贝从这些图中找顶点数最少的图,再从顶点数最少的这些 反例中找到边数最多的图,设g o 为这样的一个图因为如果g ,不是七一均匀可染 的,则g ,+ x y ( x ,y y ( g ,) ,x y 隹e ( g ,) ) 也不是k - 均匀可染的又因为k 5 , 则i v ( g o ) i 6 根据g o 的边数的极大性,在g o 中添加任意一条边e ,则g o + e 或者 含有一个顶点t ,使得d g 。“( 口) = k + 1 ,或者g o 十e 不再是2 - 退化图 设顶点 是g o 中的一个较小点,则在g o 一m 中存在一个点,使得d g 0 一m ( “) 2 ,贝j j d a 。( t 上) s4 因为d g 。“。( u ) 5 k ,d c 。+ 蛐( u ) 3 ,所以g o + u u 中不存在 顶点u 7 ,使得d g o + u v ( v ) = k + 1 则g o + u v 不是2 - 退化图,即岛+ u 中含有一个子 图日,使得6 ( 月) = 3 ,则u u e ( 日) l h s d a o ( ) = 2 ,且口的两个邻点的度数均至少 为3 ,则g o 不含有度为1 的顶点且没有两个度为2 的顶点相邻 根据引理2 1 2 ,g 0 至少包含c ) ( ,) 中的种结构记顶点z ,可,z ,w ,u 的标号 与引理2 1 2 中一致记没有标记过的。的另一个邻点为z l ,在情况( c ) 一( ,) 中, 令z = z ,x k 一1 = y ,2 = z ,x k 一2 一“,( 在情况( e ) 和( ,) 中,w z 时) 下 面找引理2 1 2 所要求的s ,现以情况( c ) 为例,其余情况同理在情况( c ) 中, 记s 7 = o k ,o 一1 ,z 2 ,z 1 ) ,因为g o 是2 - 退化图,则g o s 7 中有一个顶点z k 一2 ,满 足d g 。一s ,( x k 一2 ) s2 ,再记= z k ,z “。- 2 z 2 ,z 1 ) ,则g o 一中有一个顶 点z k 一3 ,满足d g 。一( x k 一3 ) 2 依此过程,直到找到顶点黝为止,此时记s = z 1 ,z 2 ,o k ) ,易证l g 。( 如) 一s is 七一i ( i i 七) 根据g o 的阶数的极小性 和k a ( o o ) 2a ( g o s ) ,g o s 有一个k 均匀染色,再根据引理2 1 1 ,g o 有一 个k 均匀染色,矛盾定理证毕 推论2 1 4 若g ( ( g ) 5 ) 是一个2 - 退化图,则x 。( g ) sa ( g ) ( 二) 、平面图的均匀染色 在平面图的染色方面,王维凡等在文献【2 3 】中研究了( g ) = 5 时刁i 含4 一圈或6 一,一 二、罔的( 点) 均匀染色 圈的平面图的边列表染色在( 2 4 】中研究了不含5 一圈的平面图的列表染色及边列表 染色类似关于不含短圈的平面图的各种染色的结果可参见文献【2 ”7 】从这些文 章中得到启发,从而考虑了不含短圈的平面图的均匀染色问题 引理2 2 1 1 2 4 每个不含5 圈的平面图是3 一退化的 引理2 2 2 不含3 圈,4 圈$ u 5 一圈的平面图g 含有下列情形之一: ( a 1 ) 存在三个顶点z ,x k 一1 ,一2 且d ( x a ) = d ( x k 1 ) = l ,d ( x k 一2 ) 2 ( a 2 ) 存在一条边k $ 一1 及顶点。k 一2 ,且d ( x k ) = d ( x k 一2 ) = 2 ,d ( x k 一1 ) 2 ( a 3 ) 存在两条边z 。女一1 和。z 一2 ,且d o k ) = 2 ,d ( x k 一1 ) = d ( x 一2 ) = 3 ( a 4 ) 存在m 一2 个顶点z 七,x k 一1 ,x k m + 3 及m 一2 条边z 七一m + 2 七,t k m + 2 。七一l , ,z k 一。+ 2 x k 一。+ 3 ,且d ( x k ) = d ( x k 1 ) = 一d ( x k 一。+ 3 ) = 2 ,d ( x l , 一。斗。) 一m ( 其 中m24 ) , 证明:采用反证法设g 是一个反例,则g 是一个没有3 一圈,4 圈,5 圈和情 形( a 1 ) ( a 4 ) 的平面图,不妨设g 连通 注意到e u l e r 公式i yj i e i + i f i = 2 可改写成 ( 2 d ) 一6 ) + ( d ( ,) 一6 ) r - - - 1 2 v e v 。| f 设t 表示权函数,使得对v v ,有w ( v ) = 2 d ( v ) 6 ,对,f ,有伽( ,) = d ( ,) 一6 于是g 的所有顶点和面的权和为- - 1 2 ,因为图g 没有3 圈,4 圈和5 圈,故 对每个f f ,有叫( ,) 0 我们将重新分配这些权,使其上式左边总和不变对 于o vl j f ,用w 。( o ) 表示转移后的新权 权转移规则定义如下:每个4 + 点送权2 给每个相邻的2 点 因为g 中不含情形1 ) ,所以g 中至多含有两个1 一点 情况1 :g 中若含有两个1 一点,由于g 不含情形( a 1 ) ,则g 中不再含有2 点,此时 ( z ) 2 ( 2 1 6 ) = 一8 一1 2 z v t 9 p 矛盾 情况2 :g 中至多含有4 个l 一点,则g 中至少含有网个2 一点,否则叫 ) 2 1 6 + 3 ( 2 2 6 ) = - - 1 0 - - 1 2 ,矛盾 设u v ,若d ( ) = 1 ,则 7 ( ) = ) = 2 1 6 = - - 4 一8 一 二、图的( 点) 均匀染色 若d ( v ) = 2 ,因为g 不含有情形( a 2 ) ,则没有两个2 点相邻且2 点不与1 一点相 邻,又因为g 不舍有情形( a 3 ) ,则2 一点不同时与两个3 一点相邻,所以2 点至少与一 个4 + 点相邻则w 7 ) 2 2 6 - 4 - 1 2 = 0 若d ( v ) = 3 ,则 ) 一w 0 ) ;2 3 6 = 0 若d ( v ) = m ( m 4 ) ,因为g 不含有情形( a 4 ) ,所以m 一点最多与m 一3 个2 一点相 邻,贝u 叫7 扣) 2 m 6 2 ( l 一3 ) = 0 因为对任意,f ,w 7 ( ,) = 叫( ,) 0 ,又g 中至多含有一个1 点,所 以伽7 ( 功- - 4 - - 1 2 ,矛盾引理证毕 定理2 2 3 如果平面图g 不含3 圈,4 一围和5 圈,则对于任意k m a x 4 ,( g ) ) , g 有一个k 均匀染色 证明:反证法假设g 是一个反例且顶点数最少因g 不含3 一圈,4 圈和5 一圈, 根据引理2 2 2 ,g 包含子图( a 1 ) 一( a 4 ) 中之一顶点的记号与引理2 2 2 中一致 在1 ) ,( a 2 ) ,( a 4 ) 中,记没有标记过的x k 的另一个邻点为z 1 ,在3 ) 中记茹一l 的两 个没有标记过的邻点中的一个为z 1 下面找引理2 1 1 所要求的根据引理2 2 1 , 用定理2 1 3 中同样的方法找到s = z 1 ,0 2 ,o ) ,不难验证,i n a ( x f ) 一s f k i ( 1 i 七) ,又根据阶数的极小性和k2a ( g s ) ,g s 必有一个k 一均匀染 色,根据引理2 1 1 ,g 有一个k 均匀染色,矛盾定理证毕 推论2 2 4 对任意不含3 - 圈,4 一圈利5 一圈的平面图,有( g ) ( g ) 证明:由定理2 2 3 及定理1 2 ,5 可直接得到。 引理2 2 ,5 2 8 】每个不含6 - 圈的平面图是3 退化的 推论2 2 6 如果g 是一个不含4 一圈( 或5 一圈) 和6 一圈的平面图,则j ( g ) 3 引理2 2 7 不含4 一圈和6 一圈的连通、卜面图g ( 1 y ( g ) l 5 ) 含有下列结构之一: h 1 - t 2 一q h a 一二、圈的( 点) 均匀染色 蕊耄 礤。 弋 胁:见说明 - o - 5 - 8 风 + :一= = = = 凰:见说明 钞。, 釜1 | 。众a - 1 0 ;见说明 :( - 1 3 :见兑明 令 一 i 月。1 b 二、图的( 点) 均匀染色 2 _ = = 二 皿9 h 2 0 。j ,么2 。 : = = , 日2 3 :见晚明 弋7 一 0 若d ( ,) 7 ,当,与3 一面相邻时,根据( r 4 ) ,有( ,) = 伽( ,) 一竺m a 皿( f ) m a ( f ) = 0 当,不与3 一面相邻时,有 ( ,) 一 ( ,) = 2 d ( f ) 一1 0 0 若d ( f ) = 3 ,因为g 不含4 - 圈和6 - 圈,所以与厂相邻的面均为7 + 一面 当f = 时, 7 ( ,) = ( ,) = 2 3 1 0 = 一4 当,为( 3 ,4 ,4 ) - 而时,由于g 不含日2 ,因此与,关联的4 一点不再与其它3 点相邻 又g 不舍风,则与,关联的4 一点只与一个3 一面关联于是根据性质( p 1 ) 矛f l ( p 2 ) ,有 坩( ,) 2 - - 4 + ;3 + 2 = ; 0 当,为( 3 ,4 + ,5 + ) 面时,根据( p 1 ) 一( p 4 ) ,有加7 ( ,) - 4 + 7 4 3 + g + 2 = 麓 0 当厂为( 4 + ,4 + ,4 + ) 面时,根据( p 1 ) 一( p 4 ) ,有w 7 ( ,) - 4 + 3 + 2 3 = 击 0 一1 3 一 二、图的( 点) 均匀染色 因此,根据权转移规则,有- 2 0 = 叫( 。) = w 7 ( 甸一7 ,矛盾 $ v u fz e v u f 情况2 :a ( g ) = 2 :因为g 不含风,所以g 中不含( 3 ,3 ,2 + ) 面所以下面所指 的3 一面均为非( 3 ,3 ,2 + ) 一面 情况2 1 :g 中的2 - 点至多2 个,当2 一点与3 面关联时,由于g 中不含凰o , 则g 中不含( 2 ,2 ,3 ) 一面若g 中含有1 个( 2 ,2 ,4 + ) 一面,则此( 2 ,2 ,4 + ) 一面及其关联 的2 一点的总权数为( - 4 ) + ( - - 4 ) 2 = - - 1 2 若g 中含有至多2 个( 2 ,3 + ,4 + ) 一面, ! i l l j ( 2 ,3 + ,4 + ) 一面及其关联的2 一点和3 一点的总权数不小于( - - 4 ) 2 - i - ( - 4 ) 2 + ( 一1 ) x2 = - - 1 8 当2 一点不与3 一面关联时,则与2 一点相邻的3 点的总数至多为4 因 此2 一点及与2 ,点相邻的3 一点的总权数不小于2 ( 3 2 1 0 ) - i - 4 ( 3 3 1 0 ) = 一1 2 下面权转移规则及相关讨论同情况l ( 不考虑与2 点相邻的3 点及与2 点关联的3 i l i i ) 则有- - 2 0 = ( z ) = 7 ( z ) 一1 8 ,矛盾 情况2 2 :g 中的2 一点至少3 个,因为g 不含历1 ,则2 点不与2 点相邻又因 为g 不含日1 2 ,因此与3 点相邻的2 点最多1 个 假设存在一个与3 一点相邻的2 - 点 1 ,因为g 不含f 矗2 及日1 3 ,则2 点不再与4 点 相邻又g 不含皿j ,2 - 点不同时与2 个3 - 点相邻,所以此时顶点”1 及与顶点u 1 相邻 的3 一点的总权数为( 一4 ) + ( 一1 ) = 一5 假设不存在与3 一点相邻的2 一点,因为g 不含日1 4 ,则与4 点相邻的2 点最多1 个, 设为”2 ,则 池) 一一4 下面只考虑与5 + - 点相邻的2 一点的权转移情况,而与3 点 或4 点相邻的2 点的权不变 , 定义权转移规则如下: ( r 1 ) ,限2 ) ,很3 ) 和( r 4 ) 同情况1 中的( r 1 ) , 2 ) ,( r 3 ) 和( r 4 ) ( r 5 ) 一个5 + 点送权2 给每个相邻2 点 ( r 6 ) 一个4 一点u 送权( 2 一 3 ( ) ) m 3 ( t ,) 给每个关联3 一面 ( r 7 ) 个5 + 一点 3 送权( 3 d ( v ) 一1 0 一w a ( v ) 一2 n = ( v ) ) m 3 ( ) 给每个关联3 一面 根据上面规则有下面性质: ( p 1 ) 和( p 2 ) 同情况1 中的( p 1 ) 年f l ( p 2 ) ( p 3 ) 设u 是一个5 一点,是关联予u 的一个3 一面,则叫( 口) = 5 若项点 不与2 点相邻,有情况1 中的性质( p 3 ) 若顶点u 与2 - 点相邻,因为g 不含4 - 圈,所以3 一面不与3 - 面相邻,因此m 3 ( ) 2 又g 不含王,所以n 2 ( 口) = 1 由于g 不舍凰6 ,因此顶点 不与( 2 ,5 ,5 + ) 面关联又 由于g 不含凰9 ,所以顶点口不与( 3 ,5 ,4 + ) 一面关联 一1 4 当m a ( v ) = 2 时,由于g 不含h 2 0 ,有n a ( v ) = 0 于是根据( r 5 ) 及( r 7 ) ,有t ( v f ) = ( 5 2 ) 2 = i 当m 3 ( ) = 1 l i j ,有n 3 ( ) s2 又由于g 不含日1 7 ,所以与顶点 相邻的3 一点不 再与3 一点相邻于是根据( r 3 ) ,( r 5 ) 及( r 7 ) ,有7 _ 一,) 5 2 一i 1 2 = i ( p 4 ) 设u 是一个6 + - 点,是关联于u 的一个3 一面 当顶点u 不与2 一点相邻时,有情况l 中的性质( p 4 ) 当顶点u 与2 - 点相邻时,由于g 不含皿5 ,因此礼2 ( t ,) = 1 ,又g 不含日9 ,所以g 中 不含( 2 ,3 ,2 + ) 面 若顶点v 与( 2 ,6 + ,4 + ) 一面关联,由于g 不含玩8 ,所以佗3 ( u ) = 0 于是根据( r 5 ) 及( r 7 ) ,有 r ( ,) = ( 3 d ( 口) - - 1 0 - - 2 ) ”t s ( ”) 曼垡;穿2 2 若顶点u 不与( 2 ,6 + ,4 + ) 一面关联,由于g 不含- 1 9 ,贝u 顶点 不再与( 3 ,6 + ,4 + ) - 面 关联又由于g 不含h 1 7 ,所以与顶点u 相邻的3 一点不再与3 一点相邻于是根据( r 3 ) , ( 支,5 ) 及( r ,7 ) ,有 嘶- - , f ) 垫生型等者盟业 2等+一2兰亟旨+一2一193ma(v 3 3 39 ) 。掣1 。+ 对口v ,若d ( ) = 2 ,n w ( v ) = 一4 对不与3 一点和4 一点相邻的2 一点,根据( r 5 ) , 有w 7 ( u ) = - - 4 + 2 2 = 0 若3 d ( v ) s4 ,对不与2 一点相邻的3 一点和4 - 点,同情况1 中的d ( v ) = 3 及d ) = 4 的情形,有w ( 口) 0 若d ( v ) 5 ,当顶点u 不与2 一点相邻时,同情况l 中d ( v ) 25 的情形,有w 7 ( u ) o 当顶点 与2 点相邻且同时与3 一面关联时,根据性质( p 3 ) ,( p 4 ) 及转移规 n ( r 7 ) ,可知7 ( ) = 0 当顶点 与2 一点相邻且不与3 一面关联时,由于g 不含玩5 , 则n 2 ( u ) = 1 又由于g 4 i 含日1 7 ,所以与顶点v 相邻的3 - 点不再与3 一点相邻于是根 1 5 二、图的( 点) 均匀染色 据( r 3 ) 及( r 5 ) ,有 叫7 ) 3 d ( 。) 一l o 一2 一百1 ( d ( ) 一1 ) = s d ( v ) 广- - 3 5 ; o 对,f ,若d ( f ) = 5 t b d ( f ) 7 ,同情况l 中的d ( f ) = 5 及d ( ,) 7 的情形, 有w 7 ( ,) 0 若d ( ,) = 3 ,当,为( 2 ,5 + ,5 + ) 面时,根据性质( p 1 ) ,( p 3 ) 和( p 4 ) ,有w 7 ( 力2 - 4 + i 4 3 + ;2 = ; 0 当,为( 3 ,4 ,4 ) 一面时,同情况1 中的,为( 3 ,4 ,4 ) 一面时的情形,有w 7 ( ,) 0 当厂为( 3 ,4 + ,5 + ) 一面时,根据性质( p 1 ) 一( p 4 ) ,有( ,) 一4 + i 4 3 + + 黑= 击 0 当f ;y g ( 4 + ,4 + ,4 + ) 一面时,根据性质( p 1 ) 一( p 4 ) ,有 t 0 7 ( ,) 一4 + ;3 + g 3 = 茜 0 因此,根据权转移规则,有- - 2 0 = w 7 ( z ) = w ( z ) - 5 ,矛盾 情况3 :6 ( g ) = l :由于g 不含飓1 ,则g 中至多有2 个1 一点又g 不含日2 2 ,所 以g 中不含( 3 ,3 ,2 + ) - 面 情况3 1 :g 中含有2 个1 点:由于g 不含日2 ,所以g 中不再含有2 点又由 于g 不含日2 3 ,则1 点不与3 一点相邻所以l 一点的总权数为( 一7 ) 2 = 一1 4 下面 完全同情况1 来定义权转移规则及证明有- - 2 0 = ( z ) =w 7 ( z ) # v u f善v u f 1 4 ,矛盾 情况3 2 :g 中有1 个1 点,无2 点时:此1 一点最多与一个3 点相邻,则1 点及其 相邻3 一点的总权数为( - 7 ) + ( 一1 ) = 一8 下面完全同情况1 来定义权转移规则及证 明( 刁i 考虑与1 点相邻的3 一点) ,有- - 2 0 = t ,0 ) = w ( z ) 一8 ,矛盾 情况3 3 :g 中有1 个1 一点,至少3 个2 一点:由于g 不含凰1 ,日2 3 ,日2 4 及日2 5 所 以2 点只与5 + - 点相邻又由于g 不含飓3 ,则1 点不与3 - 点相邻1 一点的总权数 为一7 下面完全同情况2 中的子情况2 2 来定义权转移规则及证明,有- 2 0 = ”( z ) = w 7 ( ) 一7 矛盾 情况3 4 :g 中有1 个1 点且g 中有2 一点,但至多2 个2 一点:由于g 不含日2 5 ,所 以2 点不与3 一点相邻,又由于g 不含王乇3 ,则1 一点不与3 一点相邻当2 点与1 个3 面关 联时,由于g 不含日2 6 ,则g 中有且仅有1 个2 一点,因此1 点,2 一点及其关

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论