（运筹学与控制论专业论文）连通图中的可去边和可收缩边.pdf

山东大学硕士学位论文 连通图中的可去边和可收缩边 集王昔 山东大学教学与系统科学学院 运筹学与控制论 山东济南2 5 0 1 0 0 中文摘要 图的连通性是图的最基本的性质之一 是图论中重要的研究课题 连通图 与网络模型和组合优化联系密切 使它拥有很强的应甩背景 连通图中的可去 边和可收缩边是探讨图的结构 递归的证明图的某些性质的重要工具 对它们 的研究具有重要的理论价值和应用价值 本文选择连通图中的可去边和可收缩 边作为研究对象 就是希望通过努力能够对进 步了解连通图的结构以及找出 其构造方法的研究工作有所帮助 本文主要研究连通图中可去边和可收缩边的 性质以及它们在特定子图上的分布情况 下面简单介绍一下本文的主要结果 对于连通图中的可去边 本文将巳有的4 连通图中可去边在圈上分布的部 分研究成果作了改进 并首次提出了6 连通图中可去边的一些性质 主要绪果 如下 定理2 2 1 0 设g 是4 连通图 c 为g 中任意的圈 若圈g 不与g 的任何阶 为2 的边点割断片相交 则c 上至少有两条可去边 定理2 3 2 设g 是6 连通图 i g i21 1 6 g 7 z y e n g 知 最a b 为其对应的分离分解 其中z a yeb 则f g 旧 e k g 定理2 3 3 设g 是6 连通图 i g i 1 1 g 的边点割原子的阶至少为3 x y 点 g 0 掣 s a b 为其对应的分离分勰 其中z a y 目 则e c s 1 岛 回 对于连通图中的可收缩边 本文将已有的4 连通图中可收绾边在完美匹配 上的分布结果进行了改进 并首次给出了5 连通图中可收缩边在完美匹配上的 分布情况 还得到了 个与6 连通图中可收缩边相关的结论 主要结果如下t i 山东大学硕士学位论文 定理3 2 1 设g 是阶大于7 的4 连通图 m 是g 的 个完美匹配 且m 上 的任意一条边不在三角形上 则m 上至少有两条可收缩边 定理3 3 2 设g 是阶大于9 的5 连通图 m 是g 的 个完美匹配 且m 上 的任意一条边不在三角形上 则盯上至少有两条可收缩边 定理3 3 4 设g 是阶大于1 1 的5 连通图 m 是g 的 个完美匹配 若图g 的任意断片的阶都大于2 则m 上至少有两条可收缩边 定理3 4 2 设g 是阶至少为8 的6 连通图 g 的任意端片的阶不等于2 设z 为g 的任意顶点 若与z 相关联的每一条边都是不可收缩的 则存在 秒 霉 使得d 6 g z n g 国 毋 关键词 连通图 可去边 可收缩边 山东大学硕士学位论文 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 nc o n n e c t e dg r a p h s l i a n gy a q i 胚 s c h o o lo fm a t h s y s s c i s h a n d o n gu n i v e r s i t y s h a n d o n gj i n a n 2 5 0 1 0 0 t b ec o n n e c t i v i t yo fg r a p h si so d eo ft h em o s ti m p o r t a n tp r o p e r t i e so f 擎a p h 8 c o n n e c t e dg r a p h sp l a y sa 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 s b e c a u s eo fi t sd 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 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 y t h es t m c t u r eo fg r a p h sa n dt op r o v e8 0 i n ep r o p e r t i e so fg r a p h sb yi n d u c t i o n t h e ya l ev 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 t h em a i nw o r ko ft h i sp a p e ri so nr 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 n c o n n e c t e dg r a p h si no r d e rt ok n o wm o r ea b o u tt h ec o n s t r u c t i o no fc o n n e c t e d g r a p h s t h i sp a p e rf o c u so nt h ep r o p e r t i e so fc o n t r a c t i b l ee d g e sa n dr e m o v a b l e e d g e si nc 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 si ns o m es p e c i 8 ls u b g r a p h so f c o n n e c t e d 口印h 8 皿地f o l l o w i n ga l et h em a i nr e s u l t 甚o ft h i sp a p e r f o rt h er e m o v a b l ee d g e si nc o n n e c t e dg r a p h s w eg i v es o m er e s u l t 8o i l t h ed i s t r i b u t i o n so fr e m o v a b l ee d g e si nc y c l e sf o r4 c o n n e c t e dg r a p h s a n d f o rt h ef i r s tt i m e w eg i v es o m er e s u l t so nt h ep r o p e r t yo fr e m o v a b l ee d g e si 6 c o n n e c t e dg r a p h s k e yc o n t r i b u t i o n sa l ea sf o l l o w s t h e o r e m j 2 2 1 0 l e tg b ea4 c o n n e c t e dg r a p ha n dcac y c l eo fg i fc d i s j o i n tf r o ma n ye d g e v e r t e x c u tf r a g m e n to fg w i t ht h eo r d e ro f2 t h e nt h e r e a l ea tl e a s tt w or e m o v a b l ee d g e si nc t h e o r e m2 3 2 l e tgb ea6 c o n n e c t e dg r a p hw i t hi g i 1 1a n d6 g 7 f o r 觚e d g e 卸 五k g 矧 只a b i st h ec o r r e s p o n d i n gs e p a r a t i n gg r o u p s u c h t h a t 茁 a 轳 b t h e n e c 旧 e r g 山东大学硕士学位论文 t h e o r e m2 3 3 l e tgb ea6 c o n n e c t e dg r a p hw i t hi g l21 1 t h eo r d e ro f e d g e v e r t e xc u ta t o mi ng i sa tl e a s t3 f o ra ne d g ex y e k g x y 只a b i st h ec o r r e s p o n d i n gs e p a r a t i n gg r o u p s u c ht h a tz a l b t h e ne g i s 匹k g f o rt h ec o n t r a c t i b l ee d g e si nc o n n e c t e dg r a p h s w eg i v ea r e s u l to nt h e d i s t r i b u t i o n so fc o n t r a c t i b l ee d g e si np 蜘m a t c h i n g so f4 c o n n e c t e dg r a p h s 舡df o rt h ef i r s tt i m e w eg i v et h ed i s t r i b u t i o n so fc o n t r a c t i b l ee d g e si np e r f e c t m a t c h i n g so f5 c o n n e c t e dg r a p h s f u r t h e rm o r e ar e s u l to i lt h ep r o p e r t y o f c o n t r a c t i b l ee d g e si n6 c o n n e c t e dg r a p h si so b t a i n e d k e yc o n t r i b u t i o n sa r e 硝 f o l l o w s t h r e m3 2 1 l e tgb ea c o n n e c t e dg r a p hw i t hf g i 7 mh eap e r f e c t m a t c h i n go fg i ft h e r ei sn oe d g e o fmc o n t a i n e di nat r i a n g l eo fg t h e nt h e r e a r ea tl e a s tt w oc o n t r a c t i b l ee d g e si nm t h e o r 哪3 3 2 l e tgb ea5 c o n n e c t e dg r a p hw i t hi g i 9 mb eap e r f e c t m a t c h i n go fg i ft h e r ei sn oe d g e o fmc o n t a i n e di nat r i a n g l eo fg t h e nt h e r e a r ea tl e a s tt w oc o n t r a c t i b l ee d g e si nm t h e o 舱m3 3 4 l e tgb ea c o n n e c t e dg r a p hw i t hi g i 1 1 m b ea p e r f e c t m a t c h i n go fg i ft h eo r d e ro fa n yf r a g m e n to fg i sa tl e a s t3 t h e nt h e r ea r e a tl e a s tt w oc o n t r a c t i b l ee d g e si nm t h 舰3 4 2 l e tgb e86 c o n n e c t e dg r a p hw i t hi g i 8 a n dt h eo r d e r o f a n ye n di ng i sn o te q u a lt o2 f o rav e r t e xz g i ft h e r ei sn oc o n t r a c t i b l e e d g ei n c i d e n tt o t h e r em u s tb ea v e r t e x 暑 n a x s u c ht h a td 3 6a n d g z n g 国 妒h o l d k e yw o r d s c o n n e c t e dg r a p h r e m o v a b l ee d g e s c o n t r a c t i b l ee d g e s i v 山东大学硕士学位论文 符号说明 v a i g i e g 6 c a d g t g 嘲 e g s g s g 一口 点k g e r c a e c a g 的顶点集合 图g 的阶 g 的边集合 g 的最小度 钉在图g 中的度 s 导出的g 的子图 s 导出子图g 旧的边集合 v c a s 的导出子图 y g 的导出子图 g 中不可去边的集合 g 中可去边的集合 g 中可收缩边的集合 z 寥 只a b 与z 鲈对应的分离分解 v 原创性声明 本人郑重声明 所呈交的学位论文 是本人在导师指导下 独立进行研 究工作所取得的成果 除文中已经注明引用的内容外 本论文不包含任何其 他个人或集体已经发表或撰写过的科研成果 对本论文的研究作出重要贡 献的个人和集体 均已在文中以踢确方式标明 本人完全意识到本声明的法 律责任由本人承担 论文作者签名 堡垒虽 日论文作者签名 遂互弦日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留 使用学位论文的规定 同意学校保留 或向国家有关部门或机构送交论文的复印件和电子版 允许论文被查阅和 借阅 本人授权山东大学可以将本学位论文全部或部分内容编入有关数据 库进行检索 可以采用影印 缩印或其他复制手段保存论文和汇编本学位论 文 保密的论文在饵密后应遵守此规定 论文作者签名 曩盛导师签日期 啦 第一章引言 在这一章中我们首先介绍对连通图中可去边与可收缩边研究的历史背景和 进展状况 之后 简单介绍本文的一些主要结果 最后 我们再来介绍一些在 本文中要用到的图论术语及其定义 未说明的图论术语会在其他章节中必要时 再给予阐述 1 1 研究背景 图的连通性理论是图论最重要的组成部分之一 它的任何实质性的研究进 展都会对图论的发展产生重大的推动作用 因而 它一直是图论与组合数学界 的学者重点关注的对象 w o l f 奖得主l o v s z 也曾致力于该理论的研究 2 6 随 着计算机与网络的迅速发展 连通图与网络模垄和组合优化的联系日益密切 使它拥有重要的理论价值和应用价值 探讨连通图的结构特征 寻求连通图的构造方法一直是图论研究的前沿课 题之一 随着应用领域的不断拓展 对它们的研究已成为近二十年来图论研究 的热点 在各类连通图递归的构造研究中 为了使任意连通图都可以由一些简 单的连通图通过重复某些运算而得 最常用的方法就是引入一些保持图的连通 性的运算 对本论文即将讨论的连通图中可去边与可收缩边的研究就是在这种 背景下产生的 早在1 9 6 1 年t u t t e 3 9 给出3 连通图的结构特征时 其实就是 利用了3 连通图的可收缩边和可去边的存在性 连通图中的可去边与可收缩边不仅是研究连通图构造的有力工具 在使 用归纳法证明连通图的一些性质中也起到了重要的作用 例如 当k 连通图 去掉一条边并作某些变形后 若得到的图依然是 连通图 由于新得到的图 的边或顶点数比原图少 如果它还保持图的某种给定性质 比如图的连通性 则可将对复杂图的某种特性的研究递归地转化为对较简单的图的相应性质的 研究 1 9 6 1 年t u t t e 3 9 给出了阶至少为5 的3 连通图都包含可收缩边的结 果 t h o m a s s e n 3 8 1 在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 s g 设g 是k 连通图 铆是g 中一条边 如果在g 中将 与可 收缩为一个顶点所得到的图仍然是k 连通的 则称跏是g 的可收缩边 j c 连通图将可收缩边收缩之后得到比原来更小的连通图 由于我们所考虑 的图都是有限图 经过有限次收缩边之后 最后得到不存在可收缩边的七连通 图 因此 我们在研究 连通图的构造时 最关键的问题之一就是要得到不存 在可收缩边的k 连通图的结构 也即收缩临界七连通圈的结构 所以 对连通 图中可收缩边的研究主要分为以下两个方面 1 对收缩临界七连通图的研究 这方面最早的研究成果由毗t e 3 9 1 在1 9 6 1 年给出 结果如下 定理1 1 2 3 9 j 若g 是3 连通图 i g i 4 则图g 中必含有可收缩边 从这个结论很容易看出 阶大于4 的收缩临界3 连通图是不存在的 对于收缩临界4 连通图的结构的研究 1 9 8 2 年m a r t i o n o v 2 7 证明了如下 定理t 定理1 1 3 e 7 收缩临界4 连通圈g 是4 连通 4 正则的 且每条边恰在一个 三角形上 上述结论说明 收缩临界4 连通图g 或者是c 或者是 边连通立方体 的线图 而 边连通立方体可由 1 4 或j 0 去掉一因子的图通过构造的方法 而得到 对于收缩临界5 连通图的结构的研究 k a a u d o 5 1 等证明了收缩临界5 连 通图不是5 正则的且它所有的边并不都包含在一个平凡割中 还得到了以下结 论l 定理1 1 4 御对任意图日 存在收缩临界5 连通图g 使得日是g 的导出子 图 2 山东大学项士学位论文 由于奄 5 时 收缩临界k 连通图的结构比较复杂 因此 利用收缩边运 算构造k 连通图的问题还没有得到完全解决 e g a w a 1 3 证明了每 个收缩l f 笛界k 连通图有一个基数小于等于 的断 片 于是可得当七 4 5 6 7 时 收缩临界惫连通图的最小度等于七 在这之 后 出现了大量的与收缩临界k 连通图中顶点的度相关的研究 下面是关于这 方面研究的部分成果 定理1 15 皿盯设g 是七连通图 k 7 且砖g 中任意两个距离小于等于2 的顶点z 与玑满足d 0 d 掣 2 譬j 一1 则g 中有可收缩边 定理1 1 6 吲每一个收缩临界7 连通图中有两个7 度顶点 定理1 1 7 p 刀每一个收缩临界7 连通图中有两个距离至多是2 的7 度顶点 2 对k 连通图中可收缩边的分布的研究 k r i 借d l 在文献 2 5 1 中详细介绍了在连通图中可收缩边的分布方面所取得 的成果 并迸 步改进了3 连通图中可收缩边数目的下界 得到了下面的定理t 定理1 1 8 删不同构于凰的3 连通图g 中至少有 i g i i 琏4 i 2 条可收 缩边 且下界是可以达到的 关于3 连通图中可收缩边在最大匹配上的分布情况 有如下结论t 定理1 1 9 1 不同构于j 的3 连通图的最大匹配上至少有一条可收缩边 关于3 连通图中可收缩边在最长圈上的分布情况 f u j i t a 在证明别人提出 的猜想时给出以下结论t 定理1 1 1 0 卢剐若g 是阶至少为5 的h a m i l t o n 的3 连通图 c 为g 的 h a m i l t o n 圈 则有i e c ne d g i i e i 8 o s 目前 对于3 连通图中可收缩边的分布和数目的研究已取得了丰富的研究 成果 而对后 4 连通图中可收缩边的分布情况和数目还知之甚少 有待于 进一步的探讨 后来人们把3 连通图中收缩边的概念推广为收缩子图 把收缩 i 晦界图的概念推广至3 临界图 其他关于连通图中可收缩边的研究可参见文献 6 1 2 2 1 2 8 3 2 4 6 等 下面我们来看一下对连通图中可去边的研究 h o l t o n 1 9 等首先给出了3 连通图中可去边的定义 3 山东大学硕士学位论文 定义1 1 1 1 口琊设e 是3 连通图g 的一条边 考虑下列运算 以 从g 中去掉e 得图g e f 缈如果e 的某个端点在g e 中度数为2 则去掉此端点 再联结此端 点在g e 中的两个邻点 f 动如果经过例中的运算后 有重边出现 则用单边代替它们 使得此图 为简单图 最后所得到的图记为g e e 若g e e 仍为了连通图 则称e 为g 的可去 边 否则称e 为g 的不可去边 关于可去边的研究成果 最早由b a r n e t t e 和g r u n b a n m 8 给出 他们得 到了 个类似可收缩边的结果 证明了每个阶大于4 的3 连通图都有可去边 并给出了3 连通图的 个递归构造的方法 d a w e s 1 0 利用这个结果给出了与 t u t t e 3 9 不同的极小3 连通图的递归构造方法 对于3 连通图中可去边的数目与分布 苏健基得到了下面几个定理 定理1 1 1 2 吲设g 是阶大于5 的3 连通图 并且g 不是轮 g 是g 中的 一个圈 则 p j 如果c 仅通过一个极大半轮 则g 上至少有一条可去边 f 缈如果c 不通过任何极 大半轮 则g 上至少有两条可去边 定理1 1 1 3 叫每个阶至少为5 的3 连通图 除w 与w 外 至少有f 3 t c i 1 8 7 1 条可去边 1 9 9 9 年尹建华 4 4 j 又将可去边的定义推广到了4 连通图 并给出了4 连 通图中不存在可去边的充要条件 定义1 1 1 4 7 设e 是毒连通图g 的一条边 考虑下列运算t 以 从g 中去掉e 得图g e 动如果e 的某个端点在g e 中度数为只则去掉此端点 再两两联结 此端点在g e 中的 个邻点 r 副如果经过f 矽中的运算后 有重边出现 则用单边代替它们 使得此图 为简单图 最后所得到的图记为g e e 若g e e 仍为l 连通图 则称e 为g 的可去 边 否则称e 为g 的不可去边 4 山东大学硕士学位论文 定理1 1 1 5 聋盯设g 是 连通图 g 中不存在可去边当豆仅当g 是c 或是 锈 利用这个结果和可收缩边的性质 尹建华 蚓又给出了4 连通图的 个递 归构造方法 对于4 连通图中可去边的分布 吴吉昌等 4 0 4 l 给出如下结果 定理1 1 1 6 i 町设g 是阶大于5 的4 连通图 若6 g 4 或9 g 3 则 6 的任一个萄上至少有两条可去边 定理1 1 1 7 廖聊设g 是阶大于7 的名连通图 c 是g 中一个最长圈 则 门j 如果c 仅通过一个双三角形 则g 上至少有一条可去边 f 夥如果c 不通过任何一个双三角形 则g 上至少有两条可去边 最近 厦门大学的徐丽琼在其博士毕业论文 4 铷中取得了突破性的进展 她将可去边的概念引入到了一般的k 连通图中 通过研究拟连通图与可去边之 间的关系 探讨七连通图中可去边的存在性问题 得到了一种5 连通图的构造 方法 主要结果如下 定义1 1 1 8 廖爿设e 是七连通困g 的一条边 考虑下列运算t 以 从g 中去搏e 得图g e 例如果e 的某个端点在g e 中度数为k 一1 则去掉此端点 再联结此 端点在g e 中的k 1 个邻点 f 圳如果经过f 矽中的运算后 有重边出现 则用单边代替它们 使得此图 为简单图 最后所得到的图记为g e e 若g e e 仍为k 连通图 则称e 为g 的可去 边 否则称e 为g 的不可去边 定义1 1 1 9 厚鄙若g 是k k 3 连通图且不存在非平凡的k 点割 则称g 是拟七 1 连通图 定理1 1 2 0 廖爿设g 是k k 3 连通图 i g l k 3 g 中不存在可去边当 且仅当g 是极小拟k 连通 定理1 l 2 1 廖可设g 是5 连通图 g 中不存在可去边当且仅当g 岂k j 利用这个结果 徐丽琼首次给出了5 连通图的 个递归构造方法 并提出 以下猜想 5 山东大学硕士学位论文 猜想1 1 2 2 廖鄙tg 是酸 芝3 连通图 g 中不存在可去边当且仅当奄为奇 敷时 g 掣j 氏 l 当七为偶数时 g 型k k 1 或上k 2 很显然 如果上述猜想成立 则可用统一的方法给出k 连通图的 个递归 构造方法 徐丽琼还首次对5 连通图中可去边的分布进行了研究 主要成果如下 定理1 1 2 3 廖珂设g 是5 连通图 g v 4 t 是g 的生成树 则有i e t n e 叠 g l 2 定理1 1 2 4 廖可设g 是5 连通图 g g 4 t 是g 的生成树 t o g e t 则有l e t o n 正 g i 2 定理1 1 2 5 廖剐设g 是5 连通图 l g i 1 0 g c 4 x y 双a b 是g 的 一个分离分解 若a 是一个边点割原子 则由v a u s 在g 中导出的子图的 每一条边都是可击边 其它关于连通图中可去边的研究可参考文献 2 9 3 1 3 5 4 2 1 等 1 2 本文的主要结果 本文主要研究连通图中可去边和可收缩边的性质以及它们在特定子图上的 分布情况 有以下几点创新z 1 对已有的4 连通图中可去边在圈上的分布结论进行了改进 并首次给 出了6 连通图中可去边的性质 2 对已有的4 连通图中可收缩边在完美匹配上的分布结果进行了改进 并 首次给出了5 连通图中的可收缩边在完美匹配上的分布情况 3 对k 连通图中可去边和可收缩边的分布情况提出了猜想 下面简单介绍一下本文的主要结果 以及在内容上的组织安排 全文共分四章 第一章简单介绍了对连通图中可去边与可收缩边的研究的 历史背景 进展状况 已取得的相关结果以及本论文的一些研究成果 并对本 文中需要用到的图论里的基本概念与符号进行了解释 这一章是后面其它各章 的基础 6 山东大学硕士学位论文 第二章主要研究连通图中可去边的性质及其分布 我们首先对已有的4 连 通图中可去边在圈上的分布结果进行了改进与推广 最终得到以下结论 定理2 2 1 0 设g 是4 连通图 c 为g 中任意的圈 若圈c 不与g 的任何阶 为2 的边点割断片相交 则g 上至少有两条可去边 接着 我们又首次给出了6 连通图中可去边的相关性质 主要结果如下t 定理2 3 2 设g 是6 连通图 l g i 1 1 6 g 7 铆 风 g 铆 s a b 为其对应的分离分解 其中霉 a l b 则e g 吲 g 五 g 定理2 3 3 设g 是6 连通图 l g i 1 1 g 的边点割原子的阶至少为3 霉 e c g 硎 s a b 为其对应的分离分解 其中卫 a 掣 b 则e c g 8 五k g 第三章主要讨论连通图中可收缩边的性质及其在完美匹配上的分布 我们 对已有的关于连通图中可收缩边在完美匹配上的分布的研究成果作了很大的改 进 首先是对已有的关于4 连通图中可收缩边在完美匹配上分布结果的改进 定理3 2 1 设g 是膨陕于7 的4 连通图 m 是g 的 个完美匹配 且m 上 的任意一条边不在三角形上 则m 上至少有两条可收缩边 然后 我们又将上述改进的结果推广到了5 连通图中 得到以下两个结论t 定理3 3 2 设g 是阶大于9 的5 连通图 m 是g 的 个完美匹配 且m 上 的任意一条边不在三角形上 则m 上至少有两条可收缩边 定理3 3 4 设g 是阶大于1 1 的5 连通图 m 是g 的 个完美匹配 若图g 的任意断片的阶都大于2 则m 上至少有两条可收缩边 最后 我们还得到了 个与6 连通图中的可收缩边相关的结论一 定理3 4 2 设g 是阶至少为8 的6 连通图 g 的任意端片的阶不等于2 设z 为g 的任意顶点 若与z 相关联的每一条边都是不可收缩的 则存在 n g c x 使得d c y 6 r g n n c y 7 山东大学硬士学位论文 在第四章中 我们首先对全文进了总结 然后在已取得的成果的基础之上 提出了以下猜想t 猜想4 0 1 设g 是k 连通图 6 g k 1 x y s a b 为g 的 个分离分 解 其中z a y b 则对任意的t s 叫是g 的可去边 猜想4 0 2 设g 是k 连通图 c 为g 中任意的圈 若圈g 不与g 的任何阶 为2 的边点割断片相交 则c 上至少有两条可去边 猜想4 0 3 设g 是k 连通图 m 是g 的 个完美匹配 若图g 的任意断片 的阶都大于2 则m 上至少有两条可收缩边 最后 我们对下 步的研究工作进行了展望 1 3 基本定义与符号 下面列出 些将在本文中使用的符号和定义 其他未定义的符号与术语参 见 9 1 图g 代表 个有序三元组 v c c e g 这里v o 表示非空顶点 集 e o 表示与v o 不相交的边集 妒台是关联函数 它使g 的每条边对应于 g 的无序顶点对 不必相异 若e 是一条边 让和v 是使得i o c e 伽的顶点 则称e 连接t 和t 顶点让和t 是e 的端点 且顶点t 和顶点t 与边e 相关联 顶点 和顶点u 相邻并互为邻点 似 代表由顶点u 在图g 中所有的邻点 所组成的t 的邻域 简记为 t 令y y g 记n o y u l e y g 掣 y y g 中元素的个数称为g 的阶 记为l g l 或钉 g 图g 中与顶点v 关 联的边的数日 称为顶点t 的度 记为d o t 6 0 表示g 中顶点的最小度 如果图g 中各个顶点的度数都等于惫 则称g 是k 正则图 d y 表示g 中恰 与y 中某个顶点相关联的边数 端点重合为一点的边叫做环 端点不相同的为 边 个图称为简单图 如果它既没有环也没有两条边连接同一对顶点 如果 图g 的顶点集和边集都有限 则称图g 为有限图 每一对不同的顶点都有一 条边相连的简单图称为完全图 n 个顶点的完全图记为j 乙 在本文中 我们仅 考虑有限的简单图 8 山东大学硬士学位论文 称图昱是g 的子图 记为昱 g 如果y 写 v g e h e 固 并且彻是 在e 日 上的限制 当日 g 但h g 时 记为hcg 并 且称日为g 的真子图 若图日是g 的子图 则称g 是日的母图 g 的生成 子图 或生成母图 是指满足y g y 日 的子图 或者母图 日 设 是v a 的 个非空子集 以 为顶点集 以两端点均在矿中的 边的全体为边集所组成的子图 称为g 的由 导出的子图 记为g f g 卅 称为g 的导出子图 导出子图g y 矿 简记为g v 它是从g 中删去 中 的点以及所有与这些点相关联的边所得到的子图 若矿 t t 则把g 一 t 简记为g t 设e 是e g 的非空子集 以f 为边集 以f 中边的端点的全体为顶 点集所组成的子图称为g 的由彤导出的子图 记为c e i g l e 称为g 的边 导出子图 边集为e 的g 的生成子图简记为g f 它是从g 中删除f 中的边所得到的子图 类似的 如果f e 则把g 一 e 简记为g e 设g 和g 2 是g 的子图 若g 1 和g 2 没有公共顶点 贝4 称它们是不相交 的 g l 和g 2 的并图g lu g 2 是指g 的 个子图 其顶点集为y g 1 u v g 其边集为e g 1 u e g 2 如果g l 和g 2 是不相交的 有时记其并图为g i g 2 设m 是e g 的 个子集 它的元素是g 中的边 并且这些边中的任意 两个在g 中均不相邻 则称m 为g 的 个匹配或对集 若匹配m 的某条边 与顶点t 相关联 则称m 饱和顶点t 如果图g 的 个匹配m 饱和g 中的 每 个顶点 则称m 为g 的完美匹配或完美对集 g 的 条途径 或通道 是指 个有限非空序列w 伽e i l e 2 t j 2 e k 仇 它 的项交替的为顶点和边 使得对1 i k e 的端点是哦和地一1 称 是从 到 的二条途径 顶点珈和 分别称为 的起点和终点 而t l 也 一l 称为它的内部顶点 整数奄为w 的长 如果途径 的边e l e 2 互不 相同 则w 称为迹 如果t i o 忱 仇互不相同 则称 为路 端点相同但 内部顶点不相同的迹称为圈 长为七的圈称为七圈 记作g 3 圈常称为三角 形 长度是奇数的圈为奇圈 否则为偶圈 g 的围长是指g 中最短圈的长 着 g 中没有圈 则定义g 的围长为无穷大 9 c 表示g 的围长 如果g 的任意 两个顶点之间都有连接它们的路 则称图g 是连通的 不连通的图的极大连通 子图称为此图的连通分支 图的连通分支的数日用u g 来表示 若v a 的子集矿使得g 一矿不连通 则 称为g 的顶点割 七顶点 9 山东大学硕士学位论文 剖是指舍有七个元素的顶点割 若g 至少有一对相异的不相邻的顶点 则g 所具有的七顶点割中最小的七 称为g 的连通度 记为k g 否则定义k g 为i g i 一1 若k g 七 则称g 是七连通的 设e 删为g 的边 收缩边伽是指在图g 中将 1 1 7 去掉 并将顶点t 和 合并成 个新的顶点 记所得的图为g e 七连通图g 中 条边称为可收 缩边 若收缩这条边后所得到的图仍然为七连通图 不存在可收缩边的非完全 七连通图称为收缩临界七连通图 显然 e 删为非完全七连通图g 的不可 收缩边当且仅当g 中存在包含顶点u 和t 的七点割 g 的所有可收缩边的集 合记为点b g 1 0 第二章连通图中的可去边 在这一章中我们主要讨论4 连通图中圈上的可去边的分布以及6 连通图 中可去边的性质 我们利用边点割原子 断片以及匿长等 将徐丽琼等在4 连 通囹中圈上的可去边的分布的部分结论进行了改进 并首次给出了6 连通图中 可去边的部分性质 2 1 基本定义和已知结果 首先 我们回顾一下七连通图中可去边的定义 定义2 i 1 廖爿设e 是l 连通图g 的一条边 考虑下列运算 以 从g 中去掉e 得图g e f 缈如果e 的某个端点在g e 中度数为七一l 则去掉此端点 再联结此 端点在g e 中的七一1 个邻点 俐如果经过俐中的运算后 有重边出现 则用单边代替它们 使得此图 为简单图 最后所得到的图记为g e e 若g e e 仍为七连通图 则称e 为g 的可去 边 否则称e 为g 的不可去边 g 的所有可去边的集合记为e r g g 的所 有不可去边的集合记为易v g 定义2 1 2 廖可设g 是七连通图 s 为g 的一个七点割 如果g s 的连通 分支能分成不相交的两部分记为g l 和g 2 使得i g l l 2 i g 2 i 2 则称s 为g 的非平凡詹点羽 g 是七连通图 e e g 若g e 中存在一个非平凡 七一l 点割s 使得g e s 恰有两个连通分支a 和b 其中霉 a 暑 b 且 i 2 i b i 2 则称 z 印为g 的分离对 z 耖 s a b 为g 的一个分 离分解 称a 和b 为由 z s 分离g 所得的边点割断片 简称g 的边点割 断片 并称阶最小的边点割断片为边点割原子 1 山东大学硕士学位论文 设玛 e n g 若蜀 妒 以及 矧 s a b 为g 的一个分离分解 其 中z a 可 b 若卸 岛 则称a 与b 是昂一边点割断片 如果品边点 割断片不包含其它岛 边点割断片作为他的子集 则称它为晶一边点割端片 若马为g 的所有的不可去边的集合 则称之为边点割端片 对于4 连通图中的可去边和不可去边的性质已有如下结论 定理2 1 3 廖 设g 是阶大于6 的4 连通图 则e x y 风 g 当且仅当 存在scy g i 矧 3 使得g e s 恰有两个连通分支a 和口 其中 a 掣 b 且f a i 2 i b i 2 定理2 1 4 1 4 4 1 设g 是阶大于7 的4 连通图 z y 点k g x y 最a b 是g 的一个分离分解 其中z a y b 如果i a i23 则对任意的牡 只 黜 是g 的可去边 对于k 连通图中可去边的研究 徐丽琼取得突破性进展 得到下列结果 定理2 1 5 艮彤设g 是k k 3 连通图 i g l 2k 3 刘e x y 毋 q 当 且仅当存在scy g i s i k 一1 使得g e s 恰有两个连通分支a 和 b 其中z a 譬 b 且i a i 2 i b i 2 定理2 1 6 a 纠谩g 是k k 6 连通图 若g 中任一条边的两个端点在g 中至多有k 一3 个公共的相邻点 则g 中存在可去边 最后 对于南连通图中可去边的存在性 徐丽琼提出以下猜想t 猜想2 1 7 廖习g 是七连通图 g 中不存在可去边当且仅当七为卡敷时 g 岂 j l 当k 为偶数时 g 鲁j l 或三k 2 质t 另外 在k 5 时 许丽琼还特别给出了以下关于5 连通图中可去边的性 山东大学硕士学位论文 定理2 1 8 廖鄙设g 是5 连通图 l g l 1 0 6 g 6 则任意z y e g x y 或是可去边或是可收缩边 定理2 1 9 廖可设g 是5 连通困 l g i 1 0 g g 4 x y j 啊 g 扛鲈 s a b 为其对应的分离分解 其中z a y b 则e g 研 e r g 在接下来的两节里 我们将对徐丽琼关于连通图中可去边的部分研究成果 进行改进与推广 2 24 连通图中圈上的可去边 对于 4 连通图中的可去边在圈上的分布情况 吴吉昌 李学良在 4 1 中有 如下结果t 定理2 2 1 廖纠设g 是4 连通图 6 g 5 或g c 4 则对g 中某一圈 al e c n e 童 g l 2 对于上述结果 徐丽琼作了进 步改进 给出以下更好的结论t 定理2 2 2 b 3 设g 是 连通图 若对于g 中莱一圈c 上任意顶点z 玉在 g 中无4 度相邻点 则f 昱 n 置r g l 2 定理2 2 3 b s 设g 是彳连通图 若g 不含k i 子图 则对g 中任一圈a 有i e c n e r g i 2 对于可去边在4 连通图4 圜上的分布 徐丽琼还特别给出以下结果 定理2 2 4 露珂设g 是4 连通图 i g i 8 c 为g 的一个幸圈 若c 上有连 续的两个度大于 的顶点 则g 上至少有一务可去边 1 3 山东大学硬士学位论文 下面 我们将进一步改进与推广上述关于4 连通图中可去边在圈上的分布 的研究成果 在给出我们的结论之前 先来回顾一下子图不相交的概念 定义2 2 5 9 设g 1 和g j 是g 的子图 若g l 和g 2 没有公共顶点 则称它 们是不相交的 若g 1 和 毛没有公共避 则称它们是边不重的 对于可去边在4 连通图4 圈上的分布情况 我们给出以下结论 引理2 2 6 设g 是4 连通图 c 为g 的一个4 圈 若c 不与g 的任何三圈 相交 则g 上至少有一条可去边 证明 设c z l 现 z l 1 为g 的4 圈 假设e q e k g 取g 的一个 分离分解 x l z 2 最a b 其中z 1 a 勋 b 由定理2 1 3 知吲 3 且 l a l 2 i b i 2 情况l l a l 3 则由x 4 x l 互k g 和定理2 1 4 知 x 4 a 因此 必有铂 s 由定理 2 1 4 和勋勋 e g 知 i b i 2 设b 2 o 由g 是4 连通图 i 酬 3 知 d a 4 d x 2 4 所以 勘口必在g 的某个三角形上 与题设隧g 不与 g 的任何三圈相交矛盾 情况2 i a i 2 设a 忙l 6 由g 是4 连通图 吲 3 知 d b 4 d x 1 4 所 以 1 6 必在g 的某个三角形上 与题设圈c 不与g 的任何三圈相交矛盾 定理得证 口 分析z 仔细观察上述引理2 2 6 的条件 若c 为4 连通图g 的 个4 圈 且e 不与g 的任何三圈相交 那么 c 与g 的任何三圈都是边不重的 类似 上述引理2 2 6 的证明 我们将引理2 2 6 进一步改进成以下结论t 定理2 2 7 设g 是4 连通图 c 为g 的一个彳圈 若c 与g 的任何三圈都 是边不重的 更i i c 上至少有一条可去边 1 4 山东大学硕士学位论文 证明 设c z l x 2 2 3 x 4 2 1 为g 的4 圈 假设e c 踟 g 取g 的 个 分离分解 l 霉2 s a b 其中 l a 奶 b 由定理2 1 3 知i s i 3 且 i a i 2 i 引 2 情况1 i a i 3 则由z 4 z l e k g 和定理2 1 4 知 x 4 a 因此 必有勋 s 由定理 2 1 4 和x 2 2 3 五i g 知 l b i 2 设b z 2 口 由g 是4 连通图 i s i 3 知 d d 4 d c x 2 4 所以 x 2 x 3 必在g 的某个三角形上 与题设圈g 与 g 的任何三圈都是边不重的矛盾 情况2 i a i 2 设a p 1 h 由g 是4 连通图 l s l 3 知 d 6 4 d c x l 4 所 以 茁1 瓤必在g 的某个三角形上 与题设圈c 与g 的任何三圈都是边不重的 矛盾 定理得证 口 引理2 2 8 设g 是4 连通图 g 为g 的一个4 圈 若圈c 不与g 的任何阶 为2 的边点割断片相交 则e 上至少有一条可去边 证明t 设c z l z 2 x 3 x 4 2 1 为g 的4 圈 假设e g 五k g 取g 的 个分 离分解 z 1 勋 s a b 其中z 1 a 现 口 由题设知i a i 3 则由2 4 2 l 蜀v g 和定理2 1 4 知 x 4 a 因此 必 有z 3 s 由定理2 1 4 和x 2 2 3 点k g 知 i b i 2 与题设圈c 不与g 的 任何阶为2 的边点割断片相交矛盾 故上述定理成立 口 浊 设c 为4 连通图g 的 个4 圈 那么 由圈c 与g 的阶为2 的边 点翻断片相交必能推出c 与g 的某个三圈有边相重 因此上述引理2 2 8 是对 定理2 2 7 的进 步改进 事实上 对于上述引理2 2 8 中4 圈上可去边数目的下限 我们还可做如 下改进 山东大学硬士学位论文 定理2 2 9 设g 是4 连通图 c 为g 的一个4 圈 若圈g 不与g 的任何阶 为2 的边点割断片相交 则c 上至少有两条可去边 证明 设c z 1 0 2 x 3 x 4 x l 为g