一种求解二部图最大匹配问题新算法及其应用  

A New Algorithm and Application of Solving Maximum Matching Problem of Bipartite Graph

作　　者：唐敏[1] 关健[1] 邓国强[1] 王海刚[2] 

机构地区：[1]桂林电子科技大学数学与计算科学学院,桂林541004 [2]桂林电子科技大学商学院,桂林541004

出　　处：《计算机系统应用》2012年第3期72-75,28,共5页Computer Systems & Applications

摘　　要：提出了解决二部图最大匹配问题的分层网络优化算法,并应用新算法对排课问题进行求解。定义了分层网络的概念及匹配的规则,结合广度优先搜索策略生成分层网络体系,然后按网络逆序找出最大匹配。实验表明,算法在解决大规模二部图最大匹配的理论问题和实际应用问题时均能获得准确的结果,具备良好的性能。This paper proposed an algorithm for maximum matching of Bipartite graph based on layered network model. Timetable Problems are solved by the new algorithm. A matching rule for layered networks is defined and proposed a concept of layered network first, and a layered network system is generated with the breadth first search strategy. Maximal matching is found according reversed network order. Experiments show that this algorithm can get accurate results and has a good performance with computational complexity in solving large-scale theoretical and practical maximum matching problems of bipartite graph.

关 键 词：分层网络 二部图 最大匹配 排课问题 

分 类 号：O157.5[理学—数学] TP301.6[理学—基础数学]