最大匹配图的围长(英文)  

The Girth of the Maximum Matching Graph

作　　者：刘岩[1] 林诒勋[2] 黄玉琴[2] 王世英[2] 

机构地区：[1]山东大学数学院,济南250100 [2]郑州大学系统科学与数学系,郑州450052

出　　处：《运筹学学报》2001年第1期13-20,共8页Operations Research Transactions

摘　　要：将一个图的所有最大匹配作为顶点集，称两个最大匹配相邻，若它们之一通过交换一条边得到另一个，由此所得图为该图的最大匹配图．本文研究了最大匹配图的围长，从而给出了最大匹配图是树或完全图的条件．The maximum matching graph of a graph has a vertex for each maximum matching and an edge for each pair of maximum matchings one of which can be transformed to another by exchanging an edge. In this paper, the girth of the maximum matching graph is studied. As a result, the conditions of the maximum matching graph being a tree or a complete graph axe obtained.

关 键 词：最大匹配 最大匹配图 围长 图 顶点集 树 完全图 

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