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

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (36): 90-94.

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

唐敏1，关健1，邓国强1，靳强2

1.桂林电子科技大学数学与计算科学学院，广西桂林 541004
2.柳林中学，湖北十堰 442000

出版日期:2012-12-21 发布日期:2012-12-21

Layered network optimization model for maximum matching problem of bipartite graph

TANG Min1, GUAN Jian1, DENG Guoqiang1, JIN Qiang2

1.School of Mathematics & Computing Science, Guilin University of Electronic Technology, Guilin, Guangxi 541004, China
2.Middle School of Liulin, Shiyan, Hubei 442000, China

Online:2012-12-21 Published:2012-12-21

摘要/Abstract

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

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

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 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.

Key words: bipartite graphs, maximal matching, layered network, reversed network order, breadth first

唐敏1，关健1，邓国强1，靳强2. 二部图最大匹配问题的分层网络优化模型[J]. 计算机工程与应用, 2012, 48(36): 90-94.

TANG Min1, GUAN Jian1, DENG Guoqiang1, JIN Qiang2. Layered network optimization model for maximum matching problem of bipartite graph[J]. Computer Engineering and Applications, 2012, 48(36): 90-94.

[1]	陈平华，杨凯. 融合信任关系和用户项目二部图的推荐算法[J]. 计算机工程与应用, 2018, 54(4): 77-83.
[2]	张绍阳，曹家波，王子凡，曲卫东. 基于加权二部图匹配的中文段落相似度计算[J]. 计算机工程与应用, 2017, 53(18): 95-101.
[3]	朱艳辉，刘璟，徐叶强，田海龙，马进. 基于条件随机场的中文领域分词研究[J]. 计算机工程与应用, 2016, 52(15): 97-100.
[4]	徐梦1，杨博1，吕诗萌1，2，唐加福1，2，章宇1，2. 基于备选路径集的在线最短耗时公交换乘方法[J]. 计算机工程与应用, 2015, 51(9): 257-261.
[5]	周俊1，3，郑中华2，张炜3. 基于改进最大匹配算法的中文分词粗分方法[J]. 计算机工程与应用, 2014, 50(2): 124-128.
[6]	孙克辉1，陈艳山1，程巍1，张志强2. 网络层与链路层综合拓扑发现算法及其实现[J]. 计算机工程与应用, 2012, 48(4): 107-110.
[7]	陈昊，侯慧群，杨承志，邱磊. SA-BFSN：一种自适应基于密度聚类的算法[J]. 计算机工程与应用, 2012, 48(36): 186-189.
[8]	叶继平，张桂珠. 中文分词词典结构的研究与改进[J]. 计算机工程与应用, 2012, 48(23): 139-142.
[9]	李国和1，2，3，刘光胜1，2，3，秦波波1，2，3，吴卫江1，2，3，李洪奇1，2，3. 综合最大匹配和歧义检测的中文分词粗分方法[J]. 计算机工程与应用, 2012, 48(14): 139-142.
[10]	高红玉，赵学锋，王占华. 一种高效的最小连通支配集贪心算法[J]. 计算机工程与应用, 2012, 48(13): 89-93.
[11]	程传鹏. 网络评价倾向性研究[J]. 计算机工程与应用, 2011, 47(25): 156-159.
[12]	吴润秀. 基于粒计算的双权网络分层算法[J]. 计算机工程与应用, 2011, 47(24): 77-80.
[13]	闫小勇¹，尚艳亮². 基于二部图模型的公交网络路径搜索算法[J]. 计算机工程与应用, 2010, 46(5): 246-248.
[14]	史金成¹，胡学钢². 基于二部图的概念聚类研究[J]. 计算机工程与应用, 2010, 46(13): 132-134.
[15]	吴蓓，陈性元，张永福，代向东，彭军. 基于分层网络系统模型的多层策略生成和表示[J]. 计算机工程与应用, 2009, 45(31): 93-97.