平面二部图的完美匹配集合上的有向根树结构及其生成

Directed Rooted Tree Structure of the Set of Perfect Matchings of Plane Bipartite Graphs and Its Generation

图的完美匹配或１－因子指覆盖了其所有顶点的独立边集．对含有完美匹配的平面二部图，其所有完美匹配通过某旋转变换形成层次组织结构，可用有向根树或半格表示．

A perfect matching or 1 factor of a graph is a set of independent edges covering all the vertices. For a plane bipartite graph G with perfect matchings, it was shown that all perfect matchings of G form a hierarchical structure through a certain rotation transformation, which can be expressed by a directed rooted tree or semilattice. And a novel directed rooted tree structure of the set of perfect matchings of G is established and can be generated by designing an algorithm.