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

• 作者: 李晶 王世英
• 来源期刊: 电子学报
• 学科: 数学
• 关键词: 最大匹配图 二部图 算法
• 年，卷（期）: 2010,（1）
• 所属期刊栏目: 学术论文
• 页码范围: 161-166
• 分类号: O157.6
• 字数: 6963字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王世英	山西大学数学科学学院	109	122	6.0	7.0
2	李晶	山西大学数学科学学院	16	125	6.0	11.0