5-连通图和7-连通图的可收缩边的分布

来源 :山东大学 | 被引量 : 0次 | 上传用户:jiaomengni
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的连通性是图论非常重要的概念之一,图的许多性质和图的连通性有着密切的关系。在图论的研究方法中,我们常常运用一些图的特性的运算,用一些简单的连通图构造出复杂的连通图满足要求的性质。基于此,图的可收缩边运算成为研究复杂连通图的有力工具之一。  本文选择连通图的可收缩边作为研究的对象,考虑5-连通图和7-连通图的可收缩边在不同的特定子图——最长圈、生成树和完美匹配上的分布情况,并得到相应的结果。对于5-连通图,本文首先对5-连通图最长圈上可收缩边的分布的已有成果进行了改进,并首次提出5-连通图生成树上可收缩边的分布情况,得出的主要结论有:定理2.1.3设G是5-连通图,且G中不存在2-断片。P:x=x1x2…xn=y是G的一条最长(x,y)-路。如果路P上任一顶点xi都满足以下条件之一,那么P上至少有两条可收缩边:⑴d(xi)≥6;d(xi)=5,则[V(P)]中无3-圈包含它。定理2.2.1设G是5-连通图,且G中不存在2-断片,H是G的一棵生成树。如果H上的任一顶点xi均满足以下条件之一,则生成树H上至少有一条可收缩边:d(xi)≥6;d(xi)=5,则[V(H)]中无3-圈包含它。对于7-连通图,本文仍然采用树形结构理论进行分类讨论,考虑了7-连通图的可收缩边在最长圈、生成树以及完美匹配上的分布情况,得到的主要结论有:定理3.1.5设G是7-连通图,且G的任意断片的阶都大于3。若C:x=x1x2…xn=y是G的任意最长圈,则C至少包含三条可收缩边。定理3.2.1设G是7-连通图,H是G的一棵生成树。如果G任意一个断片的阶都大于3,那么生成树H上至少包含两条可收缩边。定理3.3.7设G是7-连通图且|G|>15,并且M是G的一个完美匹配,如果M上的任意一条边均不在三角形上,那么M上至少包含两条可收缩边。定理3.3.8设G是7-连通图且|G|>15,M是G的一个完美匹配,如果图G的任意一个断片的阶都大于3,那么M上至少包含两条可收缩边。
其他文献
学位
举世瞩目的上海世博会开幕两个多月了,参观人数已逾两千万人次。在长达6个月的世博会举办期间,新鲜蔬菜的及时供应成为人们关注的一个重要话题。据了解,世博 The world-reno
学位
信息技术是一门对学习资源进行设计、开发、利用、管理和评价的实践性学科.随着我国信息技术的不断发展和电子计算机的普及,加强高中信息技术教育变得越来越重要.新课改的实
随着人类社会的不断进步,科学技术的不断发展,生产和生活的控制和管理问题的规模越来越大.控制系统的结构也越来越复杂,出现了各种结构的大系统.由于大系统具有结构特殊的关联项
大部分的实际工业系统(如电力系统、通信系统等)都不可避免地存在时滞和不确定现象.同时,非线性广义系统广泛出现在工程应用中,例如:飓风的预报、受限机器人等,因此,致力于非线性不
非结构化网格被广泛地应用到许多科学和工程的数值计算过程中.Delaunay三角形化方法是生成非结构化网格的重要方法之一.这种方法生成的三角形网格具有以下特点:(1)所形成的三角
期刊
泛函微分方程初值与边值问题起源于各种不同自然科学领域,如传染病学,核物理学,控制论等[13].现实中很多的现象可以用泛函微分方程来刻画,所以泛函方程的研究具有重要的理论意义和
对于完全二阶柯西问题,研究问题的正则性和解的存在性与唯一性有着非常重要的意义.现实生活中,各种波动方程,梁方程,黏弹性、强阻尼方程等为完全二阶方程提供了丰富的背景。一