（运筹学与控制论专业论文）3连通图的某些子图上的可去边.pdf

山东大学硕士学位论文 3 连通图的某些子图上的可去边 蔡王月 ( 山东大学数学学院，运筹学与控制论，济南，山东2 5 0 1 0 0 ) 中文摘要 图的连通性是图最基本的性质之一，是图论中重要的研究课 题。连通图与网络模型和组合优化联系密切，使它具备很强的应用 背景随着计算机与网络的迅速发展，这一联系日益密切，使连通 图拥有了重要的理论价值和应用价值。探讨连通图的结构特征，寻 求连通图的构造方法一直是图论研究的前沿课题之一随着数学归 纳法在图论中的广泛应用，图的“约简”日益受到重视它是指在保 持图的某种性质的前提下使图的阶数或边数减少的一系列运算的综 合图的收缩边和可去边就是在这种背景下产生的 本文主要研究连通图中可去边和可收缩边的性质，以及它们 在3 连通图中的分布情况如无特别说明，文中的图g 均为简单图。 下面简单介绍一下本文的主要结果 首先我们给出可去边与不可去边的定义定义如下： 对于3 连通图中的一条边e = x y 进行如下运算： ( 1 ) 从图g 中删除边e = x y ，得到g e ( 2 ) 如果存在一点, x ，y ，使得z ，在g - e 中的邻域g p ( 功= w ，v ，则用边删代替g e 中的路m 脚 ( 3 ) 经过( 1 ) ( 2 ) 运算所得的图g ，如果有重边，则删除g 7 的重 边，使g 7 成为简单图 用g e e 表示g 经过( 1 ) ( 2 ) ( 3 ) 运算所得到的图。如果g e e 是3 连通图，则称e 是g 的可去边，或称e 可去，否则称e 是g 的不可 去边或称e 不可去。用e r ( g ) 表示g 的可去边集，e r ( g ) 表示g 的 山东大学硕士学位论文 可去边数，e u ( g ) ，e n ( g ) 分别表示g 的不可去边集和不可去边数。 对于3 连通图中圈上的可去边的分布，本文对已有的部分研究 成果进行了改进，得出了： 结论1g 是3 连通图，c 是g 中一个6 圈。如果c 上至多存在一 组3 个连续3 度顶点，则ie ( c ) ne r ( g ) i 1 结论2g 是3 连通图，u ( g ) 6 ，c 押是g 中一个n 圈。如果g 上至 多存在一组3 个连续3 度顶点，则le ( g ) ne r ( g ) i 1 对于3 连通图中生成树外可去边的分布，本文通过对3 正则图 的研究，得出了： 结论3g 是一个3 连通图，抄( g ) 6 ，如果g 上不存在2 个连续3 度顶点，则g 的生成树丁外至少存在2 条可去边 关键词：连通图；可去边；可收缩边。 h 山东大学硕士学位论文 r e m o v a b l ee d g e si ns o m es p e c i a ls u b g r a p ho f3 - c o n n e c t e dg r a p h s c a iy u e ( 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 1 0 0 ，p r c h i n a ) a b s t r a c t t h ec o n n e c t i v i t yo fg r a p h si so n eo ft h em o s ti m p o r t a n tp r o p e r t i e so fg 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 l a 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 to fc o m p u t e r sa n di n t e m e t ，t h i sc o n n e c t i o ni sm o r ec l o s e rt h a ne v e rb e f o r e ， w h i c hm a k e sc o n n e c t e dg r a p h sv e r yi m p o r t a n ti nb 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 d i s c u s s i n gt h ec o n s t r u c t i o no fc o n n e c t e dg r a p h si sac u t t i n ge d g et o p i ci ng r a p ht h e o r y w i t hi n d u c t i o n w i d e l yu s e d ，o p e r a t i o n si ng r a p h sw h i c ha r ea s e r i e so fa l g o r i t h m st h a t r e d u c et h en u m b e ro fv e r t i c e so re d g e si nag r a p hw i t hk e e p i n gs o m e p 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 ee d g e s a n dc 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 u so nt h ep r o p e r t i e so f r e m o v a b l ee d g e sa n dc o n t r a c t i b l ee d g e si n3 - c o n n e c t e dg r a p h s ，a n dt h e i rd i s t r i b u t i o n s i nt h i s p a p e r , gi sas i m p l eg r a p h t h ef o l l o w i n ga r et h em a i nr e s u l t so ft h i s p a p e r f i r s t ，w ew i l lg i v ea d 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 e e n d v e r t i c e so feh a v ed e g r e e2i ng - e ，t h e ns u p p r e s s i 山东大学硕士学位论文 t 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 hi sd e n o t e db ygee f o ra3 - c o n n e c t e d g r a hg ，i fg eei ss t i l l3 - c o n n e c t e d ，t h e nt h ee 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 e e 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 fgi sd e n o t e db ye n ( g ) f o rr 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 ，w ew i l lg i v es o m e r e s u l t s a sf o l i o w s ： c o n c l u s i o n1gi sa3 - c o n n e c t e dg r a p h ，ci sa6 - c y c l ei ng i ft h e r e e x i s t sa tm o s to n es e to f3v e r t i c e so fd e g r e e3 ，ie ( c ) ne r ( g ) i 1 c o n c l u s i o n2gi sa3 - c o n n e c t e dg r a p h ，t ，( g ) 6 ，gi san - c y c l ei n g i ft h e r ee x i s t sa tm o s to n es e to f3v e r t i c e so fd e g r e e3 ，ie ( c ，1 ) n e r ( g ) i 1 f o rr e m o v a b l ee d g e so u t s i d eas p a n n i n gt r e ei n3 - c o n n e c t e d g r a p h s ，w eg i v eo n er e s u l tb a s e do nt h er e s e a r c hi n3 - r e g u l a rg r a p h a sf o l l o w s ： c o n c l u s i o n 3gi sa3 - c o n n e c t e dg r a p h ，v ( a ) 6 i ft h e r ed o s e n o t e x i s tc o n t i n u o u s2v e r t i c e so fd e g r e e3 ，t h e r ea r ea tl e a s t2r e m o v a b l e e d g e so u t s i d eas p a n n i n gt r e et i ng 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 山东大学硕士学位论文 h g ) igl e ( g ) u ( g ) s ( g ) a ( g ) d g ( v ) g s e ( g t s ) g s g 一， e u ( g ) e r ( g ) e c ( g ) ( x y ，s ；a ，b ) g ( 力 符号说明 g 的顶点集合 图g 的阶 g 的边集合 g 的顶点数( 阶数) g 的边数 g 的最小度 1 ，在g 中的度 s 导出的g 的子图 s 导出子图g s 】的边集合 h g ) s 的导出子图 以g ) m 的导出子图 g 中不可去边的集合 g 中可去边的集合 g 中可收缩边的集合 与砂对应的分离组 x 在g 中的邻域 v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：翻 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：壅l 导师签名j 奎宙墨 e t期：蛳。形 山东大学硕士学位论文 第一章引言 本章首先对3 连通图中可去边与可收缩边研究的历史背景和进 展状况进行一下简单的介绍。接着，我们会列出一些在本文中要用 到的图论术语及其定义，未说明的会在其它章节中必要时再给与阐 述。最后，简单介绍一下本文的主要结果。 1 1 研究背景 图的连通性理论是图论最重要的组成部分之一，它的任何实质 性的研究进展都会对图论的发展产生重大的推动作用。因而，它一 直是图论与组合数学界的学者重点关注的对象，w b l f 奖得主l o v f i s z 也曾致力于该理论的研究。随着计算机与网络的迅速发展，连通图 与网络模型和组合优化的联系日益密切，使它拥有重要的理论价值 和应用价值 讨论连通图的结构特征，寻求连通图的构造方法一直是图论研 究的前沿课题之一随着应用领域的不断拓展，对它们的研究已成 为近二十年来图论研究的热点在各类连通图递归的构造研究中，为 了使任意连通图都可以由一些简单的连通图重复某些运算而得，最 常用的方法就是引入一些保持图的连通性的运算对本论文即将讨 论的连通图中可去边和可收缩边的研究就是在这种背景下产生的。 早在1 9 6 1 年t u t t e 给出3 连通图的结构特征时，其实就是利用了3 连通图的可收缩边和可去边的存在性 连通图中的可去边与可收缩边不仅是研究连通图构造的有力工 具，在使用归纳法证明连通图的一些性质中也起到了重要的作用。例 如，当k 连通图去掉一条边并做某些变形之后，若得到的图依然是k 山东大学硕士学位论文 连通图，由于新得到的图的边或顶点数比原图少，如果它还保持图 的某种给定性质( 比如图的连通性) ，则可将对复杂图的某种特性的 研究递归的转化为对较简单的图的相应性质的研究。1 9 6 1 年t u t t e 给出了阶至少为5 的3 连通图都包含可收缩边的结果。t h o m a s s e n 在1 9 8 1 年利用这一结果使用归纳法简单的证明了关于平面图的三 个著名的定理，即k u r a t o w s k i 定理、f a r y 定理和t u t t e 定理。而在 此之前，上述三个定理的证明过程都非常的繁琐。 目前，连通图中可去边与可收缩边的存在性及其分布情况已经 成为人们十分关注的课题。本论文也将以连通图中的可去边的性质 以及它们在特定子图上的分布为主要研究对象。下面，我们来分别 介绍连通图中的可去边和可收缩边的研究进展以及部分研究成果。 先来看对连通图中可收缩边的研究。如无特别说明，下文中 的g 均为简单图。 定义1 1 【2 l j 设g 是k 连通图，砂是g 的一条边，如果在g 中将x 与y 收缩为一个顶点所得到的图仍然是k 连通的，则称砂是g 的 可收缩边。 定义1 2 用既表示阶为刀的轮，即圈g 一1 和它外面一点的联 人们在最初的研究中主要是利用可收缩边和可去边来揭示3 连 通图的构造t u l l e 在1 9 6 1 年给出： 定理1 1 【2 1 1 每一个3 连通图可以通过对一个轮进行一系列的边的 增加和适当的分解而得到 n e g a m i 通过这一定理又得出了下面结论： 定理1 21 1 0 】日是一个不同构于轮的3 连通图那么一个图g 是3 连通的且有一个可以被收缩到舒的子图当且仅当g 可以通过对日 进行一系列的边的增加和适当的分解而得到 随后人们将注意力转向了对可去边和可收缩边的研究，下面我 们先介绍3 连通图中可收缩边的相关结论可收缩边在3 连通图中 2 山东大学硕士学位论文 的研究主要有以下两个方向： ( 1 ) 3 连通图中可收缩边的边数。 首先，t u t t e 在1 9 6 1 年给出了3 连通图中可收缩边的存在性。 定理1 31 2 l l 每一个不同构于肠的3 连通图都包含一条可收缩边。 紧接着，人们自然会考虑3 连通图中到底有多少可收缩边。设x 是g 中的一个3 度顶点，在g 中用三个顶点x l ，娩，x 3 替代x ，这三 个顶点互相各有一条边相连且通过三条新的独立的边与g ( 曲相连， 构成的新图记为g + g + 称为从g 中通过对x 作一个一替代而获 得。我们称一个图为- 图如果它可以从一个3 连通3 正则图获得或 者从一个边重数为3 的多重图施中通过对每一个顶点做一个一替 代而获得 a n d o 在1 9 8 7 年得出： 定理1 4 【2 】每一个不同构于k 4 的3 连通图g 至少包含1 q ，l 条可收 缩边。这个下界只可以从- 图获得 定理1 4 给出了在特定条件下的一个下界，m c c u a i g 在1 9 9 0 年完善了这一结论 定理1 5 【9 】令八动是满足使每一个阶数为k 的3 连通图有至少八助 条可收缩边的最大整数。那么，对于k 5 f k 2 ， i fk - o m o d 6 ， 八p = k 2 + 1 ， i fk 三2 ，4 m o d 6 ， ik 2 + 3 2 ， i fk 三l ，3 ，5 m o d 6 这里，我们还要提一下【9 】中的另一个结论。对一个整数k 和 一个图g ，记曝膏( g ) = 协以g ) ：d c ( 曲纠 定理1 61 7 1 每一个不同构于k 4 的最小3 连通图包含至少三( i 以g ) l + 3i 如4 ( g ) i ) 条可收缩边 另一方面，对不可收缩边边数的估计也是研究可收缩边边数的 一条途径。 3 山东大学硕士学位论文 e g a w a 在1 9 9 7 年给出： 定理1 71 6 j 6g 是一个3 连通图且不同构于k 4 ，则g 包含至多3 igi 一【；( 圻河兀习了万一5 ) j 条不可收缩边。这个结论适用于无限图。 ( 2 ) 3 连通图中可收缩边的分布。 有几种途径研究可收缩边的分布： 一是依照可收缩边的边数或者将可收缩边限制在图的特定的子 结构中来考虑，从而找到可收缩边的特定分布以及那些允许这种分 布的3 连通图和它们有趣的性质 s a t i o 在1 9 9 0 年给出： 定理1 7 【1 5 】令g 是一个3 连通图。如果g 中存在一个包含每条可 收缩边的关联顶点的圈，那么g 是一个h a m i l t o n 图 一个k 一连通图g 中的k 可收缩边是指将这条边的两个关联 顶点收缩为一个顶点后所得到图仍然是k - 连通的。我们定义尾( g ) 为g 中肛可收缩边的集合 定理1 8 【1 1 ，1 5 】令g 是一个3 连通图。假设e 3 ( g ) 能被至多两个顶 点覆盖，那么igi 5 二是去研究3 连通图某些子分类和寻找这些子分类中可收缩边 或不可收缩边导出的子图的性质 t h o m a s s e n 在1 9 8 1 年给出： 定理1 9 【2 0 1 每一个无三边形3 连通图g 包含一个圈c 使得e ( c ) e 3 ( g ) a l d r e d 在1 9 9 2 年用另一种3 连通图的子结构研究可收缩边在 最大匹配上的分布： 定理1 1 0f l l 不同构于肠的3 连通图的每一个最大匹配上包含一 条可收缩边 下面我们来看一下对连通图中可去边的研究。 关于可去边的研究成果，最早由b a m e t t e 和g r u n b a n m 【3 给 4 山东大学硕士学位论文 出。他们得到了一个类似可收缩边的结果，证明了每个阶大于4 的3 连通图都有可去边，并给出了3 连通图的一个递归构造的方 法。d a w e s 【5 利用这个结果给出了与t u t t e 1 6 不同的极小3 连通 图的递归构造方法 对于3 连通图中可去边的数目与分布，苏健基得到了下面几个 定理。 定理1 1 1 ( 引理2 3 ) 【1 7 】设g 是阶大于5 的3 连通图，并且g 不是 轮，c 是g 中的一个圈。则 ( 1 ) 如果c 仅通过一个极大半轮，则c 上至少有一条可去边。 ( 2 ) 如果c 不通过任何极大半轮，则c 上至少有两条可去边。 定理1 1 2f 1 6 l 每个阶至少为5 的3 连通图，除与w 6 外，至少 有r ( 3 i g l + 1 8 ) 7 1 条可去边。 其他关于连通图中可去边的研究可参考文献【1 2 ，1 3 ，1 4 ，1 9 ，2 3 】 等 1 2 基本定义与符号 在本节，我们主要介绍几个基本概念和在本文中使用的符号，其 它未定义的参见 4 】 个图g 是指一个有序三元组( 以g ) ，f 4 g ) ，矽g ) ，其中坎g ) 是 非空的顶点集，e ( g ) 是不与h g ) 相交的边集，而沙g 是关联函数， 它使g 的每条边对应子g 的无序顶点对( 7 6 必相异) 若e 是一条边， 而”和1 ，是使得o o ( e ) = “v 的顶点，则称e 连接 和1 ，顶点u 和1 ， 称为e 的端点一条边的端点称为与这条边关联，反之亦然与同一 条边关联的两个顶点称为相邻的，与同一个顶点关联的两条边也称 为相邻的g ( 材) 代表由顶点z ，在图g 中所有的邻点所组成的“的 邻域，简记为( 甜) 令】，坎g ) ，记 k ( d = u m r n o o , ) 】，。 5 山东大学硕士学位论文 端点重合为一点的边称为环。一个图称为有限图，如果它的顶 点集和边集都有限。一个图称为简单图，如果它既没有环也没有两 条边连接同一对顶点。每一对不同的顶点都有一条边相连的简单图 称为完全图。n 个顶点的完全图记为图g 的顶点数和边数分 别用符号u ( g ) 和e ( g ) 表示。y ( g ) 中元素的个数称为g 的阶，记 为igi ，则有igi - u ( g ) 。 两个图g 和日是恒等的( 记为g = 印，如果以g ) = 以功，e ( g ) = e ( 忉和沙g = 0 i - 1 。两个图g 和日称为同构的( 记为g 兰忉，如 果存在两个一一映射0 or r ( g ) _ 巩和矽：e ( g ) - e ( ，使 得砂g ( p ) = v 当且仅当l 沙( ( e ) ) = p ( “) 臼( v ) 称图日是g 的子图( 记为h g ) ，如果以柳s 坎g ) ，五( 邱s e ( g ) ，并且沙是c g 在e ( 忉上的限制。当日g ，但h g 时， 则记为hcg ，并且日称为g 的真子图。若日是c 的子图。则g 称为日的母图。g 的生成子图( 或生成母图) 是指满足以切= 以g ) 的子图( 或母图) 日。从图g 中删去所有的环，并使每一对相邻顶点 只留下一条连接杆，即可得到g 的一个简单生成子图，称为g 的基 础简单图。 假设是矿的一个非空子集以为顶点集，以两端点均 在中的边的全体为边集所组成的子图，称为g 的由导出的子 图，记为g 】，g w 】称为g 的导出子图导出子图a v 】记 为g 一，它是从g 中删除中的顶点以及与这些顶点相关联的 边所得到的子图若矿= m ，则把g 一 y 简记为g v 假设e 7 是e 的非空子集。以e 7 为边集，以e 7 中边的端点全体 为顶点集所组成的子图称为g 由e 7 导出的子图，记为g e ，】，g e 7 】 称为g 的边导出子图。边集为e k e 7 的g 的生成子图简记为g e 7 ， 它是从g 中删除e 7 中的边所得到的子图类似地，在g 边上添加边 集e 7 的所有边得到的图记为g + e 7 若e 7 = e l ，则用g e 和g + e 6 山东大学硕士学位论文 来代替g 一e 和g + p 。 设g l 和g 2 是g 的子图。若g l 和g 2 没有公共顶点，则称它们 是不相交的；若g l 和g 2 没有公共边，则称它们边不重的。g l 和g 2 的并图g 1ug 2 是指g 的一个子图，其顶点集为h g l ) uv ( g 2 ) ，其 边集为e ( g i ) ue ( g 2 ) 。如果g l 和g 2 是不相交的，有时就记为其并 图g i + g 2 。 g 的顶点1 ，的度( 或次) 如( v ) 是指g 中与1 ，关联的边的数目， 每个环算作两条边。用6 ( g ) 和a ( g ) 分别表示g 的顶点的最小度和 最大度。称图g 是k 正则的如果对所有1 ，v ，有以v ) = k 。 g 的一条途径( 或通道) 是指一个有限非空序列w = v o e lv le 2 v 2 一e k v k ，它的项交替地为顶点和边，使得对1 f k ，e i 的端点是睢l 和v i 。称形是从到的一条途径，或一条( v o ，魄) 途径顶点 和魄分别称为矽的起点和终点，而v l 屹，l 称为它的内部顶 点。整数k 称为的长若途径缈的边e l ，e 2 ，魄互不相同，则缈 称为迹，这时形的长恰好是( 叨。又若途径形的顶点，l ， 也互不相同，则形称为路g 的两个顶点甜和1 ，称为连通的，如果 在g 中存在( z ，v ) 路。如果g 的任意两个顶点之间都有连接它们的 路，则称图g 是连通的不连通的图的极大子图称为此图的连通分 支，图的连通分支的数目用山( g ) 表示 称一条途径是闭的，如果它有正的长且起点和终点相同若一 条闭迹的起点和内部顶点互不相同，则它称为圈长为k 的圈称为k 圈，记作q 不包含圈的图称为无圈图，连通的无圈图称为树每 个连通图都包含生成树 若y 的子集使得g 一不连通，则称为g 的顶点割k 顶点割是指有k 个元素的顶点割。若g 至少有一对相异的不相邻顶 点，则g 所具有的k 顶点割中最小的毛称为g 的连通度，记为足( g ) ； 否则定义k ( g ) 为t ，一1 。若k ( 回k ，则称g 为七连通的。 7 山东大学硕士学位论文 1 3 本文的主要结果 本文主要研究3 连通图中可去边的性质以及它在特定子图上的 分布情况，有以下几点创新： ( 1 ) 对已有的3 连通图中可去边在圈上的分布结论进行了改进， 给出了在至多存在一组3 个连续3 度顶点的情况下可去边的性质。 ( 2 ) 对已有的3 连通图中可去边在生成树外的分布结论进行了 引申，给出了在不存在2 个连续3 度顶点的情况下可去边的性质。 下面简单介绍一下本文在内容上的组织安排。 全文共分三章，第一章简单介绍了对连通图中可去边与可收缩 边的研究的历史背景、进展状况、取得的相关结果以及本文的一些 研究成果，并简单介绍了一下文中需要的图论基本概念和符号 第二章主要研究3 连通图中可去边在圈上的分布情况，得到以 下结论： 定理2 3g 是3 连通图，c 是g 中一个6 圈。如果c 上至多存在一 组3 个连续3 度顶点，则ie ( c ) ne r ( g ) i 1 定理2 4g 是3 连通图，t ，( g ) 6 ，g 是g 中一个刀圈如果g 上 至多存在一组3 个连续3 度顶点，则ie ( g ) ne r ( g ) i 1 第三章主要讨论3 连通图中可去边在生成树外的分布状况。我 们对已有的结论进行了引申，得出了： 定理3 2g 是一个3 连通图，抄( g ) 6 ，如果g 上不存在2 个连续3 度顶点，则g 的生成树丁外至少存在2 条可去边 8 山东大学硕士学位论文 第二章3 连通图中圈上的可去边 在这一章中我们主要讨论3 连通图中圈上的可去边的分布。我 们利用极大半轮等工具，将欧见平等在3 连通图中圈上的可去边的 分布的部分结论进行了改进，给出了在至多存在一组3 个连续3 度 顶点的条件下可去边的分布。 2 1 基本定义和已知结果 首先，我们介绍一下本节中我们需要用到的定义 定义2 11 7 j 对于3 连通图中的一条边e = x y 进行如下运算： ( 1 ) 从图g 中删除边e = x y ，得到g e ( 2 ) 如果存在一点u x ，y ，使得甜在g - e 中的邻域n c e ( 甜) - - w ，1 ， ，则用边w 代替g e 中的路w u v ( 3 ) 经过( 1 ) ( 2 ) 运算所得的图g 7 如果有重边，则删除g 7 的重 边，使之成为简单图 用g e e 表示g 经过( 1 ) ( 2 ) ( 3 ) 运算所得到的图如果g e e 是3 连通图，则称e 是g 的可去边，或称e 可去，否则称e 是g 的不可 去边或称e 不可去用e r ( g ) 表示g 的可去边集，e r ( g ) 表示g 的 可去边数，如( g ) ，e n ( g ) 分别表示g 的不可去边集和不可去边数 定义2 2 【1 6 j 令h 是3 可连通图g 的一个子图，以忉= a ，x l ，x 2 ， ，x i + 3 ，e ( 卸= x l x 2 ，x 2 x 3 ，x l + 2 x l + 3 ，a x 2 ，a x 3 ，a x l + 2 ，其中j 1 如果下列条件( 1 ) ( 2 ) 成立，则称h 是g 的一个卜半轮，记作h - - s 形( a ；x 1 ，娩，x i + 3 ) s ( 1 ) x i x i + 1 如( g ) ，f = 1 ，2 ，+ 2 ( 2 ) 如( 力4 ，如( 置) = 3 ，f = 2 ，3 ，+ 2 9 山东大学硕士学位论文 定义2 3 【1 6 l 如果下列条件( 3 ) 也成立，则称是g 的极大，- 半 轮，记作h = m w ( a ；x l ，x 2 ，x l + 3 ) ： ( 3 ) n g ( x 1 ) a ，x 2 ，“ ，n o ( x l + 3 ) o ，x “2 ，1 ， ，对于任意 ，y 以g ) 。 此时称娩，x 3 ，x i + 2 是极大半轮日的内点；a 是h 的中心；z l ，x “3 是h 的端点。 定义2 41 1 6 】如果3 连通图g 的圈c 经过极大半轮日的至少2 个内 点，则称c 经过，类似可定义路经过h 。易见，如果圈c 经过日， 则下列4 种情况有且只有一种出现： ( 1 ) cch 。 ( 2 ) 存在自然数f ，z2 f j z + 2 ，使得路x l x 2 x 3 x i a x x l + 2 x 1 + 3cc ( 3 ) 存在自然数f ，3 f | + 2 ，使得路x l x 2 x 3 ，x i ac c ，而边x i + 2 x l + 3 隹e ( c ) ，或者存在自然数工2 j ，+ 1 ，使得 路x l + 3 x 1 + 2 x j acc ，而边x l x 2 譬e ( c ) 。 ( 4 ) 路x l x 2 x i + 3cc 其次，对于3 连通图中的可去边和不可去边的研究，苏健基取 得了很大的进展，得到了下列结果： 引理2 1 【1 6 】3 连通图的任意两个不同极大半轮无公共内点 引理2 21 1 8 1 设c 是3 连通图g 的一个圈，u ( g ) 6 ，那么： ( 1 ) 若lcl - 3 或4 ，则：le r ( g ) ne ( c ) i 2 ( 2 ) 若ic | - 5 且g 不同构于甄，则：fe r ( g ) ne ( c ) i 1 引理2 3 【1 8 】若c 是非轮3 连通图g 的一个圈，v ( g ) 6 ，那么： ( 1 ) 如果c 只经过一个极大半轮，则l 五( c ) n 碌( g ) l 1 ( 2 ) 如果c 不经过任何极大半轮，则ie ( c ) ne g ( g ) l 2 引理2 41 1 6 】设h - - - m w ( a ；x 1 ，x l + 3 ) 是3 连通图g 的极大半轮， 其中，2 ，则： 1 0 山东大学硕士学位论文 ( 1 ) e r ( gea x 2 ) e r ( g ) 。 ( 2 ) x i x 2 垡e r ( ge a x 2 ) 。 在接下来的一节里，我们将对欧见平关于3 连通图中可去边在 圈上的分布的部分研究成果进行改进与推广 2 23 连通图中圈上的可去边 对于3 连通图中圈上的可去边，欧见平在 1 2 】中有以下结果： 定理2 。l1 1 2 j 设c 是3 连通图g 的一个5 圈，如果c 上无3 个连续 的3 度顶点，那么le ( c ) ne r ( g ) l 2 定理2 2 【1 2 j 设c 刀是阶至少为6 的3 连通图g 上的一个n 圈，如 果c 玎上不存在3 个连续3 度顶点，则le ( g ) ne r ( g ) i 2 。 对于上述结果。我们做了进一步改进，得出以下结论： 定理2 3g 是3 连通图，c 是g 中一个6 圈。如果c 上至多存在一 组3 个连续3 度顶点，则ie ( c ) ne r ( g ) i 1 证明：用反证法。假设ie ( c ) ne r ( g ) i = 0 。 由于c 是g 中一个6 圈，c 上至多存在一组3 个连续3 度顶 点，所以g 不同构于轮。根据引理2 3 知，c 至少经过两个极大半轮 不妨设为风，耽，令凰- - m w ( a ；x i ，x 厂+ 3 ) ，飓= m w ( b ；y l ， t ，y + 3 ) ，j r , z 1 根据假设，c 上不存在可去边，所以c 只能以种方式经过凰， 飓，即路x l x 2 x f + 3cc ，路y l y 2 肌3cc 由于c 上至多存在 一组3 个连续3 度顶点，所以有厂，均小于等于2 ，且，不能同时 为2 。因为有工，l ，因此共存在以下两种情况： ( 1 ) 厂= 1 ，i = 1 即h 1 = m w ( a ；x 1 ，x 2 ，x 3 ，x 4 ) ，4 2 = m w ( b ；y l ，y 2 ，y 3 ，y 4 ) 由于 路x l x 2 x 3 x 4cc ，路y l y 2 y 3 y 4cc ，c 是一个6 圈，且c 上至多存 山东大学硕七学位论文 在一组3 个连续3 度顶点，所以l ，总的外点分别相互重合，不 妨令u = x i = y l ，y = x 4 = y 4 。对于外点u ，若它们中任一个的 度数为3 ，则会存在不止一组3 个连续3 度顶点，与题设矛盾，所 以d g ( u ) 4 ，如( v ) 4 。 由于c 是g 中一个6 圈，u ( g ) 6 ，且c 上不存在3 个连续3 度顶点，根据定理2 2 ，有le ( c ) ne r ( g ) l 2 ，与假设矛盾。 ( 2 ) 不失一般性，令f = l ，= 2 ，即h i = m w ( a ；x l ，x 2 ，x 3 ，x 4 ) ， h 2 = m w ( b ；y l ，y 2 ，y 3 ，y 4 ，y 5 ) 。 根据引理2 1 ，3 连通图的任意两个不同极大半轮无公共内点， 且c 是一个6 圈，c 中至多存在一组3 个连续3 度顶点。显然这种 情况不存在，矛盾。定理证毕。 定理2 4g 是3 连通图，u ( g ) 6 ，g 是g 中一个胛圈。如果g 上 至多存在一组3 个连续3 度顶点，则je ( g ) ne r ( g ) j 1 证明：对门作归纳证明。根据引理2 2 ，定理2 3 知，当3 船6 时， 定理成立假设6 n k 一1 时定理也成立，当n = k 7 时，用 反证法，假设ie ( c 盯) ne r ( g ) i _ 0 。 由于g 是g 中一个n 圈，g 上至多存在一组3 个连续3 度 顶点，所以g 不同构于轮因为有u ( g ) 6 ，根据引理2 3 知，g 至少经过两个极大半轮不妨设为凰，飓，令h i = m w ( a ；x i ，一 ，x + 3 ) ，仍= m w ( b ；y l ，y + 3 ) ，j 1 根据假设，g 上不存在可去边，所以g 只能以一种方式经 过凰，凰，即路x i x 2 x f + 3cg ，路y l y z 肌3cg 由于g 上 至多存在一组3 个连续3 度顶点，所以有，均小于等于2 ，且厂， 不能同时为2 因为有工，1 ，因此共存在以下两种情况： ( 1 ) 厂= l ，= 1 即日= m w ( a ；x 1 ，x z ，x 3 ，x 4 ) ，4 2 = m w ( b ；y l ，y z ，y 3 ，y 4 ) 。令g 1 = g e a x 2 ，c ：= x l x 3u ( c 一娩) ，显然a 是g 1 中的个刀一1 圈，且c ： 1 2 山东大学硕士学位论文 上至多有一组3 个连续3 度顶点。由于igi - k 7 ，所以u ( g ) 7 ， 即有u ( g 1 ) 6 。根据归纳假设碟上至少有l 条g 1 的可去边。 根据引理2 4 知这条可去边也是g 的可去边。由于x i x 3 e ( c ：) ， 但x l x 3ge ( g ) ，所以x l x 3 不是这条可去边，故这条可去边是g 上 的边，与假设矛盾。 ( 2 ) 不失一般性，令f = 1 ，= 2 ，即h i - - m w ( a ；x i ，x 2 ，x 3 ，x 4 ) ， 2 = m w ( b ；y t ，y 2 ，y 3 ，y 4 ，y 5 ) 。 令g 2 - - geb y 3 ，暖- - y 2 y 4u ( c 玎一y 3 ) 。显然砩是g 2 中 的一个n 一1 圈，由于g 上至多存在一组3 个连续3 度顶点，所 以c ：上不存在3 个连续3 度顶点。由于u ( g ) 6 ，根据定理2 2 ， 有ie ( 砩) u ( g 2 ) l 2 。即砩上至少有2 条g 2 中的可去边。 则c ：一y 2 y 4 上至少有1 条g 中的可去边。所以c n 上至少有l 条g 中的可去边，与假设矛盾。定理证毕。 1 3 山东大学硕士学位论文 第三章3 连通图中生成树外的可去边 本章主要研究3 连通图中生成树外的可去边的分布及性质。我 们利用边点割原子、断片、分离组等工具将吴吉昌等的关于3 连通3 正则图中生成树外的可去边的分布的结果进行了推广，得出了在不 存在两个连续3 度顶点情况下的可去边的分布。 3 1 基本定义和已知结果 首先，我们介绍一下本节中需要用到的几个概念。 定义3 1 【2 2 l 设e e ( g ) ，s 是以g ) 的一个2 阶子集，如果g - e - s 恰有2 个分支彳，b ，并且ial 2 ，i 曰i 2 ，则称( e ，s ) ，( p ，s ；a ，b ) 分别为e 所对应的分离对和分离组。 定义3 2 【2 2 l 令a ，bcy ( g ) ，使得a 1 2 j b ，anb = 1 2 i ，我们定 义口，例= x y e ( g ) lx a ，y b j 。 定义3 3 【2 2 】令e oce n ( g ) ，使得e o 1 2 i 。( x y ，s ；a ，b ) 是g 的一 个分离组满足x a ，y b 如果x y e o ，那么4 和b 叫做巴一 边点割断片一个己一边- 点一割断片被叫做巴- 边一点一割端 片当且仅当它不真包含任何其它g 中的既一边一点- 割断片如果 一个b 边一点一割断片彳只包含2 个元素，即lai - 2 ，那么么叫 做既一边点一割原子 其次，我们介绍一些关于3 连通图中可去边的已知的结果，并 将被用于我们下一章节的主要结论的证明 h o l t o nd a 在1 9 9 0 年发表的文章中得到以下结果： 引理3 1 【7 lg 是阶至少为6 的3 连通图，x y e ( g ) x y e n ( g ) 当 且仅当存在一个sc 以g x y ) ，使得isl _ 2 ，g 一砂一s 恰有两个 1 4 山东大学硕士学位论文 分支a 和b 且满足x a ，y b ，ial 2 ，ibl 2 。 引理3 21 7 】g 是阶至少为6 的3 连通图，( x y ，s ) 是g 的一个分离 对那么每条连接s 和 x ，y 的边是可去边。 ( x y ，s ；a ，b ) 是g 中的一个分离组，满足x d ，y b ，s = a ，6 l ，iai - - 2 ，令a = 【x ，z 因为g 是一个3 连通图，我们 有z x ，z a ，z b e ( g ) 。我们说彳是一个1 一边一点一割原子如果x a e ( g ) ，x b 仨e ( g ) ，或者彳是一个2 一边一点一割原子如果x a e ( g ) ，x b e ( g ) 。苏健基得到下面结论： 引理3 3 【1 7 1g 是一个3 连通图，( 砂，s ；彳，曰) 是g 的一个分离组如 果彳是一个1 一边一点一割原子，令a = f x ，z ) ，s = a ，6 l ，x z ，z a ，z b ，x a e ( g ) ，x b 萑e ( g ) 那么x a ，z a 舔( g ) ，z b