（运筹学与控制论专业论文）3连通图中圈上可去边的一些性质.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本 文的研究作出重要贡献的个人和集体，均已在文中以明确方式标 明。本声明的法律责任由本人承担。 论文作者签名：立叠日期：尘! 竺：复! 万 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意 学校保留或向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他 复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：二谴导师签名：趔喜匿融日 期：趔 r k j 目录 中文摘要i 英文摘要i i i 符号说明v 第一章引言1 1 1 背景介绍1 1 2 本文的结构7 第二章基本定义与符号8 第三章3 连通图中的可去边1 1 3 1 相关知识和已知结果1 1 3 23 连通图中7 圈上的可去边1 4 3 33 连通图中8 圈上的可去边1 6 第四章总结与展望2 2 参考文献2 3 致谢2 6 c o n t e n t s c h i n e s ea b s t r a c t i e n g l i s ha b s t r a c t i i i n o t a t i o n s 。1 0 7 c h a p t e r1 i n t r o d u c t i o n 1 1 1b a c k g r o u n do f t h er e s e a r c h 1 1 2 s t r u c t u r ec o n t e n t 7 c h a p t e r2 b a s i cd e f i n i t i o na n dn o t a t i o n s 8 c h a p t e r3 r e m o v a b l ee d g e si n3 - c o n n e c t e dg r a p h s 。】【1 3 1 r e l e v a n tk n o w l e d g ea n dk n o w nr e s u l t s 11 3 2 r e m o v a b l ee d g e si n7 - c y c l e so f3 - c o n n e c t e dg r a p h s 1 4 3 3 r e m o v a b l ee d g e si n8 - c y c l e so f 3 一c o n n e c t e dg r a p h s 1 6 c h a p t e r 4 c o n c l u s i o na n df u t u r e 2 2 r e f e r e n c e s ：! ：； a c k n o w l e d g e m e n t s ：1 6 1 1 j 山东大学硕士学位论文 3 连通图中圈上可去边的一些性质 亓涛 山东大学数学学院，运筹学与控制论，济南，山东2 5 0 1 0 0 中文摘要 图的连通性是图最基本的性质之一，是图论中重要的研究课题连通图与网络 模型和组合优化联系密切，使它具备很强的应用背景特别足近二十年来，随着计 算机与网络技术的迅速发展，这一联系日益密切连通图中的可收缩变与呵去边是 探讨图的结构特征，寻求以递归方式证明图的某些性质的重要工具，对它们的研究 具有重要的理论价值和应用价值随着数学归纳法在图论中的广泛应用，图的“简 约”日益受到重视它足指在保持图的某种性质的前提下使图的阶数或边数减少的 一系列运算的综合图的可缩边与可去边就是在这种背景下产生的 本文主要研究3 连通图中可去边的性质，以及可去边在圈上的分布情况下面 简单介绍一下本文的主要结果如无特别说明，文中的图g 均为简单图 首先我们给出可去边与不可去边的定义定义如下： 对于3 连通图中的一条边e = x y 进行如下运算： ( 1 ) 从图g 中删除边e = x y ，得到g e ( 2 ) 如果存在一点“ 五纠，使得“在g e 中的临域 乞一。( “) ； w y j ，则用边 删代替g e 中的路w u v ( 3 ) 经过( 1 ) ( 2 ) 运算所得的图g 如果有重边，则删除g 7 的重边，使g 7 的每条 边的重数都为一 用g o e 表示g 经过( 1 ) ( 2 ) ( 3 ) 运算所得到的图如果gee 是3 连通图，则称e 是g 的可去边，或称e 可去；否则称e 是g 的不可去边或称e 不可去用岛( g ) 表 示g 的可去边集，e r ( g ) 表示g 的可去边数，e ( g ) 和即( g ) 分别表示g 的不可去 边集和不可去边数 对于3 连通图中圈上的可去边分布，本文对已有的部分研究成果进行了推广， 得出下述两条结论： 定理3 1 如果c 是不同构于氓的3 连通图g 的一个7 圈，那么。 r，。k l 山东大学硕士学位论文 le ( c ) ne r ( g ) i 1 ； 或者g 中存在同构于孵+ 的子图，且cc ”+ 其中如阮) = 如( y ，) = 3 ，i = 2 ，3 ，4 ；d e ( a ) 4 ；无( 6 ) 4 定理3 2 如果c 是不同构于的3 连通图g 的一个8 圈，那么； le ( c - ) ne r ( g ) i l ； 或者g 中存在同构于孵，畔，孵中任意一种的子图，且c 包含在子图中其中 比“) = 比( y i ) = 3 ，i = 2 ，3 ，4 ；a t ( a ) 4 ；如( 6 ) 4 ( 有关图叼。，明，畔，嘭的构造方法详见正文部分) 关键词：连通图；可去边；可收缩边 1 1 山东大学硕士学位论文 r e s u l t so fr e m o v a b l ee d g e si nc y c l e so f3 一c o n n e c t e dg r a p h s q i t a o 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 ，r e c h i n a a b s l 。r a i ：l t h e c o n n e c t i v i t yo f g r a p h si so n e o f t h em o s ti m p o r t a n tp r o p e r t i e so f g r a p h s c o n n e c t e dg r a p h sp l a ya ni m p o r t a n tr o l ei np r a c t i c a la p p l i c a t i o n sb e c a u s eo fi t sc l o s ec o n n e c t i o nw i t hn e t w o r km o d e la n dc o m b i n a t o r i a lo p t i m i z a t i o n w i t ht h er a p i dd e v e l o p m e n t o fc o m p u t e r sa n di n t e r n e t ，t h i sc o n n e c t i o ni sc l o s e rt h a ne v e rb e f o r eo v a * i t h ep a s tt w o d e c a d e s c o n t r a c t i b l ee d g e sa n dr e m o v a b l ee d g e sa r ep o w e r f u lt o o l st os t u d yt h es t r u c t u r e o f g r a p h sa n dt op r o v es o m ep r o p e r t i e so f g r a p h sb yi n d u c t i o n n e ) ，a r ev e r yi m p o r t a n ti n b o t ht h e o r e t i c a lr e s p e c ta n dp r a c t i c a la p p l i c a t i o n s w i t hi n d u c t i o nw i d e l yu s e d ，o p e r a t i o n s i ng r a p h sw h i c ha r eas e r i e so f a l g o r i t h m st h a tr e d u c et h en u m b e ro f v e r t i c e so re d g e si na g r a p hw i t hk e e p i n gs o m ep r o p e r t ya r em o r eu s e f u ld a yb yd a y i nt h i sc o n t e x t ，r e m o v a b l e e d g e sa n d c o n t r a c t i b l ee d g e sa r eu s e di nr e s e a r c h t h i sp a p e rf o r c e so nt h ep r o p e r t i e so fr e m o v a b l ee d g e si n3 - c o n n e c t e dg r a p h s ，a n d t h e i rd i s t r i b u t i o n si nc y c l e s t h ef o l l o w i n ga r et h em a i nr e s u l t s i nt h i sp a p e r , gi sas i m p l e g r a p h f i r s t ，w ew i l lg i v ead e f i n i t i o n c o n s i d e rt h ef o l l o w i n go p e r a t i o n s ： ( 1 ) d e l e t eef r o mg ，r e s u l t i n gi nt h eg r a p hg e ( 2 ) i fs o m ee n d v e r t i c e so feh a v ed e g r e e2i ng e , t h e nj o i n tt h e m ( 3 ) i fm u l t i p l ee d g e so c c u r , w eu s es i n g l ee d g e st or e p l a c et h e m t h ef i n a lr e s u l t a n tg r a p ha f t e r ( 1 ) ( 2 ) ( 3 ) o p e r a t i o n si sd e n o t e db ygep f o ra3 一 c o n n e c t e dg r a p hg ，i fgeei ss t i l l3 - c o n n e c t e d ，t h e nt h e e d g eei sc a l l e dr e m o v a b l e ；o t h e r - w i s e ，i ti sc a l l e du n r e m o v a b l e t h es e to fa l lr e m o v a b l ee d g e so fg i sd e n o t e db y 艮( g ) ； w h e r e a st h es e to fa l lu n r e m o v a b l e e d g e so fg i sd e n o t e db ye n ( g ) t h en u m b e ro fa l l r e m o v a b l ee d g e sa n du n r e m o v a b l ee d g e so fga r ed e n o t e dr e s p e c t i v e l yb ye r ( g ) a n d p ( g ) f o rr e m o v a b l ee d g e si nc y c l e so f3 - c o n n e c t e dg r a p h s ，w ew i l lg i v et w or e s u l t sa s h i i-，lp 山东大学硕士学f 镜论文 f o l l o w s ： t h e o r e m3 1i fci sa7 - c y c l ei n3 - c o n n e c t e dg r a p hgw h i c hi sn o ti s o m o r p h i ct o ，t h e n ： ie ( c ) ne r ( g ) i l ； o rgc o n c l u d eas u b g r a p hw h i c hi si s o m o r p h i ct ow ：* , w h e r ecc 孵a n dd g ( x i ) = 如( ”) = 3 ，f = 2 ，3 ，4 ；d e ( a ) 4 ；d o ( 6 ) 4 t h e o r e m3 2i fci sa8 - c y c l ei n3 - c o n n e c t e dg r a p hgw h i c hi sn o ti s o m o r p h i ct o w 9 ，t h e n ： ie ( c ) ne r ( g ) l l ； o rgc o n c l u d ea tl e a s to n es u b g r a p hw h i c hi si s o m o r p h i ct ot h eg r a p ho f 哦，w ：o r 纬善，w h e r ec c o n t a i n si n s i d ea n dd c ( 工f ) = d o ( n ) = 3 ，= 2 ，3 ，4 ；d c ( 曲4 ；d c ( 6 ) 4 ( t h ec o n s t r u c t i o nm e t h o d sa b o u t 孵，孵，晔a n d 嘭a r ei nt h et e x t ) k e y w o r d s ：c o n n e c t e dg r a p h s ；r e m o v a b l ee d g e ；c o n t r a c t i b l ee d g e i v j一 山东大学硕士学位论文 以g ) e ( g ) i g i “g ) d g ) 巧( g ) ( g ) 6 0 ) 如( 力 g s 】 g s g 一， e c ( e ) e r ( g ) 正( g ) e r ( c ) 钳( g ) ( 砂，s ；a ，回 符号说明 g 的顶点集合 g 的边集合 图g 的阶 g 的顶点数 g 的边数 g 的最小度 g 的最大度 点x 在g 中的临域 点y 在g 中的度 由s 导出的g 的子图 h g ) s 的导出子图 v ( g ) v 的导出子图 g 中可收缩边的集合 g 中可去边的集合 g 中不可去边的集合 g 中的可去边数 g 中的不可去边数 与砂对应的分离组 v 山东大学硕士学f 靛论文 山东大学硕士学位论文 第一章引言 在这一章中，我们首先对连通图中可去边与可收缩边研究的历史背景和进展情 况进行简要介绍，然后简单概括一下本文的主要结构与框架 1 1 背景介绍 图的连通性理论是图论最重要的组成部分之一，它的任何实质性的研究进展都 会对图论的发展产生重大的推动作用因而，它一直是图论与组合数学界的学者重 点关注的对象，w o l f 奖得主l o v f i s z 也曾致力于该理论的研究连通图与网络模型 和组合优化联系密切，使它具备很强的应用背景特别是近二十年来，随着计算机 与网络技术的迅速发展，这一联系e l 益密切因而，对它们的研究具有重要的理论 价值和应用价值 讨论连通图的结构特征，寻求连通图的构造方法一直是图论研究的前沿课题之 一随着应用领域的不断拓展，对它们的研究已成为近二十年来图论研究的热点 在各类连通图递归的构造研究中，为了使任意连通图都可以由一些简单的连通图重 复某些运算而得，最常用的方法就是引入一些保持图的连通性的运算对本论文即 将讨论的连通图中可去边的研究就是在这种背景下产生的早在1 9 6 1 年t u r e 8 1 给 出3 连通图的结构特征时，其实就是利用了3 连通图的可收缩边与可去边的存在性 质 连通图中的可收缩边与可去边不仅是研究连通图构造的有力工具，在使用归纳 法证明连通图的一些性质中也起到了重要的作用例如，当k 连通图去掉一条边并 做某些变形以后，若得到的图依然足k 连通图，由于新得到的图的边或顶点数比原 图少，如果它还保持图的某种给定性质( 比如图的连通性) ，则可将对复杂图的某 种特性的研究递归的转化为对较为简单的图的相应性质的研究1 9 6 1 年t u n e 8 】给 出了阶至少为5 的3 连通图都包含可收缩边的结果t h o m a s s e n 6 】在1 9 8 1 年利用 山东大学硕士学儆论文 这一结果使用归纳法简单的证明了关于平面图的三个著名的定理，即k u r a t o w s k i 定 理、f a r y 定理和t u t t e 定理而在此之前，上述三个定理的证明过程都非常的繁琐 目前，连通图中可收缩边与可去边的存在性及其分布情况已经成为人们十分关 注的课题本文也将以连通图中可去边的性质以及它们在特定子图( 圈) 上的分布 情况为主要研究对象下面，我们来分别介绍连通图中的可收缩边与可去边的研究 进展及部分研究成果 先来看对连通图中可收缩边的研究 定义1 1 1 8 】设g 是k 连通图，砂足g 中一条边如果在g 中将x 与y 收缩为一个顶 点所得到的图仍然足k 连通的，则称砂是g 的可收缩边 k 连通图将可收缩边收缩之后得到比原来更小的连通图，由于我们所考虑的图 都是有限图，经过有限次边的收缩以后，最后得到不存在可收缩边的k 连通图的结 构，也即收缩临界k 连通图的结构所以，对连通图中可收缩边的研究主要分为以 下两个方面： 1 对收缩临界k 连通图的研究 这方面最早的研究成果由t u t t e 8 1 在1 9 6 1 年给出，结果如下； 定理1 1 【8 】若g 是3 连通图，igi 4 ，则图g 中必含有可收缩边 从这个结论很容易看出，阶大于4 的收缩临界3 连通图是不存在的 对于收缩临界4 连通图的结构的研究，m a r t i o n o v 2 9 1 于1 9 8 2 年证明了如下定 理： 定理1 2 【2 9 】收缩临界4 连通图g 是4 连通，4 正则的，且每条边恰在一个三角形 上 上述结论说明，收缩临界4 连通图g 或者足暖或者是7 胆边连通立方体的线 图而7 2 边连通立方体可由肠或尬4 去掉一因子的图通过构造的方法而得到 对于收缩临界5 连通图的结构的研究，k a n d o ( 9 】等证明了收缩临界5 连通图不 是5 正则的且它所有的边并不都包含在一个甲凡割中，还得到了以下结论： 2 山东大学硕士学位论文 定理1 3 t 9 】对任意图日，存在收缩临界5 连通图g 使得h 是g 的导出子图 由于k 5 时，收缩临界k 连通图的结构比较复杂，因此，利用收缩边运算构造 足连通图的问题还没有得到完全解决 e g a w a t 3 2 】证明了每个收缩临界k 连通图有一个基数小于等于k 4 的断片，于是 可得当k = 4 ，5 ，6 ，7 时，收缩临界k 连通图的最小度等于k 在这之后，出现了大量的 与收缩临界k 连通图中顶点的度相关的研究下面是关于这方面研究的部分成果。 定理1 4 f 3 2 1 设g 是k 连通图，k 7 ，且对g 中任意两个距离小于等于2 的顶点x 与y ，满足烈力+ d r y ) 2 【誓j 一1 ，则g 中有可收缩边 定理1 5 【3 2 】每一个收缩临界7 连通图中有两个7 度顶点 定理1 6 f 3 2 1 每一个收缩临界7 连通图中有两个距离至多是2 的7 度顶点 2 对k 连通图中可收缩边的分布的研究 a n d o ，e n o m o t o 和s a i t o 9 】在1 9 8 7 年对3 连通图中可收缩边的数目进行了研究。 得到了： 定理1 7 【9 】设g 是除凰外的任一3 连通图，则g 至少有f i g i 2 条可缩边 他们还刻划了达到此下界的图类： 定理1 i n 设g 是除忍外的3 连通图，则下列三条陈述等价： ( 1 ) 恰好有f i g i 2 条可缩边 ( 2 ) g 是3 正则的且每个点均在某个三角形中 ( 3 ) g 可由某个3 正则3 连通图将每个点均用一个三角形替换而得到 m c c u a i g l l l 】在1 9 9 0 年将图类限制到极小3 连通图后，给出了一个好的下界： 定理1 9 1 设g 是除肠外的任一极小3 连通图，则g 至少有i c l 2 + 3 v , d 条可缩 边其中y ，为g 中非3 度点的数目 t h o m a s s e n 6 通过研究3 连通图的某些子分类和寻找这些子分类中可收缩边或 不可收缩边的导出子图的性质，在1 9 8 1 年给出： 定理1 1 0 6 1 每一个无三边形的3 连通图g 包含一个圈c 使得e ( c ) e 3 ( g ) 3 山东大学硕士学位论文 a l d r c d 2 0 】在19 9 2 年用另一种3 连通图的子结构研究可收缩边在最大匹配上的 分布情况： 定理1 1 1 2 0 】不同构于心的3 连通图的最大匹配i 二至少包含一条可收缩边 目前，对于3 连通图中可收缩边的分布和数目的研究已取得了丰富的研究成果 而对烈七4 ) 连通图中可收缩边的分布情况和数目还知之甚少，有待于进一步的探 讨后来人们把3 连通图中收缩边的概念推广为收缩子图，把收缩临界图的概念推广 至3 临界图其他关于连通图中可收缩边的研究可参见文献 1 8 ，【1 9 l 【2 1 ，【2 3 3 1 】 等 下面我们来看一下对连通图中可去边的研究 h o l t o n 等1 2 于1 9 9 0 年首先给出了3 连通图中可去边的定义 定义1 2 【2 1 设e 是3 连通图g 的一条边，考虑下列运算： ( 1 ) 从g 中去掉e 得图g e ( 2 ) 如果e 的某个端点在g e 中度数为2 ，则去掉此端点，再联结此端点在g e 中的两个邻点 ( 3 ) 如果经过( 2 ) 中的运算后，有重边出现，则用单边代替它们，使得此图为简 单图 最后所得到的图记为gee 若ge e 仍为3 连通图，则称e 为g 的可去边，否 则称e 为g 的不可去边 关于可去边的研究成果，最早由b a m e u e 和g r u n b a n m 3 】给出他们得到了一 个类似可收缩边的结果，证明了每个阶大于4 的3 连通图都有可去边，并给出了3 连通图的一个递归构造方法d a w e s f 3 0 】利用这个结果给出了与 l u r e 8 1 不同的极小 3 连通图的递归构造方法 另外，f o u q u e t 和t h u i l l i e r t 4 l 在1 9 8 8 年研究了3 正则3 连通图中的可去边，得 到了： 定理1 1 2 4 每个阶至少为6 的3 正则3 连通图至少有( i g i + 6 ) 2 条可去边 4 山东大学硕士学位论文 对于连通图中可去边的数目与分布，苏建基 1 3 1 1 4 】得n t 下面几个定理： 定理1 1 3 ( j i 蟹j l3 1 1 ) 1 1 3 j 设g 足阶大于5 的3 连通图，并且g 不是轮，c 是g 上的 一个圈，那么 ( 1 ) 如果c 仅通过一个极大半轮，则c 上至少存在一条可去边 ( 2 ) 如果c 不通过任何极大半轮，则c 上至少存在两条可去边 定理1 1 4 1 4 】每个阶至少为5 的3 连通图，除和甄外，至少存在f ( 3igi + 1 8 ) 7 1 条可去边 1 9 9 9 年尹建华f 2 8 】又将可去边的定义推广到了4 连通图，并给出了4 连通图中 不存在可去边的充要条件 定义1 3 【2 8 1 设e 足4 连通图g 的一条边，考虑下列运算： ( 1 ) 从g 中去掉e 得图g e ( 2 ) 如果e 的某个端点在g e 中度数为3 ，则去掉此端点，再联结此端点在g e 中的三个邻点 ( 3 ) 如果经过( 2 ) 中的运算后，有重边出现，则用单边代替它们，使得此图为简 单图 最后所得到的图记为gee 若gee 仍为4 连通图，则称e 为g 的可去边，否 则称e 为g 的不可去边 定理1 1 5 2 s 设g 足4 连通图，g 中不存在可去边当且仅当g 是q 或足c ： 利用这个结果和可收缩边的性质，尹建华又给出了4 连通图的一个递归构造方 法 对于4 连通图中可去边的分布，吴吉昌等 2 7 1 给出如下结果； 。 定理1 1 6 1 2 7 】设g 是阶大于5 的4 连通图，若6 ( g ) 25 或反g ) 4 ，则对于g 上的 任一个圈e 满足l ( c 1 ) f l e r ( g ) i 之2 其中双g ) 表示g 的围长 定理1 1 7 t 2 7 】设g 是阶大于7 的4 连通图，c 是g 中一个最长圈则： ( 1 ) 如果c 仅通过一个双三角形，则c 上至少存在一条可去边 5 山东大学硕士学f 靛论文 ( 2 ) 如果c 不通过任何一个双三角形，则c 上至少存在两条可去边 最近，厦门大学的徐丽琼在其博士毕业论文 2 6 中取得了突破性进展，她将可 去边的概念引入到了一般的k 连通图中，通过研究拟连通图与可去边之间的关系， 探讨k 连通图中可去边的存在性f q n ，得到了一种5 连通图的构造方法主要结果 如下： 定义1 4 【2 6 】设e 是k 连通图g 的一条边，考虑下列运算： ( 1 ) 从g 中去掉e 得图g e ( 2 ) 如果e 的某个端点在g e 中度数为k 一1 ，则去掉此端点，再联结此端点在 g e 中的k 一1 个邻点 ( 3 ) 如果经过( 2 ) 中的运算后，有重边出现，则用单边代替它们，使得此图为简 单图 最后所得到的图记为g e e 若g e e 仍为k 连通图，则称e 为g 的可去边，否 则称e 为g 的不可去边 定义1 5 【2 6 】若g 是七 3 ) 连通图且不存在非甲凡的k 点割，则称g 是拟k + 1 连 通图 定理1 1 8 t 2 6 】设g 是颤七3 ) 连通图，igi k + 3 ，g 中不存在可去边当且仅当g 足 极小拟k 连通 定理1 1 9 2 6 】设g 是5 连通图，g 中不存在可去边当且仅当g 兰k 6 利用这个结果，徐丽琼首次给出了5 连通图的一个递归构造方法，并提出以下 猜想： 猜想1 1 【2 6 1g 是k ( k 3 ) 连通图，g 中不存在可去边当且仅当k 为奇数时，g 兰鲰l ； 当k 为偶数时，g 兰k k + l 或凰+ 2 很显然，如果上述猜想成立，则可用统一的方法给出k 连通图的一个递归构造 方法 其它关于连通图中可去边的研究可参考文献 1 5 】， 1 6 1 ， 1 7 】，【2 4 】，【2 5 等 6 山东大学硕士学位论文 1 2 本文的结构 本文共分为四个章节 第一章，弓l 言交代本文的研究背景与研究方向，并对图论中的一些基础知识 进行必要的说明 1 1 背景介绍系统介绍有关连通图中可收缩边与可去边的研究背景和研究 意义，以及以往的一些重要研究成果 1 2 本文的结构简单概括本文的主要结构与框架 第二章，基本定义与符号简要介绍一下图论中需要了解的基础知识，以及一 些常用的数学符号 第三章，3 连通图中的可去边在这一章中，我们主要对3 连通图中可去边的 性质及分布进行研究，主要研究成果包括：3 连通图中7 圈上可去边的分布，以及3 连通图中8 圈上可去边的分布 3 1 相关知识和已知结果介绍与3 连通图中可去边相关的一些基本知识，和 证明下面两节的结论时需要用到的一些已知结果 3 23 连通图中7 圈上的可去边对3 连通图中7 圈上的可去边的性质及分布 情况进行研究 3 33 连通图中8 圈上的可去边对3 连通图中8 圈上的可去边的性质及分布 情况进行研究 第四章，总结与展望总结了本文讲述的内容与创新点，并指出文中值得进一 步探讨和研究之处 7 山东大学硕士学位论文 第二章基本定义与符号 在这一章中，我们介绍一些有关本文中需要了解的的基本概念与符号，其它未 特别说明的符号和术语参见文献【l 】 图g 代表一个有序三元组( 以g ) ，e ( g ) ，砂6 ) ，这里以g ) 表示非空顶点集，e ( g ) 表示与以g ) 中顶点相交的边集，是关联函数，它使g 的每条边对应于g 的无序 顶点对( 不必相异) 若e 足一条边，u 和v 足使得惦( p ) = u v 的顶点，则称e 连接u 和v ，顶点u 和y 足e 的端点，且顶点“和顶点，与边e 相关联，顶点”和顶点v 相 邻并互为邻点n o ( v ) 代表由顶点v 在图g 中所有的邻点所组成的y 的邻域，简记 为( v ) 。令】，y ( g ) ，记n d y ) = u 炬r g y 图g 中的顶点数和边数分别用v ( g ) 和s ( g ) 表示v ( g ) 中的元素个数称为g 的阶，记为i g i ，则有i g i = y ( g ) g 的顶点 ，的度( 或次) 是指g 中与v 关联的边 的数目，记为d d v ) 如果图g 中各个顶点的度数都等于k ，则称g 是足正则图用 6 ( g ) 和( g ) 分别表示g 中顶点的最小度和最大度d ，表示g 中恰与】，中某个顶点 相关联的边数端点重合为一点的边称为环一个图称为简单图，如果它既没有环 也没有两条边连接同一对顶点如果图g 的顶点集和边集都有限，则称图g 为有限 图每一对不同的顶点都有一条边相连的简单图称为完全图刀的顶点的完全图记 为在本文中，我们仅考虑有限的简单图 两个图g 和月是恒等的( 记为g = 日) ，如果y ( g ) = 以爿) ，e ( g ) = e c 印 并且谚g = 砂两个图g 和称为同构的( 记为g 兰h ) ，如果存在两个一一映射 p ：y ( g ) 一( 爿) 和妒：e ( g ) - e ( 加，使得砂g ( p ) = “1 ，当且仅当砂h ( 妒( p ) ) = 吠甜) p ( d 称图日是g 的子图( 记为h g ) ，如果y ( 奶纵g ) ，( 邡e ( g ) ，并且妇 是砂6 在e ( 加上的限制当h g ，但h g 时，记为hcg ，并且称日是g 的真 子图若图日足g 的子图，则称g 是h 的母图g 的生成子图( 或生成母图) 是指 满足v ( g ) = 以t - 1 ) 的子图( 或者母图) h 从图g 中删去所有的环，并使每一对相 邻顶点只保留一条连接的边，即可得到g 的个简单生成子图，称为g 的基础简单 8 山东大学硕士学位论文 图 设是h g ) 的一个非空子集，以为顶点集，以两端点均在中的边的全 体为边集所组成的子图，称为g 的由导出的子图，记为g 【】，g w 】称为g 的 导出子图导出子图g v 】简记为g 一，它是从g 中删去中的点以及所有 与这些点相关联的边所得到的子图若= y ，则把g 一 v 简记为g v 设e 7 是e ( g ) 的非空子集，以e 7 为边集，以e 7 中边的端点的全体为顶点集所 组成的子图称为g 的由e 7 导出的子图，记为g e 】，g e 】称为g 的边导出子图 边集为7 的g 的生成子图简记为g e 7 ，它是从g 中删除e 7 中的边所得到的 子图类似的，在g 中添加边集f 的所有边得到的图记为g + f 如果e = p ，则 可分别将g 一 e 和g + e 简记为g e 和g + e 设g l 和g 2 是g 的子图，如果g l 和g 2 没有公共顶点，则称它们是不相交 的，g l 和g 2 的并图g lug 2 是指g 的一个子图，其顶点集为v ( g 1 ) uv ( g 2 ) ，其边 集为e ( g 1 ) ue ( g 2 ) 如果g l 和g 2 足不相交的，可记其并图为g l + g 2 设m 足e ( g ) 的一个子集，它的元素足g 中的边，并且这些边中的任意两条在 g 中均不相邻，则称m 是g 的一个匹配或对集若匹配肘的某条边与顶点y 相关 联，则称m 饱和顶点1 ，如果图g 的一个匹配m 饱和g 中的每一个顶点，则称m 是g 的一个完美匹配或完美对集 g 的一条途径( 或通道) 足指一个有限非空序列w = r o e l v l e 2 v 2 e k v k ，它的项 交替的为顶点和边，使得对l i k ，e i 的端点是和睢1 称是从v o 到的 一条途径顶点v o 和v k 分别称为的起点和终点，而v l ，屹，l 称为它的内部 顶点，整数后为的长如果途径的边e l ，e 2 ，玖互不相同，则称为迹；如 果v o ，y l 互不相同，则称形为路端点相同但内部顶点不相同的迹称为圈，长 为k 的圈称为k 圈，记作q 长度为奇数的圈为奇圈，否则为偶圈g 的围长是指 g 中最短圈的长，记为g ( g ) ；若g 中没有圈，则定义g 的围长足无穷大 图g 中的一条路被称为h a m i l t o n 路，如果它经过g 中的所有顶点经过g 9 山东大学硕士学位论文 中所有顶点的圈被称为g 的h a m i l t o n 圈如果g 中存在h a m i l t o n 圈，则称g 为 h a m i l t o n 图，或者说g 是h a m i l t o n 的 如果g 的任意两个顶点之间都有连接它们的路，则称图g 是连通的不连通图 的极大连通子图称为此图的连通分支，图的连通分支的数目用t o ( g ) 来表示若存 在v ( g ) 的子集y 7 使得g 一不连通，则称为g 的顶点割k 顶点割足指含有k 个元素的顶点割若g 至少有一对相异且不相邻的顶点，则g 所具有的k 顶点割中 最小的k ，称为g 的连通度，记为“g ) ；否则定义( g ) 为l g l 一1 其中，如果g 是 甲凡的或者非连通的，那么k ( g ) = 0 若k ( g ) k ，则称g 足k 连通的所有非甲凡 的连通图都是1 连通的 1 0 山东大学硕士学位论文 第三章3 连通图中的可去边 本章主要介绍了3 连通图中可去边的性质，以及可去边在圈上的分布情况在 第一节中我们介绍有关3 连通图中可去边的一些基本知识，以及证明第二、三节的 结论时需要用到的一些已知结果在之后的两节里，我们分别给出了3 连通图中7 圈和8 圈上的可去边的性质及分布情况 3 1 相关知识和已知结果 定义3 1 t 2 】设e 是3 连通图g 的一条边，考虑下列运算： ( 1 ) 从g 中去掉e 得图g e ( 2 ) 如果e 的某个端点在g - e 中度数为2 ，则去掉此端点，再联结此端点在g e 中的两个邻点 ( 3 ) 如果经过( 2 ) 中的运算后，有重边出现，则用单边代替它们，使得此图为简 单图 用g e e 表示g 经过( 1 ) ( 2 ) ( 3 ) 的运算后得到的图若g e e 仍为3 连通图，则称 e 为g 的可去边，否则称e 为g 的不可去边用岛( g ) 表示g 的可去边集，e r ( g ) 表 示g 的可去边数，毋( g ) 和e u ( g ) 分别表示g 的不可去边集和不可去边数 引理3 1 t 2 】设g 6 ，x y ( g ) ，则x y e ( g ) 的充要条件为存在s v ( g x y ) ，i s i = 2 ，使g 一砂一s 恰有2 个分支a 与召，其中x a ，y b 且m i 2 ，i b i 2 这时称( x y ，s ) 为g 的分离对，称( x y ，s ；a ，功为g 的分离分解，彳，b 称为由 ( 砂，s ) 分离g 所得的边一点割断片，简称为g 的边点割断片由引理1 知，如果 x y e u ( 6 ) ，则g 中存在分离分解( x y ，s ；a ，b ) 使x a ，y b 设( v ，s7 ；彳7 ，) 是g 的另一个分离分解，令 局= 口7ns ) u 岱7os ) u ( s 7 o4 ) ， x 2 = 岱7n 彳) o ( s 7 ns ) o ( b 7os ) ， x 3 = ( b 7ns ) op 7 o s ) u ( s 7 n b ) ， x 4 = ( s 7 n b ) u ( s 7ns ) u ( t 1 7n5 ) 11 山东大学硕士学位论文 引理3 2 t 2 l 设g 6 ，( x y , s ) 是g 的一个分离对，则g 中每条连接s 与 工，y j 的边 都是可去边 设( x y ，s ；a ，b ) 是g 的分离分解，x a ，y b 以及s = a ，b 1 如果阻i = 2 ，设 a = x ，z ，因g 是3 连通图，所以有z x ，z a ，z b e ( g ) ，期e ( g ) 或者x b e ( g ) 可 设翮e ( g ) 这时，如果x b 彗丘( g ) ，则称彳足l 型2 边一点割原子；如果x b e ( g ) ， 则称彳是2 型2 边一点割原子因而，如果彳是基数为2 的边点割断片，则彳必 是1 型或2 型2 边点割原子 由引理3 2 可推出： 引理3 3 【1 3 】设( x y s ；a ，b ) 是g 的分离分解，a 是l 型2 边点割原子，a = x ，z ，s = l a ，6 ，x z ，z 口，z b ，x a e ( g ) ，x b 萑e ( g ) ，贝9x a ，z i t i e i e ( g ) ，z b e u ( g ) 引理3 4 t b 】设( x y , s ；a ，b ) 是g 的分离分解，彳是2 型2 边点割n - - y - ，a = 工，z l ，s = 口，6 ，x z ，z a ，z b ，x a ，x b e ( g ) ，秀b 么 ( 1 ) x a ，x b ，澎e r ( g ) ( 2 ) 如果z c i e t v ( g ) ，则比( 6 ) = 3 ；如果z b 局，( g ) ，则如( 口) = 3 在文献 1 4 中引入了半轮和极大半轮的概念，定义如下： 定义3 2 t h l 令是3 连通图g 的一个子图，h 印= 口；x l ，x 2 ，x t + 3 ，( 1 4 ) = x l x 2 ，x 2 x 3 ，x i + 2 x l + 3 ，a x 2 ，a x 3 ，a x l + 2 ，其中，1 如果下述条件( 1 ) 和( 2 ) 成立， 则称h 足g 的一个，- 半轮： ( 1 ) x i x i + l e u ( g ) ，f = 1 ，2 ，+ 2 ( 2 ) d c