求二部图的最大匹配图的一种算法  

An Algorithm for Constructing the Maximum Matching Graphs on Bigraphs

作　　者：李晶[1] 王世英[1] 

机构地区：[1]山西大学数学科学学院,山西太原030006

出　　处：《电子学报》2010年第1期161-166,共6页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60773131);山西省自然科学基金(No.2008011010)

摘　　要：一个图的最大匹配图是以这个图的最大匹配集作为顶点集,两个顶点相邻当且仅当这两个最大匹配恰有一条边不同.本文首先对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.

关 键 词：最大匹配图 二部图 算法 

分 类 号：O157.6[理学—数学]