偶图求最小覆盖的一种算法  

Minimum Covering Algorithm on Bipartite Graph

作　　者：张秀梅[1] 

机构地区：[1]辽宁工学院数理科学系,辽宁锦州121001

出　　处：《辽宁工学院学报》2007年第2期132-135,共4页Journal of Liaoning Institute of Technology(Natural Science Edition)

基　　金：辽宁省教育厅科研计划资助项目(05L187)

摘　　要：以Konig定理作为理论基础,分析偶图的任一最大匹配的饱和顶点集与其任一最小覆盖的关系,得出偶图的任一最小覆盖都包含在该偶图的任一最大匹配的饱和顶点集中的结论。并利用此结论寻求到从偶图的非饱和顶点出发,利用偶图最大匹配求出偶图最小覆盖的一种算法。On the basis of Konig theorem, the relations between the vertices set ot 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.

关 键 词：偶图 最大匹配 最小覆盖 Konig定理 多项式时间算法 

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