最大匹配图的性质

来源 :华南师范大学 | 被引量 : 0次 | 上传用户:hxffxh2009
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
最大匹配问题有着广泛的应用,并且在图论和组合最优化中起着非常重要的作用。从算法的角度来看,人们想知道图的所有最大匹配之间的关系,因此开始研究以最大匹配为顶点构造的变换图的性质。当图G有完美匹配时,张福基和郭晓峰等人研究了完美匹配图的性质。当图G没有完美匹配时,Eroh和刘岩等人研究了最大匹配图的性质。   本文所涉及的图均为无向、简单有限图。我们称图M(G)为图G的最大匹配图,该图以图G的所有最大匹配为顶点,两个最大匹配在该图中相邻当且仅当它们的对称差是一条长为2的路。本文研究了M(G)的结构,证明了一个关于最大匹配图中两个顶点最小距离的充要条件,刻画了最大匹配图直径为2的二部图。   令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),A(G)∪D(G)和D(G)导出的子图为GC,GAD和GD。记dG(v1,v2)为G中连接两顶点v1和v2的最短路的长度。令M1和M2为G的两个最大匹配。我们分别记M1(Θ)M2为M1和M2的对称差,r(M1(Θ)M2)为M1(Θ)M2中交错圈的数目。   本文的主要结果如下:   定理1设G是一个图,M(G)是G的最大匹配图且M和M"是G的两个最大匹配.则dM(G)(M,M")=|M-M"|+r(M(Θ)M")当且仅当存在一个有正剩余的二部子图G1使得M(Θ)M"(∈) E(G1)和V(G1)(∈)V(G)-V(M∩M").   定理2设G=(U1,U2)是一个没有孤立点的二部图.则M(G)的直径为2当且仅当C(G)=(φ)或Gc只有一个完美匹配且GAD=S*n,Sm∪Sk或Sm∧1Sk(m,k≥2).
其他文献
本文对流体力学方程(如,Boltzmann方程和Navier-Stokes方程)解的极限行为做了相关研究。即,上述方程的解的大时间行为,以及Navier-Stokes方程的粘性消失极限。全文共分为四章,其中
翻转课堂课前学习微课以构建主义为指导,利用情境教学法设计教学,通过创设典型情境,激起学生的学习兴趣,从而用情感活动加强认知活动,是教育界广泛接受的教学方法.但在实践过
该文给出了关于模糊关系方程及不等式求解的新方法.引入了符号矩阵,通过对符号矩阵的操作,简便地得到方程的最广泛的解集.当然最大解和极小也随之得到.另外将模糊关系不等式
学位
在阅读教学中,常常看到这样的境况:学生在阅读中,漫不经心的看着,有气无力的读着,无精打采的瞅着,阅读教学的处境依然到了这种尴尬的境地,这让我们的老师的教学情何以堪?我们
期刊
学位
Sylvester矩阵方程在众多领域中都有涉及,如图像恢复、神经网络、信号处理、模型降阶等。由于精确解的获得很困难,且在许多实际应用中,数值解也扮演非常重要的角色,因此关于Sylve
“中外合作办学”专业对专业课程的讲授有着双语授课的要求.而在应用型大学,双语教学面临着师资队伍英文授课资历深浅不一,学生英文水平参差不齐,专业课程内容理解困难等障碍
随着社会的发展,英语已经成为人们生活、工作和学习的重要组成部分,英语的表达和写作能力也已经成为人们沟通和交流的重要能力.在现代中国的教育体系中,英语教学主要分为听、