论文部分内容阅读
最大匹配问题有着广泛的应用,并且在图论和组合最优化中起着非常重要的作用。从算法的角度来看,人们想知道图的所有最大匹配之间的关系,因此开始研究以最大匹配为顶点构造的变换图的性质。当图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).