第二类最大匹配图

来源 :华南师范大学 | 被引量 : 0次 | 上传用户:czy239239
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文所涉及的图均为无向、简单有限图。我们称一个新图M2(G)为图G的第二类最大匹配图,若该图以图G的所有最大匹配为顶点,两个最大匹配在该图中相邻当且仅当它们的对称差是一条长为2的路或者是一个圈。本文研究了M2(G)的结构,证明了M2(G)没有禁止子图,刻画了M2(G)分别为树、圈、完全图时图G的结构,并且得到了M2(G)中两顶点距离的上界。  令D(G)={v∈V(G)|存在一个最大匹配不覆盖点v},A(G)={v∈V(G)-D(G)|至少存在一个D(G)中的点与v相邻},C(G)=V(G)-(A(G)∪D(G))。为了表达的方便,我们分别记由C(G),D(G)和A(G)∪D(G)导出的子图为GC,GD和GAD。记dG(v1,v2)为G中连接两顶点v1和v2的最短路的长度。令M1和M2为G的两个最大匹配。我们分别记M1()M2为M1和M2的对称差,r(M1()M2)为M1()M2中交错圈的数目,p(M1()M2)为M1()M2中各交错路长度之和。  本文的主要结果如下:  定理1设G是一个图。那么M2(G)≌M2(GC)□M2(GAD)。  定理2设G是一个图。那么存在一个图H使得G是M2(H)的导出子图。  定理3设G是一个无孤立点的图。那么M2(G)是非平凡的树当且仅当G满足下列条件之一:  (1)G=GC且G恰有两个完美匹配;  (2)C(G)=0或GC恰有一个完美匹配,并且GAD是树。  定理4设G是一个无孤立点的图。那么M2(G)是完全图当且仅当G满足下列条件之一:  (1)C(G)=0或GC恰有一个完美匹配,并且GAD=K3或GAD=K1,n;  (2)G=GC,并且对于G的任意一个完美匹配M而言,任意两个M-交错圈的对称差都是一个偶长圈。  定理5设G是一个无孤立点的图。  (1)当D(G)=0时,M2(G)是圈当且仅当G满足下列条件之一:  (a)G恰有三个完美匹配;  (b)G恰有四个完美匹配,并且存在一个完美匹配M使得G中恰有两个M-交错圈,记为C1和C2,且C1∩C2=0。  (2)当D(G)≠0且GC至多有一个完美匹配时,M2(G)是圈当且仅当GAD∈{B*,C2n+1,2K1,2,K1,3}。  (3)当D(G)≠0且GC至少有两个完美匹配时,M2(G)是圈当且仅当GAD=K1,2和GC恰有两个最大匹配。  定理6设G是一个图。那么dM2(G)(M1,M2)≤r(M1()M2}+1/2P(M1()M2)。其中M1和M2是图G的两个最大匹配。
其他文献
本文共分为三章.第一章回顾所研究问题的历史背景与发展现状.第二章给出本文所需的预备知识,并简要陈述本文的主要工作.第三章讨论离散的薛定谔方程的呼吸子的存在性.  我
考虑个体结构差异的生物种群动力学是生态学领域中基本的研究课题之一。它在揭示种群的演化规律中起着很重要的作用。种群生态学是生态学的重要组成部分,而个体生命参数是种群
本文主要利用混合有限元方法解半线性椭圆型偏微分方程。为了线性化方程组,我们构造了建立在牛顿叠代法上的两层网格算法。首先,我们在粗网格上解原始的非线性方程组,然后,我们在
高维拟共形映射是上世纪五六十年代才兴起的学科.由于它在几何分析、偏微分方程、拓扑以及低维流形等领域的广泛应用,使其成为数学研究中的一个热点.经过这些年的研究,高维拟共
从历史来看,经济全球化和金融自由化像一把双刃剑,它能促进贸易和投资、使世界范围内的资源配置更为有效合理、加速技术转让和产业结构调整的进程、提高国家金融业的效率和创新
数字签名是信息安全领域的一个重要研究方向,它在身份识别与认证、数据完整性保护和抗否认等方面具有其它技术无法替代的作用。作为手写签名的模拟和扩展,数字签名广泛应用于
随着世界经济的快速发展和现代科学技术的进步,多数企业会选择把自己的资源投放于核心竞争力上,由第三方物流企业来负责完成原材料的物流配送以及后续待售成品的物流配送。物流
随着科技的迅速发展,社会生活的各领域堆积了越来越多的数据信息。为将复杂多样的信息转换为有用信息,数据挖掘技术应运而生。而作为数据挖掘重要工具之一的聚类分析技术也成
本篇论文研究了一类带有纯时滞的离散Gilpin-Ayala捕食者-食饵系统的持久性和全局稳定性以及在时间尺度上带有反馈控制和时滞的共生模型的持久性,概周期解的存在性和一致渐近
初中物理教材的内容与生活联系较紧密,着重于学生对生活现象的认识由感性上升到理性,并掌握简单的计算。而到了高中阶段,教材的编排则着重于对学生逻辑思维能力和知识点间联