摘要
给出了一个多部图及其匹配问题的定义,提出了求解单圈多部图匹配问题的一个算法。该算法提出多部图顶点间的可达性定义,并使用试探与缩小规模相结合的方法以及求二部图的最大匹配算法,求解单圈多部图的最大匹配问题。经过验证,算法的效率比较高。
The paper defines multi-partite graphs and matching problems for it, and defines the multi-partite graphs which including only one cycle, and discusses a method that to solve maximum matching problem of the multi-partite graphs which including only one cycle, suggest a algorithm that based on reachable of multi-partite graphs, and utilize one of the maximum matching problems algorithm of bipartite graph to find a maximum matching of the multi-partite graph which including only one cycle.
出处
《广西师范大学学报（自然科学版）》
CAS
北大核心
2007年第2期202-205,共4页
Journal of Guangxi Normal University:Natural Science Edition
基金
海南省自然科学基金资助项目(80636)
关键词
多部图
匹配问题
算法
multi-partite graphs
matching problems
algorithm
