论文部分内容阅读
本文所涉及的图均为无向、简单有限图。我们称一个新图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的两个最大匹配。