二部图最大匹配问题的分层网络优化模型 - 计算机工程与应用.pdf

90 2012 ，48 （36） Computer Engineering and Applications 计算机工程与应用 二部图最大匹配问题的分层网络优化模型 1 1 1 2 唐 敏 ，关 健 ，邓国强 ，靳 强 1 1 1 2 TANG Min , GUAN Jian , DENG Guoqiang , JIN Qiang 1.桂林电子科技大学 数学与计算科学学院，广西 桂林 541004 2.柳林中学，湖北 十堰 442000 1.School of Mathematics Computing Science, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China 2.Middle School of Liulin, Shiyan, Hubei 442000, China TANG Min, GUAN Jian, DENG Guoqiang, et al. Layered network optimization model for maximum match- ing problem of bipartite graph. Computer Engineering and Applications, 2012, 48 （36 ）：90-94. Abstract ：In order to solve the maximum matching problem of bipartite graph, the concepts of layered network and reversed network order are proposed. On this basis, 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 read- able, easy to understand and put into operation, with super properties in solving large-scale problem. It also has a good performance with computational complexity. Key words ：bipartite graphs; maximal matching; layered network; reversed network order; breadth first 摘 要：为解决二部图最大匹配问题，提出了分层网络及网络逆序的概念，在此基础上建立了一种分层网络优 化模型及其算法。给出了算法的思想、步骤、实例、时间复杂度分析，概述了求解二部图最大匹配问题的常见 算法，与分层网络优化算法进行比较。实验验证，算法可读性强，易于理解和操作，在解决大规模二部图最大 匹配问题时具有良好的性能。 关键词：二部图；最大匹配；分层网络；网络逆序；广度优先 文献标志码：A 中图分类号：TP3 doi ：10.3778/j.issn. 1002-8331.1105-0458 1 引言 提出了新的思路。将计算机的处理能力与良好的算 匹配问题是组合优化中得到较早研究的问题之 法相结合，是解决大规模理论及实际问题的一个有 [1] 效途径，特别是NP 难问题。二部图是一个非常有用 一 。许多实际问题可以转化为在一个二部图中寻 [2-4] 的理论模型，只要是诸如“工作安排”之类的问题都 求匹配 。譬如集合划分问题、不同类型的排序问 题、指派问题、边