摘要
定义了简单图匹配边的匹配优先指数、竞争集、匹配余集及匹配余图等重要概念,从最大匹配的定义及匹配边与非匹配边的竞争关系着手,在图的关联矩阵基础上,提出了求无权简单图最大匹配的一种操作简单、编程容易的新算法——"表单作业法".
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.
出处
《四川师范大学学报（自然科学版）》
CAS
CSCD
北大核心
2012年第4期478-481,共4页
Journal of Sichuan Normal University（Natural Science）
基金
国家自然科学基金(61079022)资助项目
中国民航飞行学院科研基金(J2010-44和J2010-48)
关键词
简单图
关联矩阵
最大匹配
表单作业法
simple graph
correlation matrix
maximum matching
form-operating method
