| 求二部图的最大匹配图的一种算法 |
| |
| 引用本文： | 李晶,王世英. 求二部图的最大匹配图的一种算法[J]. 电子学报, 2010, 38(1): 161-166 |
| |
| 作者姓名： | 李晶 王世英 |
| |
| 作者单位： | 山西大学数学科学学院,山西太原,030006;山西大学数学科学学院,山西太原,030006 |
| |
| 基金项目： | 国家自然科学基金(No.60773131);;山西省自然科学基金(No.2008011010) |
| |
| 摘 要： | 一个图的最大匹配图是以这个图的最大匹配集作为顶点集,两个顶点相邻当且仅当这两个最大匹配恰有一条边不同.本文首先对Gallai Edmonds结构定理中的三部分顶点在二部图中进行了详细刻画.然后讨论了构造最大匹配图问题的计算复杂性.最后深入研究了二部图最大匹配图的结构性质并给出了构造二部图的最大匹配图的一种算法.
|
| 关 键 词： | 最大匹配图 二部图 算法 |
| 收稿时间： | 2008-01-03 |
An Algorithm for Constructing the Maximum Matching Graphs on Bigraphs |
| |
| LI Jing,WANG Shi-ying. An Algorithm for Constructing the Maximum Matching Graphs on Bigraphs[J]. Acta Electronica Sinica, 2010, 38(1): 161-166 |
| |
| Authors: | LI Jing WANG Shi-ying |
| |
| Affiliation: | School of Mathematical Sciences;Shanxi University;Taiyuan;Shanxi 030006;China |
| |
| Abstract: | 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 m... |
| |
| Keywords: | maximum matching graph bigraph algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《电子学报》浏览原始摘要信息 |
|
点击此处可从《电子学报》下载免费的PDF全文 |
