6连通图中的可收缩边

作     者：张志芳 

作者单位：河南师范大学 

学位级别：硕士

导师姓名：卢建立

授予年度：2011年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：连通图 收缩临界连通图 可收缩边 完美匹配 

摘      要：早在200多年前,人类已经开始涉足图论的研究领域.1736年,Euler用图的方法解决了哥尼斯堡七桥问题,发表了第一篇图论论文.二十世纪三十年代以来,图论在科学界异军突出,活跃非凡.哈密顿圈问题、四色问题、中国邮递员问题等等,这些都是图论中非常重要的问题,而且在解决信息和计算机科学、生物学、化学等学科问题上图论也已经显示出很大的优越性.与此同时,在社会科学以及工程技术领域中,图论也有着广泛的运用. 图的连通性是图的最基本的性质之一,连通度是分析和刻画图的有力工具,有大量的问题可以归结为图的条件边连通问题,所以这方面是图论的热点研究领域.目前,互联网络已经与人们的工作、日常生活等方面息息相关,连通图与网络模型和组合优化的密切联系,使它拥有很强的应用背景.K-连通图的K-可去边和K-可收缩边的存在对于探讨图的结构、证明图的某些性质有着重要的应用,所以,对于它们的研究具有非常重要的理论价值和应用价值.本论文选择连通图中的可收缩边作为研究对象,目的就是通过努力能够进一步的了解连通图的结构以及找出其构造方法,对以后的研究工作有所帮助. 本论文主要研究6-连通图中可收缩边的性质以及它们在特定子图上的分布情况.下面先简单介绍一下本文的主要结果. 第二章主要研究6-连通图完美匹配上可收缩边的分布情况,得到如下结论:定理设G是阶大于12的6?连通图,M是G的一个完美匹配,若图G的任意断片的阶都大于3,则M上至少有两条可收缩边. 第三章在第二章研究基础上,继续探索6-连通图中的可收缩边,得到6-连通图最长圈上可收缩边的分布情况,结论如下: 定理设G是一个任意断片的阶都大于2的6-连通图, C = x x ... xx是G的任意最长圈,若C上的任意顶点xi都满足以下条件之一,则G至少包含两条可收缩边. (1) d ( x)≥7;(2) d ( x) = 6,则V (C )中无3-圈包含它. 不存在K-可收缩边的非完全K-连通图称为收缩临界K-连通图.收缩临界K-连通图的研究也是目前比较热门的一个课题,本文第四章给出了收缩临界6?连通图6度点的分布及断片的相应结果. 定理设G是收缩临界6-连通图, x是G中任意一点,设A是一个x-原子,记N = T, N (x)∩T≠Φ,则A∩T中有与x相邻的6度点或两点的距离为2. 定理设G是收缩临界6-连通图, x∈V ( G), F是G中的断片,且x∈N ( F).若|F|≥4,|(F|-)|≥3且N ( x )∩F = {x},则存在一点x,使得: x∈N ( F )∩N ( x )∩N ( x )∩V (G ).