OALib Journal期刊
ISSN: 2333-9721
费用：99美元

投递稿件

查看量	下载量

相关文章
更多...

四川师范大学学报(自然科学版) 2012

关于简单图最大匹配的矩阵算法研究

, PP. 478-481

段春生,庄刘

Keywords: 简单图,关联矩阵,最大匹配,表单作业法

Full-Text Cite this paper Add to My Lib

Abstract:

定义了简单图匹配边的匹配优先指数、竞争集、匹配余集及匹配余图等重要概念,从最大匹配的定义及匹配边与非匹配边的竞争关系着手,在图的关联矩阵基础上,提出了求无权简单图最大匹配的一种操作简单、编程容易的新算法——“表单作业法”.

References

[1]	Umeyama S. An eigendecomposition approach to weighted graph matching problem[J]. IEEE Trans Patt Anal Mach Intel,1988,10(5):695-703.
[2]	Almohamad H A, Duffuaa S O. A linear programming approach for the weighted graph matching problem[J]. IEEE Trans Patt Anal Mach Intel,1993,15(5):522-525.
[3]	Gold S, Rangarian A. A graduated assignment algorithm for graph matching[J]. IEEE Trans Patt Anal Mach Intel,1996,18(4):337-388.
[4]	Zavlanos M M, Pappas G J. A dynamical systems approach to weighted graph matching[J]. Automatica,2008,44(11):2817-2824.
[5]	Yuan J J. Induced matching extendable graph[J]. J Graph Theo,1998,28:203-313.
[6]	王勤,原晋江. 导出匹配可扩图的度和条件(英)[J]. 郑州大学学报:理学版,2000,32(1):19-21.
[7]	Rizzi R. A short proof of K？nig's Matching Theorem[J]. J Graph Theo,2000,33:138-139.
[8]	田俊华. 求二部图完全匹配的一种回溯算法[J]. 榆林学院学报,2003,13(3):14-15.
[9]	代西武,李群高. 求偶图最大匹配的矩阵算法[J]. 北京建筑工程学院学报,2002,18(3):75-78.
[10]	田晓明,朱绍文. 关于无向二部图最大匹配集矩阵算法的研究[J]. 湛江师范学院学报:自然科学版,2000,21(2):69-73.
[11]	钟声,云敏,焦安全. 求解单圈多部图的匹配算法[J]. 广西师范大学学报:自然科学版,2007,25(2):202-205.
[12]	毛华,庞双杰. Hall婚配定理的新证明方法[J]. 河北大学学报:自然科学版,2008,28(2):127-129.
[13]	Lovasz L, Plummer M. Matching Theory[M]. New York:North-Holland,1980.
[14]	Bondy J A, Murty U S R. Graph Theory with Applications[M]. London:Macmillan Press,1796.
[15]	赵静,但琦. 数学建模与数学实验[M]. 3版. 北京:高等教育出版社,2008.
[16]	耿素云,屈婉玲,张立昂. 离散数学[M]. 北京:清华大学出版社,2008.

Contact Us

service@oalib.com

WhatsApp +8615387084133