6连通图中的可收缩边

来源 :河南师范大学 | 被引量 : 0次 | 上传用户:xienengxian0615
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
早在200多年前,人类已经开始涉足图论的研究领域.1736年,Euler用图的方法解决了哥尼斯堡七桥问题,发表了第一篇图论论文.二十世纪三十年代以来,图论在科学界异军突出,活跃非凡.哈密顿圈问题、四色问题、中国邮递员问题等等,这些都是图论中非常重要的问题,而且在解决信息和计算机科学、生物学、化学等学科问题上图论也已经显示出很大的优越性.与此同时,在社会科学以及工程技术领域中,图论也有着广泛的运用.   图的连通性是图的最基本的性质之一,连通度是分析和刻画图的有力工具,有大量的问题可以归结为图的条件边连通问题,所以这方面是图论的热点研究领域.目前,互联网络已经与人们的工作、日常生活等方面息息相关,连通图与网络模型和组合优化的密切联系,使它拥有很强的应用背景.K-连通图的K-可去边和K-可收缩边的存在对于探讨图的结构、证明图的某些性质有着重要的应用,所以,对于它们的研究具有非常重要的理论价值和应用价值.本论文选择连通图中的可收缩边作为研究对象,目的就是通过努力能够进一步的了解连通图的结构以及找出其构造方法,对以后的研究工作有所帮助.   本论文主要研究6-连通图中可收缩边的性质以及它们在特定子图上的分布情况.下面先简单介绍一下本文的主要结果.   第二章主要研究6-连通图完美匹配上可收缩边的分布情况,得到如下结论:   定理设G是阶大于12的6-连通图,M是G的一个完美匹配,若图G的任意断片的阶都大于3,则M上至少有两条可收缩边.   第三章在第二章研究基础上,继续探索6-连通图中的可收缩边,得到6-连通图最长圈上可收缩边的分布情况,结论如下:   定理设G是一个任意断片的阶都大于2的6-连通图,C=x1x2…xmx1是G的任意最长圈,若C上的任意顶点xi都满足以下条件之一,则G至少包含两条可收缩边.   (1)d(x1)≥7;   (2)d(x1)=6,则V(C)中无3-圈包含它.   不存在K-可收缩边的非完全K-连通图称为收缩临界K-连通图.收缩临界K-连通图的研究也是目前比较热门的一个课题,本文第四章给出了收缩临界6-连通图6度点的分布及断片的相应结果.   定理设G是收缩临界6-连通图,x是G中任意一点,设A是一个x-原子,记NA=TA,N(x)∩TA≠φ,则A∩TA中有与x相邻的6度点或两点的距离为2.   定理设G是收缩临界6-连通图,x∈V(G),F是G中的断片,且x∈N(F).若|F|≥4,|-F|≥3且N(x)∩F={x1},则存在一点x2,使得:x2∈N(F)∩N(x)∩N(x1)∩V6(G).  
其他文献
学位
本文详细分析了古城油田泌123区套管损坏情况,按套损率、套管型号、使用寿命、套损点与油层关系、与套管接箍的位置关系等进行深入分析。分地质因素、工程因素具体深入分析了
谱图理论主要研究图的谱性质与图的结构性质之间的关系,通过图的谱性质刻画图的结构性质.1985年,Brualdi和J.Hoffman在文[4]中提出了邻接谱半径的极图问题.近三十年来,谱半径的极图
Wythoffs游戏是公平组合游戏中重要的组成部分.该游戏模型可描述为:有两堆各若干个石头,游戏者轮流移动,(i)要么从两堆中选定一堆,从中移走任意正整数个石头(称为Nim移法);(i
学位
本文概述了钻井用膨润土的基本组成、晶体结构及基本性质,通过对四种膨润土的改性方法及原理的研究,结合运用X-射线衍射仪等多种分析方法对其微观组分进行分析,确定几种土的主要
本文主要讨论以下问题:一方面是Hopfπ-余代数上的双积结构及其性质;另一方面是具有投射的Hopfπ-余代数的分解问题.   首先,本文简单介绍了Hopfπ-余代数的研究背景及本
文13东块为文东滚动背斜东翼。经过20年的开发,主力层水淹严重,二三类层存在注不进、采不出的特点,同时由于文13东的地质特点使井况加剧损坏。为此,在精细剩余油研究、开展构造精
本文利用距离几何的理论与方法,研究了欧氏空间、球面空间、双曲空间中n维单形的几何不等式问题,建立了单形一些新的几何不等式和一些不等式的推广。全文共分五章:   第一章,
在本文中,利用circle fixed point index lemma给出了Circle Packing基本定理唯一性的一个简洁证明;利用Winding Number的同伦不变性,推广了Rouche定理继而给出了关于全纯函数连