| 求解单圈多部图的匹配算法 |
| |
| 引用本文： | 钟声,云敏,焦安全.求解单圈多部图的匹配算法[J].广西师范大学学报(自然科学版),2007,25(2):202-205. |
| |
| 作者姓名： | 钟声 云敏 焦安全 |
| |
| 作者单位： | 海南大学,信息科学技术学院,海南,海口,570228 |
| |
| 摘 要： | 给出了一个多部图及其匹配问题的定义,提出了求解单圈多部图匹配问题的一个算法。该算法提出多部图顶点间的可达性定义,并使用试探与缩小规模相结合的方法以及求二部图的最大匹配算法,求解单圈多部图的最大匹配问题。经过验证,算法的效率比较高。
|
| 关 键 词： | 多部图 匹配问题 算法 |
| 文章编号： | 1001-6600（2007）02-0202-04 |
| 收稿时间： | 2006-12-15 |
| 修稿时间： | 2006-12-15 |
Algorithm for Matching Problems of Multi-partite Graphs Which Include One Cycle |
| |
| ZHONG Sheng,YUN Min,JIAO An-quan.Algorithm for Matching Problems of Multi-partite Graphs Which Include One Cycle[J].Journal of Guangxi Normal University(Natural Science Edition),2007,25(2):202-205. |
| |
| Authors: | ZHONG Sheng YUN Min JIAO An-quan |
| |
| Institution: | College of Information Science and Technology,Hainan University,Haikou 570228,China |
| |
| Abstract: | The paper defines multi-partite graphs and matching problems for it,and defines the multi-partite graphs which including only one cycle,and discusses a method that to solve maximum matching problem of the multi-partite graphs which including only one cycle,suggest a algorithm that based on reachable of multi-partite graphs,and utilize one of the maximum matching problems algorithm of bipartite graph to find a maximum matching of the multi-partite graph which including only one cycle. |
| |
| Keywords: | multi-partite graphs matching problems algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
