（运筹学与控制论专业论文）关于图的几类边染色问题.pdf

山东大学硕士学位论文 关于图的几类边染色问题 辛永训 ( 山东大学数学与系统科学学院，济南2 5 0 1 0 0 ) 中文摘要 本文考虑的图均为有限无向图，允许有重边但不允许有环对于一个图g = g e ) ，我们用v ( a ) 和e ( a ) 分别表示它的顶点集和边集对任意的t ，y ( g ) ， 我们用d g ( ) 表示口在g 中的度数( g ) 和6 ( g ) 分另表示图g 的最大度和最 小度设 和，2 是定义在v ( a ) 上的两个非负整数值函数且对任意的”y ( g ) ， 有0 ( u ) ，2 ( 口) d ( 口) 若存在对图g 的边集合e ( g ) 的染色，使每种颜色 的边集合的生成子图日满足 f l ( v ) sd t f ( v ) ，2 ( u ) ，v v y ( g ) ， 则称这样的边染色为图g 的( ，2 ) 一边染色同种颜色的边集合称为图g 的一 个( ， ) 一因子，因此图g 的( ，丘) - 边染色也称为图g 的( ，2 ) 一因子分解 若对所有的顶点口v 都满足 ( u ) = 0 且，2 ( u ) = 1 ，则图g 的( ，2 ) 边 染色就是传统意义上的边染色能对图g 进行正常边染色所需的最少颜色数称 为图g 的边色数，记为x ( g ) v i z i n g 已经证明对于任意多重图g 都有 ( g ) ) ( 。( g ) ( g ) + p ( g ) 而就简单图而言，图的边色数x ( g ) 则介于( g ) 和( g ) 一1 之间这样，可以 根据图的边色数将简单图分为两类若x 。( g ) = ( g ) ，则称g 为第一类的；否 则，称g 为第二类的研究图的分类是图论的一个重要方向 若对所有的顶点u v 都满足 ( ) = 0 且，2 ( ”) = ，( ”) ，则图g 的( ，厶) 一 边染色就是图g 的，一边染色能对图g 进行，边染色所需的最少颜色数称为 图g 的，边色数，记为x ，( g ) 若再为图g 的每一对顶点u ，口定义一个正整数 函数g ( u ”) ，且要求连接钍，材的同种颜色的边数不得超过9 ( 钍，”) ，这样的，一边染 色称为图g 的厶边染色能对图g 进行矗一边染色所需的最小颜色数称为图 g 的，9 一色数，记为妃( g ) ，_ 边染色是一般边染色的推广，而矗- 边染色又是 ，一边染色的推广， 若对所有的顶点口，都满足1 1 ( v ) = 1 且，2 ( ) = d ( ) ，则图g 的( ，厶) - 边染 色就是传统意义上的边覆盖染色对图g 进行边覆盖染色所需的最大颜色的数 目就称为图g 的边覆盖色数，记为x ：( g ) g u p t a 已经证明对于任意多重图g 都 有 d ( g ) 一p ( g ) x ：( g ) 6 ( g ) 山东大学硬士学位论文 而就简单图而言。图的边覆盖色数x ：( g ) 或者等于a ( a ) 或者等于e ( a ) 一1 这 样我们就可以根据边覆盖色数将简单图划分为两类若疋( g ) = 6 ( g ) ，则称g 是 c i 类的；否则称g 为c i i 类的对于任意图讨论它的分类是困难的，但对于一 些特殊图讨论其分类则是可能的 若对所有的顶点竹都满足 ( ”) = ，( 材) 且，2 ( ) = d ( u ) ，则图g 的( ，1 ，2 ) - 边 染色就是图g 的，边覆盖染色对图g 进行，- 边覆盖染色所需的最大颜色数 称为图g 的，边覆盖色数，记为x ；。( g ) 图的，- 边覆盖染色是一般边覆盖染色 的推广对于无环多重图g ，若我们给出了图g 的一种产边覆盖染色，并且图g 的重边皆染不同的颜色，则我们称图g 的这种，边覆盖染色为超，- 边覆盖染 色而对图g 进行超，边覆盖染色所需的最大颜色数称为图g 的超，- 边覆盖 色数，记为x 么( g ) 图的超产边覆盖染色是图的，一边覆盖染色的推广而若我 们再给定一个定义在e ( g ) 上的正整数函数g ( v w ) ，v w e ( g ) ，令重边中染同种 颜色的边数至多是g ( v w ) 取代重边染不同颜色的约束，则我们又得到了一种图的 ，一边覆盖染色的推广，我们称之为图g 的旷超边覆盖染色对图g 进行酽超 边覆盖染色所需的最大颜色数我们称为图g 的g 超边覆盖色数，记为 ( ；。( g ) 图的染色理论是图论的一个重要分支图的染色的种类现在已有很多，例如 通常的边染色，点染色，及面染色，全染色，列表染色和星染色等等其中研究 最多的，结果也比较完善的就是图的边染色传统意义上图的边染色就是把图的 边集分解为一些互不相交的边独立集的并的方法我们定义了图的( ，2 ) 一边染 色，它是图的，边染色和，一边覆盖染色的推广本文讨论了多重图的，一边覆 盖染色的两种推广：超，一边覆盖染色和g 超边覆盖染色 全文共分三章第一章简单介绍一下图论的基本概念，边染色理论的历史和 发展状况及已有的一些相关结论这一章是后面其他章节的基础 第二章讨论图的超，边覆盖染色的存在性并给出x ；。( g ) 一个一般意义的下 界其主要结论如下定理所示 定理2 3 1 令g = g ( k e ) 为一个图，1 ( v ) 【( d ( 钉) 一芦( ) ) 川，口v 那么我们有 x ；。( g ) m i n , 【( d ( 智) 一p ( 口) ) ，( 甘) j 第三章则讨论图的g 一超边覆盖染色的一些情况，包括它存在条件及x ；。( g ) 一般意义的下界其主要结论为下面的定理 定理3 3 1 令g = g ( v e ) 为一个图，1 s ( v ) sl ( d ( 钉) 一芦( 钉) ) 州，口v 对于v w e ，1 g ( v w ) r a i n f ( , ) ，) 那么我们有 x 蠢( g ) r 理粤【( d ( u ) 一p ( v w ) i g ( v w ) ) l l ( v ) j 另外，本论文的第二章和第三章最后还分别提出了一些问题，以待进一步研 究 i i 山东大学硕士学位论文 关键词：图；多重图；边染色；f 一边覆盖染色；超，一边覆盖染色；g - 超 边覆盖染色 1 l l 山东大学硕士学位论文 o ne d g e - c o l o r i n gp r o b l e m so fg r a p h s x i ny o n g x u n ( s & o o lo fm a t h s y s s c i ，s h a n d o n gu n i v 。，j i n a n2 5 0 1 0 0 ) a b s t r a c t t h r o u g h o u tt h i sp a p e r ，ag r a p hg ( ke ) a l l o w sm u l t i p l ee d g e sb u tn ol o o p sa n d h a saf i n i t ev e r t e xs e tv ( c ) a n daf i n i t ea n dn o n e m p t ye d g es e te ( g ) d a ( t ，) i st h e d e g r e eo ft h ev e t e x 钉o fgf o ra l l v l e ta ( c ) a n d6 ( c ) d e n o t et h em a x i m u m d e g r e ea n dt h em i n i m u md e g r e eo fg ，r e s p e c t i v e l y g i v e nag r a p hg ，l e t a n d ，2 b et w oi n t e g e r - v a l u e df u n c t i o n sd e f i n e do nv ( a ) s u c ht h a t0 h ( v ) 矗0 ) 墨d ( 口) f o ra l l v i ft h e r ee x i s t sac o l o r i n go fe ( g ) i nw h i c he v e r ye d g es e tw i t ht h e s a m ec o l o ri sas p a n n i n gs u b g r a p hho fgs a t i s l y i n g f l ( v ) d h ( v ) 五扣) ，v v v ( c ) t h e nt h ee d g ec o l o r i n go fgi sc a l l e da n ( f l ，2 ) 一e d g ec o l o r i n go fg w ec a l lt h ee d g e s e tw i t ht h es a m ec o l o ra n ( ，2 ) 一f a c t o r s oa n ( f l ，2 ) 一e d g ec o l o r i n go fgw i t h c o l o r sd i v i d e st h ee d g es e te ( g ) i n t oe d g ed i s j o i n t ( ，南) 一f a c t o r s 目，r ，r ，i t i sa l s oc a l l e da n ( f 1 ，2 ) 一f a c t o r i z a t i o n i ff l ( v ) = 0a n d ( u ) = 1f o re a c hv e r t e xvo fg ，t h e na n ( ，2 ) 一e d g ec o l o r i n g o fgi sa no r d i n a r y ( p r o p e r ) e d g ec o l o r i n g t h em i n i m u mn u m b e ro fc o l o r sn e e d e d t op r o p e r l ye d g ec o l o r i n ggi sc a l l e dt h ec h r o m a t i ci n d e xo fg ，a n di sd e n o t e db y x ( g ) v i z i n gp r o v e dt h a tf o ra n ym u l t i g r a p hg ， a ( c ) x ( g ) a ( g ) + 肛( g ) h o l d s f o rs i m p l eg r a p hg ，t h ec h r o m a t i ci n d e xx ( g ) i se i t h e r ( g ) o ra ( c ) 一1 ， as i m p l eg r a p hgi ss a i dt ob eo fc l a s so n ei fx 。( g ) = ( g ) ，a n do fc l a s st w o i fx ( g ) = a ( c ) + 1 t h er e s e a r c ho nt h ec l a s s i f i c a t i o no fs i m p l eg r a p h si so n e i m p o r t a n tb r a n c ho fg r a p ht h e o r y i ff l ( v ) = 0a n d ，2 ( 口) = f ( v ) f o ra l lv e r t e x 口v ，a n ( ，2 ) 一e d g ec o l o r i n go f gi sa n e d g ec o l o r i n g t h em i n i m u mn u m b e ro fc o l o r sn e e d e dt o 一e d g ec o l o r i n g gi sc a l l e dt h ef c h r o m a t i ci n d e xo fg ，a n di sd e n o t e db y r ( g ) g i v e nap o s i t i v e i n t e g e r - v a l u e df u n c t i o n9 ( u ，口) f o ra _ p a i rt 上a n d o fd i s t i n c tv e r t i c e s ，i ft h e r ee x i t s l v 山东大学硕士学位论文 a l l1 一e d g ec o l o r i n gcs u c ht h a tt h en u m b e ro fe d g e so fgw i t ht h es a i n ec o l o ra n d j o i n i n gua n d i sn o tg r e a t e rt h a ng ( u ，u ) ，t h e ns u c ha n ，一e d g ec o l o r i n gi sc a l l e da n 1 r e d g ec o l o r i n go fg t h em i n i m u mn u m b e ro fc o l o r sn e e d e dt o1 旷e d g ec o l o r i n gg i sc a l l e dt h e 厶一c h r o m a t i ci n d e xo fc ，a n di sd e n o t e db y 玩( g ) t h ef - e d g ec o l o r i n g i sag e n e r a l i z a t i o no ft h eo r d i n a r ye d g ec o l o r i n g 。 i fk ( v ) = la n d 。如( u ) = d ( v ) f o ra l l v e r t e x 口v ，a n ( f l ，2 ) ，e d g ec o l o r i n g o fgi sa l lo r d i n a r ye d g ec o v e rc o l o r i n g t h em a x i m u mn u m b e ro fc o l o r sn e e d e dt o e d g ec o v e rc o l o r i n gg i sc a l l e dt h ee d g ec o v e rc h r o m a t i ci n d e xo fg ，a n di sd e n o t e d b yx ：( g ) g u p t ap r o v e dt h a ta n ym u l t i g r a p hgh a s 6 ( g ) 一p ( g ) x ：( g ) 6 ( g ) t h u st h ee d g ec o v e rc h r o m a t i ci n d e xx ：( g ) o fa n ys i m p l eg r a p hi se q u a lt oe i t h e r a ( a ) o rd ( g ) 一1 o nt h eb a s eo ft h ee d g ec o v e rc h r o m a t i ci n d e x ，w ed i v i d es i m p l e g r a p h si n t ot w oc l a s s e s ，as i m p l eg r a p hgi ss a i dt ob eo fc l a s sc ii fx o ( c ) = 6 ( g ) ， a n do fc l a s sc i ii fx ：( g ) = a ( c ) 一1 t od e t e r m i n et h ec l a s s i f i c a t i o no fa n ys i m p l e g r a p hi sd i f i i c u l t b u ti ti sp o s s i b l et od e t e r m i n et h ec l a s s i f i c a t i o no fs o m es p e c i a l g r a p h s i fk ( v ) = f ( v ) a n d ，2 ( 口) = d ( v ) f o ra l lv e r t e xv v ，t h e na n ( 1 1 ，2 ) e d g e c o l o r i n go fgi s a 2 1f e d g ec o v e r - c o l o r i n g ，t h em a x i m u mn u m b e ro fc o l o r sn e e d e d t of e d g ec o v e r - c o l o r i n ggi sc a l l e dt h ef e d g ec o v e rc h r o m a t i ci n d e xo fg a n di s d e n o t e db yx f c ( g ) 。o b v i o u s l y , t h ef - e d g ec o v e rc o l o r i n gi sa g e n e r a l i z a t i o no ft h e e d g ec o v e rc o l o r i n g l e tgb eam u l t i g r a p hw i t h o u tl o o p s ，w ec a l lct h es u p e rf e d g e c o v e rc o l o r i n gi fci sa nf - e d g ec o v e rc o l o r i n go fga n dm u l t i p l ee d g e sr e c i v ed i s t i n c t c o l o r s t h em a x i m u mn u m b e ro fc o l o r sn e e d e dt ot h es u p e rf - e d g ec o v e rc o l o r i n g gi sc a l l e dt h es u p e r ，一e d g ec o v e rc o l o r i n gc h r o m a t i ci n d e xo fg ，a n di sd e n o t e d b yx 盖( g ) l e tg ( v w ) b ea ni n t e g e r - v a l u e df u n c t i o no ne ( g ) ，v w e ( g ) i ft h e n u m b e ro ft h ee d g e sw i t ht h es a m ec o l o ri nm u l t i p l ee d g e si sa tm o s tg ( v w ) i n s t e a d o fm u l t i p l ee d g e sr e c i v i n gd i s t i n c tc o l o r s ，t h e nw eh a v eg o tan e w e d g ec o l o r i n gc a l l e d g s u p e re d g ec o v e rc o l o r i n go fg t h em a x i m u mn u m b e ro fc o l o r sn e e d e dt ot h e g - s u p e re d g ec o v e rc o l o r i n gg i sc a l l e dt h eg - s u p e re d g ec o v e rc o l o r i n gc h r o m a t i c i n d e xo fg ，a n di sd e n o t e db yx ；。( g ) t h ec o l o r i n gt h e o r yo fg r a p h si so n ei m p o r t a n tb r a n c ho fg r a p ht h e o r y t h e c o l o r i n gt h e o r yh a sm a n yk i n d s ，s u c ha l se d g ec o l o r i n g ，v e r t e xc o l o r i n g ，f a c ec o l o r i n g ， t o t a lc o l o r i n ga n ds oo n a m o n gt h e m ，t h ee d g ec o l o r i n gi sg i v e nm o s ta t t e n t i o na n d h a sm a n yp e r f e c tr e s u l t s t h eo r d i n a r ye d g ec o l o r i n go fg r a p h si sj u s tt od i v i d et h e e d g es e to fgi n t od i s j o i n ti n d e p e n d e n te d g es e t s n o ww ec o n s i d e ro t h e rf o r m si n v 山东大学硕士学位论文 w h i c hw ec a nd i v i d et h ee d g es e t t og e n e r a l i z et h ed e f i n i t i o n so fs o m ev a r i e t i e so f e d g ec o l o r i n g ，w eu s et h ec o n c e p t i o no f ( ， ) 一e d g ec o l o r i n gw h i c hc o n t a i n st h ec o n - c e p t i o n so fl e d g ec o l o r i n ga n df e d g ec o v e rc o l o r i n g i nt h i sa r t i c l e ，o u ra t t e n t i o n i s1 0 c a t e do nt w og e n e r a t i o n so ft h ef e d g ec o v e rc o l o r i n g t h ep a p e ri sd i v i d e di n t ot h r e ec h a p t e r s ，i nc h a p t e ro n e ，w ei n t r o d u c es o m e b a s i cc o n c e p t i o n so fg r a p ht h e o r y , t h eh i s t o r yo ft h ee d g ec o l o r i n ga n dt h ep r o g r e s s o nt h ee d g ec o l o r i n g t h i sc h a p t e ri st h eb a s eo ft h ef o l l o w i n gc h a p t e r s c h a p t e rt w o i sm a j o ri nt h es u p e r ，- e d g ec o v e r - c o l o r i n g i nt h i sc h a p t e r ，t h e m a i nr e s u l ti sa st h ef o l l o w i n gt h e o r e m t h e o r e m2 3 1l e tg = g ( ve ) b eag r a p ha n d1 f ( v ) 【( d 如) 一p ( 口) ) 肛 f o ra l lu v t h e n x ；。( g ) m 。i y nl ( d ( ”) 一“( ”) ) ，( u ) j c h a p t e rt h r e ei sm a j o ri ng - s u p e re d g ec o v e r c o l o r i n g i nt h i sc h a p t e rw eh a v e t h ef o l l o w i n gr e s u l t t h e o r e m3 3 1l e tg ( ve ) b eag r a p ha n d1sf ( v ) l ( d ( a ) 一弘扣) ) 弘j f o ra l l va n d1 g ( v w ) r a i n ( v ) ，( 叫) ) ，f o ra l l 口知e t h e n ；，( g ) m 。i y nl ( d ( ”) 一p ( w ) g ( t u ) ) ，( ) j f u t h e r m o r e ，i nc h a p t e rt w oa n dc h a p t e rt h r e e ，w el i s ts o m ep r o b l e m sf o r f u t u r er e s e a r c h k e yw o r d s ：g r a p h ；m u l t i g r a p h ；e d g ec o l o r i n g ；，一e d g ec o v e r - c o l o r i n g ；s u p e rf - e d g ec o v e r c o l o r i n g ；g - s u p e re d g ec o v e r - c o l o r i n g v l 山东大学硕士学位论文 v ( c ) e ( g ) 占( g ) ( g ) d v ( v ) u ( a ) e ( u ，w ) x ( g ) x ( g ) ) ( ：( g ) x 。址( g ) x ；。( g ) ) ( z ( g ) l x j 符号说明 g 的顶点集合 g 的边集合 g 的最小度 g 的最大度 ”在图g 中的度 g 的重数 ”，w 两点之间的边集合 g 的色数 g 的边色数 g 的覆盖边色数+ g 的，一覆盖边色数 g 的超，一覆盖边色数 g 的9 一超边覆盖色数 不超过z 的最大整数 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：墨鍪型 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 蝣撇：蛆聊虢华攀 山东大学硕士学位论文 第一章引言 本章第一节首先介绍一些本文中常用的图论定义及术语，其他的图论术语 在其他章节必要时再给予阐述第二节介绍图论的边染色理论的历史以及发展 状况第三节简单介绍相关的已有结论及本论文的主要结论 1 1 基本概念 我们首先介绍一些常用的图论术语其他的定义和术语请参见参考文献f 1 1 二元集合g = y ( g ) ，e ( g ) 称为一个图其中v ( a ) ，叫做顶点集合，y ( c ) 的元素叫做图g 的顶点；e ( c ) 叫做边集合，e ( g ) 的元素叫做g 的边当 l y ( g ) i + l e ( g ) l ： ig ( ”) 一c j ( u ) l ”e v c a ) i i ，9 = 1 ，2 ，k ，v v6y ) 尽可能的小假设存在顶点让6v 和i ，j 1 ，2 ，k ) 使a ( 让) 一g ( u ) 2 考虑图g 的边导出子图h = g ( u ；i ，j ) = e ( i ) u e ( j ) 根据 上面的引理2 1 1 ，我们可以用同样的颜色对子图h 重新染色，使得到的后一边染 色c 具有如下性质： ( 1 ) 若d h ( v ) 为奇数，则jq ( 口) 一q ( u ) i = 1 ； ( 2 ) 若d h ( v ) 为偶数，有iq ( u ) 一c ：( 口) i = o ；否则，iq ( ) 一q ( ”) l = 2 ，顶 点v 必属于子图的一个边数为奇数的欧拉分支而且子图日的任一个边数为 奇数的欧拉分支也只存在这样一个顶点w 满足iq ( 叫) 一c ；( 叫) l = 2 ； ( 3 ) 若顶点”v 满足fg ( ”) 一0 ( 可) f = 0 ( 或者= 1 ) ，则有ic ：( ”) 一q ( “) | = 0 ( 或者= 1 ) 成立这些性质保证了iq ( ”) 一c ；( u ) i ，y4 ( 坼) 若我们有a ( v o ) 9 ( v o ) ，那么( q p ) 一交错链就可以生长( 也就是说一次可以 增长上一条边) 交错链最后的顶点阱可以与起始点”o 重合以我们的观点来看， 如果e ，被染上n 色，( ) p ( 珈) + 2 ，并且不为奇圈，那么交换交错链上的颜色 将改进原来的染色方式以下，我们简称交换交错链上的颜色0 _ 和卢为交换 引理2 1 3 给定图g 的一种最优的且使得重边染不同颜色的染色e 令是 g + ( 口，卢) 一条起始于顶点”的( o 卢) ，交错链则交换k 后不会使新的染色比原 来的坏，并且重边染不同颜色的约束不会被破坏 证明首先，交换后我们记新的染色为c 7 在不是奇圈的情况下，我们有 瓯v ) = g ( ) 一1 ，v ) = ov ) + 1 ；不妨设蜥是k 的染p 色的终点，则 瓯( 珥) = gv ，) + 1 ，g ；v r ) = ov ，) 一1 所有k 上的中间点都不受影响，即 g ( 叫) = 巴( 训) ，q ( 叫) = o ( 叫) ，w v n 坼) 所以，当k 不是奇圈的时候，交 换k 不会使染色变坏当是奇圈时，c l ( v ) = c 么( ”) 一2 ，但( u ) = ov ) + 2 所以新染色也没有变坏 至于重边的限制，由于我们是在口( a ，p ) 找的交错链，所以k 中的边的颜 色。( 或p ) 在所处的重边中是唯一的，所以，重新染为口( 或n ) 后没有破坏重边 的要求，从而在原图当中也仍然是满足要求的引理证毕 口 9 山东大学硕士学位论文 下面的这个引理对于本章的主要定理有着重要的作用 引理2 1 4 ( 【2 0 】) 设g = g ( ue ) 是一个图e 是图g 的一种边染色，且q 和 口是其中的两种颜色如果图g 中存在两个顶点z ，y v 使得q ( ) 口( 口) 且 p ( z ) q ( z ) ，o ，p c ，边e = x y 染色为p ，那么一定存在图g 的一条( o ，p ) 一交 错链，它以一条染q 色的边起始于y 点，满足( a ) ，( b ) 和( c ) 中的某一个 ( a ) 既不停止于z 点也不停止于y 点并且不包含边e ( b ) k 包含着边e 而且包含着含有点y 的一个奇圈( 奇圈里并不包含点z 和 边e ) ( c ) k 停止于z 并且包含着不同于e 的染卢色的边e ，而且并不包含边e 证明令k 是一条以一边起始于点y 的交错链 ( 1 ) 既不停止于z 点也不停止于y 点并且不包含边e 这就是情况( a ) ( 2 ) 停止于z 点但并不包含边e k 的最后一条边一定染p 色，因此这种 情况也就是( c ) ( 3 ) k 停止于y 点并且不包含顶点z 和边e 在这种情况里，的最后一条 边必定染颜色o 因此，k 是一个起始于顶点y 并且也终止于顶点y 的奇圈 这样，我们就给加上边e 作为k 的最后一条边这种情况就是情况( b ) ( 4 ) 停止于y 点并且包含边e 但不包含z 点同情况( 3 。) 一样，的最 后一条边也必定染。色因此，k 是包含y 点并且包含边e 的一个奇圈但是 在这种情况里我们可以重新定义交错链使得起始于点y 并且以一条p 一边 终止于点z ( 我们可以反方向的取这个奇圈从点y 到点z 的那一部分) 这种情况 就又是( c ) 了 以上讨论的是边e 不被包含的情况下面我们来讨论边e 也被包含的情况 假设边e 包含在交错链中如果e 被包含在从y 到z 的这个方向里，那么 一定是停止于z 点，这也就是情况( b ) 如果e 被包含在从z 到y 的这个方向 里，则这条链是起始于y 并且e 是其最后的一条边，从而也就是一个偶圈k + 在 这种情况下，我们将这个偶圈+ 从图g 中去除，在剩下的新的图里重新定义交 错链k 边e 将不会在图中出现，这也就是前面讨论的情况( 1 ) ，( 2 。) 和( 3 ) 现 在将k 还原回去情况( 1 ) 和( 2 ) 分别是情况( a ) 和( c ) 情况( 3 ) 如上处理后 就是情况( b ) 从而所有的情况讨论完毕 口 如果h = g ( z ；o ，p ) 是一个奇圈，并且在图g 中我们有q ( 。) = 卢( 。) + 2 ，对 于任意一个顶点 v 工，我们有a ( v ) = p ( ) ，那么我们称图g 的连通子图日 是一个障碍( ( 1 4 和【1 7 】) 显然，并不是所有的多重图都有超，一边覆盖染色( 这与一开始给定的参数，( 口) 和p 有关) 因此，在下一节中，我们首先讨论一下图g 的超，一边覆盖染色的存在性 1 0 山东大学硕士学位论文 条件在第三节中我们再给出色数) ( ；。( g ) 的下界当1 ，( u ) s 【( d ( 口) 一u ( v ) ) l u j 时， ) ( ；c ( g ) 2r a 。i 矿n 【( d ( ) 一p ( u ) ) ，( ”) j 而对于奇圈g 来说， ) ( ；。( g ) = 1 在这种意义下，我们的结论达到了最好 2 2多重图的超，一边覆盖染色的存在性 如果一个图g = g ( ve ) 既没有重边也不包含环那么就是一个简单图若 g ( k e ) 是一个简单图，当1 f ( v ) d ( v ) 时，图g 必定存在一个超，一边覆盖 染色图g 中的所有边均染上同一种颜色，那么这种染色就是g 的一种超，边 覆盖染色接下来，我们总是假定g = c ( v ，e ) 是一个多重图，f ( v ) 是定义在 v ( a ) 上的一个非负整数函数下面的结论可以在 1 7 中找到 定理2 2 1 令g = g ( ve ) 是一个二部图，并且 6 ，= r a i n l d ( v ) f ( v ) j ： v ) 那么就有? 。( g ) = 6 ，而且，如果6 ，= 女2 ，则必定存在图g 的一个，边覆 盖染色c 使得i | e ( i ) i ie ( j ) l i 曼1 ，i ，j6 1 ，2 ，) 并且iz ( ) 一j ( v ) 1 1 ， v ，i ，j 1 ，2 ，) 利用 1 7 】中的证明定理2 2 1 同样的方法，我们得到了下面的定理 定理2 2 2 ( 2 1 】) 令g = g ( ve ) 是一个二部图，6 ，= r n i n 【d ( v ) f ( v ) j ： v ) 并且p = m o z p ( ”) ：口6v ) 设f 是定义在v ( c ) 上的一个非负整数值函数，并 且使得1 f ( v ) sm ( u ) 肛( ”) j ， 6v 那么我们有 x ；。( g ) = 6 ， 证明令k = , i s = r a i n 【d ( v ) f ( v ) j ： y ) 我们从图g ( ke ) 重新构造一个图 g 1 = g - ( m ，e 1 ) 方式如下所示图g 。顶点集合：= v u u v ， t ：u 在图g 中 与 相邻) 图g 。的边集合e 。如下方法构造：如果e = ( u ，口) e ( g ) ，则边( u ，u ”) ， ( 1 1 0 ，抛) 和( 口，巩c ) 都在图g 1 中出现并且其重数p ( u ，u ) = p ( u ， 0 i i , ) = p ( u ，u ) ， p ( u 口，口u ) = k 一肛( u ，u ) ( 若p ( 让， ) = k ，则p ( 让 ，口u ) = 0 ，这就表明牡 和口u 在图 g 1 中是不相邻的) 因此，对每一个u k v ，d ( v ) = 七现在我们在( g ，) 上 山东大学硕士学位论文 定义一个非负整值函数，l ( ”) f l ( u ) = 1 k v ，( 口) ”v 显然图g 1 也是一个二部图由定理2 2 1 ，我们有 ) ( j ，。( g ，) = r a i n r a i n 【d ( v ) f l ( ”) j ： v ) ，r a i n l d ( ) ，1 ( u ) j ：口u y ) ) = r a i n r a i n 【d ( v ) f l ( ) j ： y ) ，m i n d ( v ) ：u y ) ) = m i n 6 i ，k ) = 七 令c 是图g - 的一个正常的用k 种颜色的 一边覆盖染色由于d ( v ) = k 并 且f ( u ) = 1 对所有的u k v 都成立，那么所有与让u ( 或者i l i a ) 邻接的边都染 上了不同的颜色这样与u ( 或者”) 邻接的重边都被染上了不同的颜色也就是 说，这种 一边覆盖染色e 也就是g 1 的一种超，1 边覆盖染色我们又注意到 g 1 中的连接顶点u 和u u 的重边肛( u ，u ”) 恰恰与图g ，中连接顶点u 和抛的重 边p ( u ， u ) 有着相同的颜色因此我们能用上面的颜色来染g 中连接u 和口的 重边，这样我们就得到了图g 的用k = 6 ，种颜色来染色的超，一边覆盖染色注 意到x ；。( g ) 6 ，我们就得到了x ；。( g ) = 酊定理证毕 口 注意定理2 2 2 表明，如果1s ，( u ) s 【d ( u ) 肛( u ) j 对所有的郇ev 都成立，那 么二部图有超，一边覆盖染色，并且x ；。( g ) = 以，为最好的结论 现在我们考虑更为一般的图的情况 定理2 2 3 一个图g 当p = 2 并且v v v ，1 f ( v ) s 【( d ( u ) 一1 ) 2 j 时有超，一 边覆盖染色 证明令c 是图g 的最优的一种2 一边染色并且使得重边染上不同的颜色如 果o ( c ) = o ，那么c 就是g 的一种超，一边覆盖染色现在假定存在某个顶点 u v ，i 1 ，2 ) ，使得吼( u ) 0 很显然一定存在某种颜色j 1 ，2 ) i ，使得 j ( u ) f ( u ) + 1 考虑边导出子图g + ( u ；i ，j ) 由于j ( u ) 一i ( u ) 3 ，由引理2 2 1 ， 我们就能得到g ( u ；i ，j ) 的一种新的2 一边染色c 7 并且使用的是原来g 中染色的 颜色这样我们就使得g 中的重边仍然染不同的颜色，且有盯( c ) m 洲i n 恻”) 一p ( 吼m ) j 证明令k = 哑? l ( d ( t ，) 一p ( ) ) ，( 口) j k = l 的情况是很