二部图最大匹配问题的分层网络优化模型  

Layered network optimization model for maximum matching problem of bipartite graph

作　　者：唐敏[1] 关健[1] 邓国强[1] 靳强 

机构地区：[1]桂林电子科技大学数学与计算科学学院,广西桂林541004 [2]柳林中学,湖北十堰442000

出　　处：《计算机工程与应用》2012年第36期90-94,共5页Computer Engineering and Applications

摘　　要：为解决二部图最大匹配问题,提出了分层网络及网络逆序的概念,在此基础上建立了一种分层网络优化模型及其算法。给出了算法的思想、步骤、实例、时间复杂度分析,概述了求解二部图最大匹配问题的常见算法,与分层网络优化算法进行比较。实验验证,算法可读性强,易于理解和操作,在解决大规模二部图最大匹配问题时具有良好的性能。In order to solve the maximum matching reversed network order are proposed. On this basis, problem of bipartite graph, the concepts of layered network and a layered network model and an algorithm are established. The algorithm is given the idea, steps, examples, analysis of time complexity. The general algorithms are summarized and given the comparison with layered network optimization algorithm. Experiments show that this algorithm is readable, easy to understand and put into operation, with super properties in solving large-scale problem. It also has a good performance with computational complexity.

关 键 词：二部图 最大匹配 分层网络 网络逆序 广度优先 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]