最大匹配的路变换图

Path-transformation graph of maximum matchings

图G的最大匹配的路变换图NM(G)是这样一个图,它以G的最大匹配为顶点,如果两个最大匹配M_1与M_2的对称差导出的图是一条路(长度没有限制),那么M_1和M_2在NM(G)中相邻.研究了这个变换图的连通性,分别得到了这个变换图是一个完全图或一棵树或一个圈的充要条件.

The path-transformation graph of maximum matchings of a graph G,denoted by NM(G)is a graph where vertices are maximum matchings of G and two maximum matchings M1 and M2 are adjacent in NM(G)if the symmetric difference of M1 and M2 induces a path(there is no limit for the length of the path).In the paper,we study the connectivity of the transformation graph,and obtain the necessary and sufficient condition that the transformation graph is a complete graph or a tree or a cycle,respectively.