中文摘要：

一个图的最大匹配图是以这个图的最大匹配集作为顶点集,两个顶点相邻当且仅当这两个最大匹配恰有一条边不同.本文首先对Gallai-Edmonds结构定理中的三部分顶点在二部图中进行了详细刻画.然后讨论了构造最大匹配图问题的计算复杂性.最后深入研究了二部图最大匹配图的结构性质并给出了构造二部图的最大匹配图的一种算法.

英文摘要：

The maximum matching graph of a graph is that graph whose vertices are the maximum matchings and where two vertices are adjacent if and only if the two maximum matchings differ by exactly one edge.In this paper,we first study the structure of three kinds of vertices in the Gallai-Edmonds theorem on bigraphs.Then,we show the computational complexity of the problem of constructing maximum matching graphs.Finally,we study the structure of the maximum matching graphs and give an algorithm for constructing the maximum matching graphs on bigraphs.