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

Layered network optimization model for maximum matching problem of bipartite graph

为解决二部图最大匹配问题,提出了分层网络及网络逆序的概念,在此基础上建立了一种分层网络优化模型及其算法。给出了算法的思想、步骤、实例、时间复杂度分析,概述了求解二部图最大匹配问题的常见算法,与分层网络优化算法进行比较。实验验证,算法可读性强,易于理解和操作,在解决大规模二部图最大匹配问题时具有良好的性能。

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.