| 关于简单图最大匹配的矩阵算法研究 |
| |
| 引用本文： | 段春生,庄刘.关于简单图最大匹配的矩阵算法研究[J].四川师范大学学报(自然科学版),2012,35(4):478-481. |
| |
| 作者姓名： | 段春生 庄刘 |
| |
| 作者单位： | 中国民航飞行学院计算机学院,四川广汉,618307 |
| |
| 摘 要： | 定义了简单图匹配边的匹配优先指数、竞争集、匹配余集及匹配余图等重要概念,从最大匹配的定义及匹配边与非匹配边的竞争关系着手,在图的关联矩阵基础上,提出了求无权简单图最大匹配的一种操作简单、编程容易的新算法——"表单作业法".
|
| 关 键 词： | 简单图 关联矩阵 最大匹配 表单作业法 |
Research on Matrix Algorithm of the Greatest Matching of the Simple Graph |
| |
| DUAN Chun-sheng
,
ZHUANG liu.Research on Matrix Algorithm of the Greatest Matching of the Simple Graph[J].Journal of Sichuan Normal University(Natural Science),2012,35(4):478-481. |
| |
| Authors: | DUAN Chun-sheng ZHUANG liu |
| |
| Institution: | (College of Computer Science,Civil Aviation Flight College of China,Guanghan 618307,Sichuan) |
| |
| Abstract: | In this paper,for a simple graph the concepts of matching priority index of a matching edge,competitive set,matching coset and matching co-graph,etc,are defined.By using the definition of maximum matching and the competitive relation between matching and non-matching edges,based on the correlative matrix of a graph,a new algorithm named "form-operating method" is creatively proposed for non-weighted simple graphs.In using this method to calculate the maximum matching,the operation is simple and the programming is quite easy. |
| |
| Keywords: | simple graph correlation matrix maximum matching form-operating method |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
