k-连通图中生成树和完美匹配上的可收缩边

来源 :山东大学 | 被引量 : 0次 | 上传用户:galatea
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图论是组合数学的分支,是一个具有悠久历史并且发展迅速的数学分支。它起源于一个古老的民间游戏—格尼斯堡七桥问题。1736年欧拉解决了上述问题,发表了关于图论的第一篇文章,图论由此产生。  图的结构特征是图论的主要研究方向之一,其中图的连通性一直是图论研究的重要课题。在研究图的连通性的过程中主要包括对图的结构特征进行探究和分析。在进行有关连通图的构造时,我们一般采用一些定义作为基础,并且运用特殊的运算来保持图的连通性,对复杂的连通图进行上述运算得到简单的连通图。因为可去边与可收缩边能够保持图的连通性,所以它们成为构造连通图的常用工具。  假设边e=xy∈E(G),把顶点x,y都去掉,并把与这两个顶点关联的边都去掉,再将一个新的顶点u添加到图G中,并且将刚刚去掉的两个顶点的所有邻点与新增的顶点邻接。上述运算即为将边e收缩,得到的新图记为G/e。如果得到的新图依然能够保持原图的连通性,我们称这条边e是G的可收缩边,反之则为不可收缩边。  本文主要研究k-连通图中的可收缩边的存在性及数目,分别为k-连通图中生成树上的可收缩边数目以及如果图中存在完美匹配时完美匹配上的可收缩边数目,并得下述结果。  定理2.1假设G是阶数为n(n≥7)的k-连通图(k≥3),H是G的一棵生成树,满足图G的任意断片阶数都大于「k/2(]),则H上至少有k+1条可收缩边。  假设k-连通图中存完美匹配,给出其可收缩边数目的结果如下:  定理3.1假设G是阶数为n(n≥0)的k-连通图(k≥3),M是G的一个完美匹配,满足图G的任意断片阶数都大于「k/2(]),则M上至少有「k/2(])+1条可收缩边。
其他文献
本文主要研究学生的学习态度对于考试成绩的影响.在模型中,每个考生有一标签g∈{0,1}∶1,0二值分别表示该生学习态度端正和不端正.假定考生v的标签gv是未知的.主要目的之一就
自然科学与工程技术中许多非线性问题的不断出现使得Sobolev空间表现出了其应用范围的局限性,例如对一类具有变指数增长性条件的非线性问题的研究。具有变指数增长性条件的非
矩阵理论是代数学科的一个重要分支,也是一种基本的数学工具,在数学学科以及其他的很多学科领域内都有重要的应用。目前,矩阵理论已经广泛的应用在无线通信,金融统计,系统工
双曲型守恒律方程数值解法既是偏微分方程数值解研究的重点,也是难点。通常我们只能得到该方程的弱解,所以必须对其加以限制,才可能获得符合物理背景的解。与物理背景紧密联
变量降维问题一直在统计研究学习以及实际应用领域起到至关重要的作用,对于存在多重共线性问题的数据,一般的最小二乘方法基本失效。本文介绍了一般的共线性变量选择方法包括