| 偶图求最小覆盖的一种算法 |
| |
| 引用本文： | 张秀梅.偶图求最小覆盖的一种算法[J].辽宁工学院学报,2007,27(2):132-135. |
| |
| 作者姓名： | 张秀梅 |
| |
| 作者单位： | 辽宁工学院数理科学系 辽宁锦州121001 |
| |
| 基金项目： | 辽宁省教育厅科研计划资助项目(05L187) |
| |
| 摘 要： | 以Konig定理作为理论基础,分析偶图的任一最大匹配的饱和顶点集与其任一最小覆盖的关系,得出偶图的任一最小覆盖都包含在该偶图的任一最大匹配的饱和顶点集中的结论。并利用此结论寻求到从偶图的非饱和顶点出发,利用偶图最大匹配求出偶图最小覆盖的一种算法。
|
| 关 键 词： | 偶图 最大匹配 最小覆盖 Konig定理 多项式时间算法 |
| 文章编号： | 1005-1090(2007)02-0132-04 |
| 修稿时间： | 2006-11-08 |
Minimum Covering Algorithm on Bipartite Graph |
| |
| ZHANG Xiu-mei.Minimum Covering Algorithm on Bipartite Graph[J].Journal of Liaoning Institute of Technology(Natural Science Edition),2007,27(2):132-135. |
| |
| Authors: | ZHANG Xiu-mei |
| |
| Abstract: | On the basis of Konig theorem,the relations between the vertices set of M-saturated(M is any maximum matching set of a bipartite graph G)and any minimum covering set of a bipartite graph G,were analyzed.The conclusion was found that in a bipartite graph G any minimum covering set was included in the vertices set which is M-saturated.Then harnessing the conclusion to find a algorithm that starting from the vertices of M-unsaturated and utilizing any maximum matching set M can find one of its minimum covering set in a bipartite graph. |
| |
| Keywords: | bipartite graph maximum matching minimum covering Konig theorem polynomial time algorithm |
| 本文献已被 CNKI 维普 等数据库收录！ |
