匹配可扩理论的若干新结果

来源 :厦门大学 | 被引量 : 0次 | 上传用户:catche
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
匹配理论是图论中一个重要的基础分支,它不仅对认识图的结构有重要作用,而且也广泛的应用到组合优化,理论化学等研究领域。匹配可扩理论是匹配理论中热门的研究方向,已产生了许多有价值的结论,特别是引入了k-可扩图、n-因子临界图、(n,k,d)-图、k-圈共振图等一系列图类,这些概念的引入对进一步揭示图的结构有重要的贡献。本文主要研究了1-可扩图中可去耳朵数的下界,图的分数匹配可扩性,奇图(阶为奇数)的匹配可扩性以及如何用最少的完美匹配覆盖图中所有边等问题。 设G是一个图。如果删除G中任意n个点后所得的余图有k-匹配,并且任意的k-匹配都可以扩充为该余图的一个亏d-匹配,那么称G是一个(n,k,d)-图[1]。显然这一概念是k-可扩图和n-因子临界图的推广。k-可扩图对应的是(0,k,0)-图,n-因子临界图对应的是(n,0,0)-图。本文我们也称(0,k,1)-图是几乎k-可扩图。下面是本文的主要结果: 1.改进了Carvalho,Lucchesi与Murty [2]给出的1-可扩图中可去耳朵数的下界,证明了任意一个1-可扩图G至少有χ(G)个边不交的可去耳朵,其中χ(G)表示图G的边色数;并得到了1-可扩图中可去边的一些性质。 2.设G是一个1-可扩图,χe(G)表示覆盖G中所有边所需最少完美匹配的数目,称为图G的excessive指数。我们给出了χe(G)的一个紧的上界;对任意正整数k≥3,构造了一个图G使得△(G)=3但χe(G)=k;进而研究了乘积图G×H的excessive指数χe(G×H)。 3. 改进了已有的(n,k,d)-图的刻画;给出了几乎k-可扩图和几乎k-可扩二部图的刻画;研究了几乎k-可扩图与n-因子临界图之间的关系,去边和加边对几乎k-可扩图的影响以及平面奇图的匹配可扩性。 4.给出了分数尼一可扩图的两个充分条件和极小分数k-可扩图的刻画;证明了分数后k-可扩二部图与k-可扩二部图是等价的;并研究了分数k-可扩图与n-因子临界图之间的关系。
其他文献
互补性概念是最优化问题以及平衡性分析和计算研究的中心.事实上,在研究线性规划的初期,线性规划的算法、分析及其结构等基本方面与互补松弛性的相关性就已经获得了普遍的认可,
块算法和分解算法是支持向量机的两个主要迭代算法,序贯最小优化算法是一种特殊的分解算法,将工作集的样本个数固定为两个,带来的直接后果是迭代次数的增加,当原始训练集的样
TV正则化方法是近几年来处理图像复原、图像去噪的一个新的方法、新的热点。在时域上单正则参数的TV正则化方法在图像去噪中的应用相当广泛和有效。而小波变换更是处理图像的
本文给出了二维Ricci流方程的一个八维李代数  X1=(e)t,X2=(e)x,X3=(e)y,X4=t(e)t+u(e)u,  X5=y(e)x-x(e)y,X6=x(e)x+y(e)y-2u(e)u,  X7=xy(e)x+y2-x2/2(e)y-2yu(e)u,X
目前,大多数企业应用系统都采用面向对象技术与关系数据库相结合的开发方式,这意味着数据需要在对象模型和关系模型间进行转换。这就引出了对象模型和关系模型之间的阻抗不匹配
期刊
本文主要研究Cantor级数∞∑n=1bn/a1…an和Ahmes级数∞∑n=11/an以及级数∞∑n=1bn/an。其中a1,a2,…为大于1的整数,b1,b2,…为任意整数并使得Cantor级数∞∑n=1bn/a1…an和Ahmes
期刊
计算机和以计算机为核心的信息网的出现和发展,使人类开始步入了信息时代,这为人们的生活和工作带来了极大的便利,人们可以通过网络快速传递、及时了解和相互交流信息;然而,科技的