（运筹学与控制论专业论文）边染色图中的匹配、圈及图的圆染色.pdf

山东大学，法国巴黎南大学( 巴黎1 1 大) 博士学位论文 边染色图中的匹配、圈及图的圆染色 王光辉 ( 山东大学数学与系统科学学院，济南2 5 0 1 0 0 ) ( 法国巴黎南大学( 巴黎1 1 大) 信息科学实验室，9 1 4 0 0 ) 中文摘要 图论的研究始于2 0 0 多年前关于图论的第一篇论文是1 7 3 6 年e u l e r 发表 的。他用图的方法解决了哥尼斯堡( k s n i g s b e r g ) 七桥同题二十世纪六十年代以 来，图论在科学界异军突起，活跃非凡图论中有很多著名的问题，如哈密尔顿同 题，四色问题，中国邮递员问题等并且，应用图论来解决化学，生物学，信息和 计算机科学等学科问题已显示出极大的优越性同时，图论在工程技术领域及社 会科学中也有着广泛的应用它作为离散数学的一个重要分支，受到了各方面的 普遍重视 我们用g 表示一个图，若g 的每条边都染上颜色，则称g 为边染色图给 定个边染色图g ，关联子顶点口的不同颜色的边的数日。称为顶点口的色度。记 为俨( u ) 如果把一般的未染色图看作是每条边都染不同颜色的边染色图，则顶点 的色度就等于它的度除了在图论和算法上的重要应用外，边染色中的许多问题 还出现在分子生物科学，心理学和网络通信等其它的领域中因此，近年来，这方 面的研究变得活跃起来，主要集中在边染色图中某些特殊子图的存在性上边染 色图中的子图，如果任意相邻的两条边的颜色都不相同，我们称之为交错子图， 或者称为边正常染色子图进一步，如果该子图中所有边的颜色都不相同，我们称 之为彩色子图这两类子图的研究尤其受到关注图的匹配，路和圈是图论中的基 础研究领域，因此边染色图中的彩色的( 交错的) 匹配，路和圈就成了一个重要的 研究方向 图中过每个顶点的圈，称为图的哈密尔顿圈图的哈密尔顿圈问题。是图论中 的一个经典问题其中一个著名的猜想是c h v a t a lf 2 0 提出的如下猜想，韧度充 分大的图有一个哈密尔顿圈对于许多特殊的图类，例如弦图和平面图，上述猜 想被证明是成立的【1 1 ，1 2 ，2 3 1 图g 的一条珏途径是指g 的一条经过每个顶点 至多k 次的闭支撑途径图的个哈密尔顿圈就是图的1 一途径作为哈密尔顿圈 的一个非常有趣的变形，图的肛途径引起了很多人的兴趣j a c k s o n 和w o r m a l d 山东大学。法国巴黎南大学( 巴黎1 1 大) 博士学位论文 5 4 】研究了缸途径，并猜想任意1 - 坚韧图都有一条2 - 途径这个猜想仍然没有 得到证明，最好的结果是任意4 - 坚韧图都有一条2 - 途径【37 】自然地，我们会考 虑如下问题：确定最小的整数= k ( a ) 使得对最大度为的任意图都有一条肛 途径对于一般图，这个问题是平凡的，因为最大度为的任意树都有一途径 【5 4 ，但对于 a ，不含任何k 一途径但如果我们考虑无桥图( 2 - 边连通图) ，情 况就不一样了我们在第五章中。讨论了这个问题 另一方面，图的染色理论在图论中占有很重要的地位近年来，图的圆染色的 研究变的异常活跃，得到了一系列漂亮的结果，也产生了许多新颖的研究方法， 逐渐成为图的染色理论中的一个重要分支图的选择数洌表色数) 是图的一个很 重要的参数，其中一个著名的定理是t h o m a s s e n 8 1 1 的关于平面图的5 - 可选择性 的证明最近，z h u 【8 9 】和m o h a r 6 0 】给出了圆选择数的概念，因此，对平面图 的圆选择数的研究也就成了一个非常有意义的研究方向另外，b o k a l 等 6 9 1 考 虑了有向图的圆染色，把色数和圆色数的概念推广到有向图因此，许多关于无向 图中的染色和圆染色方面的问题。我们都可以在有向图中考虑 本文研究了图论中的几个问题，具体地，我们研究了边染色图中的匹配和圈， 图的k 途径和图的圆染色全文共分为七章第一章。我们给出了个简短但相 对完整的综述首先，我们给出了一些基本的定义和术语，并且对上述三个方向的 研究进展分别做了介绍最后，我们列出了本文的主要结果 在第二章，我们考虑了边染色图中的彩色匹配问题边染色图中的一个彩色 匹配是指任意两条边的颜色都不相同的一个匹配在一般的未染色图中。最大匹 配问题( 找一个边数最多的匹i 己) 是多项式可解的( 6 1 1 ) 丽在边染色图中，即使 是在边染色二部图中，最大彩色匹配问题( 找个边数最多的彩色匹配) 是n p - 完 全的( 【4 5 】) 因此，彩色匹配的研究主要集中在边染色完全图和边染色完全二部图 中e r d 6 s 和p s s a 3 0 l 研究了极值图论中的一个很基本的问题，他们证明了任意 一个顶点个数至少为2 枳最小度至少为k 的图，都有一个k 条边的匹配我们在 边染色图中研究了类似的问题我们证明了若g 是个边染色图，并且对任意点 口都有( 口) k 4 ，则g 含有一个有f 紫1 条边的彩色匹配我们还证明了若 g 是个边染色二部图，并且对任意顶点口，都有 c ( ) 3 ，则g 有个警1 条边的彩色匹配并且，我们给出了色邻域的概念，研究了边染色二部图中，满足 某种色邻域条件的彩色匹配问题 在第三章，我们研究了边染色图中的彩色圈首先，我们给出了边染色图存在 彩色圈的色度条件并且。我们运用关于c a c c e t t a - h g g k v i s t 猜想( 有向图中有向 山东大学。法国巴黎南大学( 巴黎1 1 大) 博士学位论文 三角形存在往) 的个结果，得到了边染色图存在彩色三角形或者彩色四边形的色 度条件同时，我们还研究了边染色图中的长彩色圈 在第四章，我们讨论了边染色圉中色度和交错圈的关系，碍到了边染色图中 几类特殊交错圈存在的色度条件同时，我们还对b o f i o b 6 s - e r d 6 s 猜想( 边染色完 全图中的交错啥密尔顿圈的存在性) 做了研究。给出了满足b o l l o b k s - e r d 6 8 条件的 边染色完全图中，最长交错圈的圈长的一个下界 在第五章，我们研究了图的虹途径，证明了最大度为的任意无桥圈协边 连通图) 都有一条( 4 - 1 ) 2 i 一途径，并且证明了这个界是最好可能的 在第六章，我们考虑m o h a r 【6 9 】提出的关于平面图的圆选择数的一个同题， 研究了具有大围长的平面图的圆选择数我们证明了匿长至少为! 虫学的平面图 的圆选择数至多为2 + ：，从而改进了 5 8 1 中的结果另外。我们还讨论了几类特 殊平面图( 系列平行图，外平面图，奇轮) 的圆选择数 在第七章，我们沿用【7 1 】中的定义。对有向图的染色和圆染色做了进一步的 研究我们证明了如果一个有向图d 的补图不含有向的哈密尔顿圈。则d 的圆 色数( d ) 等于它的色数 ( ( d ) 我们还得出，给定一个正常缸染色的有向图d ， = x ( d ) ，则d 中存在有向路过这k 种颜色这些结果分别对无向图中的相应的 结果做了推广 另外，在每一章里面，我们都提出了几个可以进一步考虑的问题和未解决的 猜想 关键词；彩色匹配；彩色圈；交错圈；k - 途径；圆选择数；圆色数 山东大学，法国巴黎南大学( 巴黎1 1 大) 博士学位论文 m a t c h i n g s ，c y c l e si ne d g e c o l o r e dg r a p h sa n d c i r c u l a rc o l o r i n g g u a n g h u iw a n g ( s c h o o lo fm a t h s y ss c i ，s h a n d o n gu n i v ，j i n a n2 5 0 1 0 0 ) ( l r i ，p a z i s - s u du n i v e r s i t y ( p a r i s1 1 ) ，o r s a y , 9 1 4 0 0 ，f r a n c e ) a b s t r a c t t h es t u d yo fg r a p ht h e o r ys t a r t e do v e rt w oh u n d r e d sy e a r sa g o t h ee a r l i e s t k n o w np a p e ri sd u et oe u l e r ( 1 7 3 6 ) a b o u tt h es e v e nb r i d g e so fk s n i g s b e r g s i n c e 1 9 6 0 s ，g r a p ht h e o r yh a sd e v e l o p e dv e r yf a s ta n dn u m e r o u sr e s u l t so ng r a p ht h e o r y s p r u n gf o r t h t h e r ea r em a n yn i c ea n dc e l e b r a t e dp r o b l e m si ng r a p ht h e o r y , s u c h a sh a m i l t o n i a np r o b l e m ，f o u r - e o f o rp r o b l e m ，c h i n e s ep o s t m a np r o b l e m ，e t c m o r e - o v e l ，g r a p ht h e o r yi s 诵d e l y 印p n e di nc h e m i s t r y , c o m p u t e rs c i e n c e ，s o c i a ls c i e n c e ， b i o l o g ya n do t h e rd i s c i p l i n e s a sas u b f i e l di nd i s c r e t em a t h e m a t i c s ，g r a p ht h e o r y h a sa t t r a c t e dm u c ha t t e n t i o nf r o ma l lp e r s p e c t i v e s l e tgb eag r a p h e a c he d g eo fgi sa s s i g n e dac o l o r t h e ngi sa ne d g e - c o l o r e dg r a p h g i v e na l le d g e - c o l o r e dg r a p hg ，l e td c 扣) ，n a m e dt h ec o l o rd e g r e eo f av e r t e x 口，b ed e f i n e da st h em a x i m u mn u m b e ro fe d g e si n c i d e n tw i t h 口，t h a th a v e d i s t i n c tc o l o r s i fw er e g a r da nu n c o l o r e dg r a p ha sa ne d g e c o l o r e dg r a p hf o rw h i c h a l le d g e sh a v ed i f f e r e n tc o l o r s ，t h e nt h ec o l o rd e g r e eo fav e r t e xi st h ed e g r e eo fi t r e c e n t l y , t h ep r o b l e m si ne d g e - c o l o r e dg r a p l l 8a r o u s ea ne x t e n s i v ei n t e r e s t ，d u et o t h e i rg r e a ti m p o r t a n c ei nt h e o r ya n da p p l i c a t i o n si nv a 矗o u sf i e l d s m a n yo ft h e m c a nb ed e s c r i b e da sf o l l o w s ：g i v e nag r a p h i c a ls t r u c t u r e ( ah a m i l t o n i a nc y c l e ，f o r i n s t a n c e ) w i t hp r e s c r i b e dp r o p e r t i e s ，d o e sag i v e ne d g e - c o l o r e dg r a p hc o n t a i ni t ? a 8 u b g r a p hi na ae d g e - c o l o r e dg r a p h i sc a l l e da l t e r n a t i n gi fa n yt w oa d j a c e n te d g e s h a v ed i s t i n c tc o l o r s ，s o m e t i m e sc a n e dap r o p e r l ye d g e - c o l o r e ds u b g r a p h m o r e o v e r ， i fa n yt w oe d g e so fi th a v ed i f f e r e n tc o l o r s ，t h e nt h i ss u b g r a p hi ss a i dt ob eh e t e - r o c h r o m a t i c ，o rr a i n b o w ，m u l t i c o l o r e d t h e s et w ok i n d so fs u b g r a p h sh a v er e c e i v e d i v 山东大学，法国巴黎南大学( 巴黎1 1 大) 博士学位论文 i n c r e a s i n ga t t e n t i o ni nt h ep a s td e c a d e m a t c h i n g s ，p a t h sa n dc y c l e sa r ea m o n g t h eb a s i cr e s e a r c hf i e l d so fg r a p ht h e o r y , t h u si ti so fs p e c i a li n t e r e s t st os t u d yt h e h e t e r o e h r o m a t i c ( a l t e r n a t i n g ) m a t c h i n g s ，p a t h sa n dc y c l e si ne d g e - c o l o r e dg r a p h s a n o t h e ra c t i v ea l e ao fg r a p ht h e o r yi st h es t u d yo fh a m i l t o n i a nc y c l e s a c y c l et h a tc o n t a i n se v e r yv e r t e xo fg i sc a l l e dah a m i l t o n i a nc y c l eo fg aw e n k n o w nc o n j e c t u r eb yc h v t a l 【2 0 】s t a t e st h a te v e r ys u f f i c i e n t l yt o u g hg r a p hh a sa h a m i l t o u l a nc y c l e t h ea b o v ec o n j e c t u r ew a sp r o v e dt ob et r u ef o rs o m es p e c i a l g r a p h s ，s u c ha sc h o r d a l 窜a p h sa n dp l a n a rg r a p h s ( 8 e e ，e g ，【1 1 ，1 2 ，2 3 】) a n o t h e r a p p r o a c ht oc h v 矗t a l sc o n j e c t u r ei st os h o wt h ee x i s t e n c eo fw e a k e rs u b s t r u c t u r e s t h a nh a m i l t o nc y c l e s ak - w a l ko fgi s8c l o s e ds p a n n i n gw a l kv i s i t i n ge a c hv e t - t e xa tm o s t 南t i m e s ah a m i l t o n i a nc y c l ei st h e na1 - w a l k b e i n ga ni n t e r e s t i n g v a r i a t i o no nt h en o t i o no fah a m i l t o nc y c l e ，k - w a l kh a sr e c e i v e dc o n s i d e r a b l ea t t e n t i o n j a c k s o na n dw o r m a l d 【5 4 】i n v e s t i g a t e dt h ek - w a l ka n dc o n j e c t u r e dt h a t e v e r y1 - t o u g hg r a p hh a sa q - w a l k 7 i h eb e s tr e s u l ti nt h i sd i r e c t i o ni st h a te v e r y 4 - t n u g hg r a p hh a sa 7 - w a l k 【3 7 1 an a t u r a lp r o b l e mi st od e t e r m i n et h el e a s tp o s - s i b l ek = 七( ) s u c ht h a te v e r yg r a p ho fm a x i m u md e g r e eaa d m i t sak - w a l k f o r g e n e r a lg r a p h s t h i sp r o b l e mi st r i v i a ls i n c ea t r e eo fm a x i m u md e g r e e h a sa a - w a l k 【5 4 ，a n di td e a r l yd o 髑n o ta d m i ta n y c - w a l kw i t h 七 a n es i t u a t i o n c h a n g e si fw er e s t r i c to u r s e l v e st ob r i d g e l e s s ( i e ，2 - e d g e - c o n a e c t e d ) g r a p h s w e c o n s i d e rt h i sp r o b l e mi nc h a p t e r5 o nt h eo t h e rh a n d ，t h ec o l o r i n gt h e o r yo fg r a p h sh a sac e n t r a lp o s i t i o ni n g r a p ht h e o r y t h es t u d yo fc i r c u l a rc o l o r i n g sh a sb e e nv e r ya c t i v ei nt h ep a s t d e c a d ea n dt h et h e o r yo fc i r c u l a rc o l o r i n gh a sb e c o m ea ni m p o r t a n tb r a n c ho f c o l o r i n gt h e o r yw i t hm a n y e x c i t i n gr e s u l t sa n dn f f wt e c h n i q u e s ，t h ec h o o s a b h t y o fg r a p h si sa ne x t e n s i v e l ys t u d i e dg r a p hp a r a m e t e r f o re x a m p l e ，w eh a v et h e t h o m a s s e n sc e l e b r a t e dr e s u l t ，t h e5 - c h o o s a b i l i t yo fp l a n a rg r a p h s 【s 1 z h ui s 9 】 a n dm o h a r 【6 9 】g a v ean a t u r a lc i r c u l a rv e m i o no fc h o o s a b i l i t y a n dt h e8 t u d yo ft h e c i r c u l a rc h o o s a b i u t yf o rp l a n a rg r a p h s ，p r o p o s e db ym o h a r 【6 9 ，i sa n o t h e ri n t e r e s t - i n gt o p i c f u r t h e r ，t h ec i r c u l a rc h r o m a t i cn u m b e ra n dt h ec h r o m a t i cn u m b e rh a v e n a t u r a le x t e n s i o n si nd i g r a p h s ( 7 1 1 ) t h u sm a n yi n t e r e s t i n gp r o b l e m sc o n c e r n i n g t h ec o l o r i n ga n dc i r c u l a rc o l o r i n go fg r a p h sc a nb ec o n s i d e r e di nt e r m so fd i g r a p h s t h i st h e s i si sc o n c e r n e d w i t hs o m ep r o b l e m so fg r a p ht h e o r y m o r es p e c i f i c a l l y , v 山东大学，法国巴黎南大学( 巴黎1 1 大) 博士学位论文 o u ra i mi st od i s c u s ss o m et o p i c so nm a t c h i n g s ，c y c l e si ne d g e - c o l o r e dg r 印h s ，缸 w a l k sa n dc i r c u l a rc o l o r i n go fg r a p h s w ch a v ec o n s t r u c t e do u rw o r ki n8 c v c n c h a p t e r s as h o r tb u tr e l a t i v e l yc o m p l e t ei n t r o d u c t i o ni sg i v e ni nc h a p t e r1 f i r s t ， w eg i v es o m eb a s i cd e f i n i t i o n sa n dn o t a t i o n s t h e nw ed e s c r i b es o m cp r o g r c s so f a b o v et h r e et o p i c s a tl a s t ，w eo u t l i n et h em a i nr e s u l t so ft h i st h e s i s t h em a i nf o c u 8o fc h a p t e r2i st oc o n s i d e rt h eh e t e r o c l l r o m a t i cm a t c h i n g s i ne d g e - c o l o r e dg r a p h s ，i nu n c o l o r e dg r a p h s ，t h em a x i m u m m a t c h i n gp r o b l e m ( f i n d i n gam a x i m u mm a t c h i n g ) i ss o l v a b l ei np o l y n o m i a lt i m e ( 6 1 1 ) h o w e v e r ，t h e m a x i m u mh e t e r o c h r o m a t i cm a t c h i n gp r o b l e m ( f i n d i n gam a x i m u mh e t e r o c h r o m a t i c m a t c h i n g ) i ne d g e - c o l o r e dg r a p h si sn p - c o m p l e t e ，e v e i lf o re d g e - c o l o r e db i p a r t i t e g r a p h s ( 4 5 1 ) t h u sm o s to ft h ee x i s t i n gr e s u l t sa b o u ti td e a lw i t ht h ee d g e - c o l o r e d c o m p l e t eg r a p h so re d g e - c o l o r e db i p a r t i t ec o m p l e t e sg r a p h 8 e r d 6 sa n dp 6 s a 【3 0 】 s t u d i e daf u n d a m e n t a lq u e s t i o ni ne x t r e m a lg r a p ht h e o r ya n ds h o w e dt h a te v e r y g r a p ho fo r d e rn 土l e a s t2 ka n dm i n i m u md e g r e ea tl e a s t 知c o n t a i n sam a t c h i n gw i t h e d g e s w es t u d yt h ea n a l o g o u sp r o b l e m si ne d g e - c o l o r e dg r a p h s i nf a c t w e s h o wt h a tf fg i sa ne d g e - c o l o r e dg r a p ha n d 扩( 秽) 2k 4f o re v e i yv e r t e xt ，o fg ， t h e ngh a sah e t e r o c h r o m a t i cm a t c h i n gw i t h 百5 k - 3 1e d g e s a n dw ea l s op r o v et h a t i fgi sa ne d g e - c o l o r e db i p a r t i t eg r a p ha n dd c ( v ) 23f o re v e r yv e r t e x o fg ， t h e ngh a sah e t e r o c h r o m a t i cm a t c h i n gw i t h 警 e d g e s m o r e o v e r ，w ed e f i n et h e + c o l o rn e i g h b o r h o o do fav e r t e xs e ta n ds t u d yt h el a r g eh e t e r o c h r o m a t i cm a t e h i n g s i ne d g e - c o l o r e db i p a r t i t e 窜a p h su n d e rs o m ec o l o rn e i g h b o r h o o dc o n d i t i o n s i nc h a p t e r3 ，w ea r ei n t e r e s t e di ns o m ec o l o rd e g r e ec o n d i t i o n st h a tg u a r a n t e e t h ee 2 d s t e n c eo ft h eh e t e r o e h r o m a t i cc y c l e si ne d g e - c o l o r e dg r a p l l 8 i np a r t i c u l a r ， w eo b t a i nt h ec o l o rd e g r e ec o n d i t i o n si nw h i c ha ne d g e - c o l o r e dg r a p hc o n t a i n s o n eh e t e r o e h r o m a t i ct r i a n g l eo ro n eh e t e r o c h r o m a t i cq u a d r i l a t e r a l o n eo fo u r m a i nt o o l si sar e m i tf o rt h ec a c c e t t a - h 戋g g k v i s t si n t r i g u i n gc o n j e c t u r ea b o u t t h ee x i s t e n c eo ft h ed i r e c t e dt r i a n g l e si nd i g r a p h s a l s o ，w ei n v e s t i g a t et h el o n g h e t e r o c h r o m a t i cc y c l e si ne d g e - c o l o r e dg r a p h 8 i nc h a p t e r4 ，w ed i s c u 铝t h ea l t e r n a t i n gc y c l e sw i t hp r e s c r i b e dl e n 昏h si n e d g e - c o l o r e dg r a p h su n d e rt h ec o l o rd e g r e ec o n d i t i o n s 1 m r t h e r ，w ec o n s i d e ra c o n j e c t u r eo fb o l l o b a s - e r d 6 s ，w h i c hi n v o l v e st h ea l t e r n a t i n gh a m i l t o n i a nc y c l e si n e d g e - c o l o r e dc o m p l e t eg r 印i l s w eg i v eal o w e rb o u n df o rt h el e n g t ho ft h el o n g e s t 山东大学，法国巴黎南大学( 巴黎1 1 大) 博士学位论文 a l t e r n a t i n gc y c l e s ，i ne d g e - c o l o r e dc o m p l e t eg r a p h ss a t i s f y i n gt h eb o l l o b d s - e r d 6 s s c o n d i t i o n i nc h a p t e r5 w es h o wt h a te v e r yb r i d g e l e s sg r a p ho fm a x i m u md e g r e e h a s a ( + 1 ) 1 2 一w a l k i na d d i t i o n ，讹p r o v et h a tt h eb o u n di sb e s tp o s s i b l e i nc h a p t e r6 w ep r o v et h a tt h ec i r c u l a rc h o o s a b i l i t yo fp l a n a rg r a p hw i t h g i r t ha tl e a s t 地学i sa tm o s t2 + ：，w h i c hi m p r o v e sar e s u l ti n 【5 3 】i na d d i t i o n ， w eg i v e8 0 m er e s u l t sa b o u tt h ec i r c u l a rc h o o s a b i l i t yo fs o m es p e c i a lp l a n a rg r a p h s i nc h a p t e r7 ，f o l l o w i n gt h ed e f i n i t i o n i n 【7 l 】，w ei n v e s t i g a t et h ec i r c u l a rc o l - o r i n ga n dc o l o r i n go fd i g r a p h s w ep r o v et h a t ，f o rad i g r a p h ，i fi t 8c o m p l e m e n t c o n t a i n sn od i r e c t e dh a m i l t o n i a nc y c l e ，t h e ni t sc i r c u l a rc h r o m a t i cn u m b e re q u a l s t oi t sc h r o m a t i cn u m b e r w ea l s os h o wt h a tt h e r ee x i s td i r e c t e dp a t h sm e e t i n ga l l c o l o r si nd i g r a p h sw i t hp r o p e rc o l o r i n g s t h e s eg e n e r a l i z es o m ei n t e r e s t i n gr e s u l t s i nu n d i r e c t e dg r a p h s i na d d i t i o n ，w ep r e s e n ts o m eu n s o l v e dp r o b l e m sa n dc o n j e c t u r e st ob ec o n s i d - e r e di nc h a p t e r s2 , 3 ，4 ，5 ，7 k e y w o r d s ：h e t e r o c h r o m a t i cm a t c h i n g ；h e t e r o c h r o m a t i cc y c l e ；a l t e r n a t - i n gc y c l e ；k - w a l k ；c i r c u l a rc h o o s a b i l i t y ；c i r c u l a rc h r o m a t i cn u m b e r 山东大学，法国巴黎南大学( 巴黎1 1 大) 博士学位论文 符号说明 设g 是一个图，其顶点集为y ( g ) ，边集为e ( g ) ( g ，c ) 是一个具有边染色 c 的边染色图设d 是一个有向图，其顶点集合为y ( d ) ，弧集合为a ( d ) 集合s 的基数 不大于茹的最大整数 不小于$ 的最小整数 图g 的顶点集 图g 的边集 图g 的最小度 图g 的最大度 顶点口的在g 中的度数 顶点 在g 中的邻域 图g 的围长 图g 的由s 导出的子图 v i n g g 习 g 扣 出 习 研 吲 m m 郴 即 郴 撕 眦 刚 山东大学，法国巴黎南大学( 巴黎1 1 大) 博士学位论文 d c ( ) 。( s ) x ( c ) k ( g ) x d a ) x “( g ) 站( ”) 蛎( ”) x ( o ) x 。( g ) 顶点w 在边染色图( g ，g ) 中的色度 顶点集合s 在边染色图( g ，g ) 中的一个最大色邻域 图g 的色数 图g 的圆色致 图g 的选择数 图g 的圆选择数 顶点口在d 中的出度 顶点 在d 中的入度 有向图d 的色数 有向图d 的圆色数 l 】c 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：己彩配 日妇：掣 关于学位论文使用授权的声明 本人同意学校保留或向国家有关部门或机构送交论文的印刷件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手 段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签 一：獗期：乎扣 山东大学，法国巴黎南大学( 巴黎l l 大) 博士学位论文 第一章绪论 图论的研究始于2 0 0 多年前关于图论的第一篇论文是1 7 3 6 年e u l e r 发表 的，他用图的方法解决了哥尼斯堡( k s n i g s b e r g ) 七桥问题= 十世纪六十年代以 来，图论在科学界异军突起。活跃非凡图论中有很多著名的问题，如哈密尔顿问 题，四色问题，中国邮递员问题等并且，应用图论来解决化学，生物学，信息和 计算机科学等学科问题已显示出极大的优越性同时，图论在工程技术领域及社 会科学中也有着广泛的应用它作为离散数学的一个重要分支，受到了各方面的 普遍重视 本文研究了图论中的如下问题，边染色图中的匹配和圈。图的肛途径和图的 圆染色 在这一章中，我们给出了一个简短但相对完整的综述，全章共分为五节在 1 1 节。我们给出了一些基本的概念和术语在1 2 ，1 3 和1 4 节中。我们对上述 三个方向的研究进展分别做了介绍在1 5 节，我们列出了本文的主要结果 1 1基本概念和术语 1 1 1图和有向图 一个图g 是指由非空点集v ( c ) 和边集e ( g ) 及惦构成的有序三元组 ( y ( g ) ，e ( g ) ，妒g ) ，其中关联函数妒g 是从边集到g 的无序点对的一个映射如 果e 是一条边并且存在点t 和口满足掣i g ( e ) = 钍u ，则称e 连接点“和点叫点t 和口称为边b 的端点 在本文中，图g 具有有限的顶点集y 和有限的边集e 设s 是一个集合，俐 表示集合s 的基数对图g 中的顶点u ，口的度就是关联于u 的边的条数。我们记 为d g ( 口) 记6 ( v ) = m i n d c ( v ) ：。y ( g ) ) ，a ( g ) = m a x d v ( 口) ： y ( g ) ，则 6 ( g ) 和( g ) 分别表示图g 的最小度和最大度对于g 中的顶点子集s ，s 的邻 域定义为和s 中的顶点相关联的所有顶点的集合。记为n o ( s ) 若s = ” ，则 的邻域记为n d o ) 在不产生混淆的情况下，我们常用ke ，d ( u ) ，最，( s ) ，n ( v ) 山东大学，法国巴黎南大学( 巴黎1 1 大) 博士学位论文 分别代替y ( g ) ，e ( g ) ，d g ( ) ，6 ( g ) ，z x ( g ) ，n t i s ) ， ，g ( ) 若v ( h ) y ( g ) ，e ( h ) e ( g ) ，并且妒h 一惦i f ( 研，其中i 表示将映射掣扫 限制到边集e ( h ) 上，则称图日是图g 的子图在图g 中设子集s y ( g ) ，图 g 的由顶点集s 导出的子图记为a s l ，其顶点集为s ，边集是= u v e ( g ) ： u ，u 研，并且关联函数是妒g ie ，设岛cy ( g ) ，用g s 1 表示图g 的删去点 集研和与其关联的边后得到的子图图g 的支撑子图日是指图g 的子图且满 足v ( h ) = y ( g ) 图g 的个匹配