一种新的图同构判定算法
|
摘要
图的同构判定是图论学科中诸多难题之一,由于它在模式识别、人工视觉、电路分析、分子结构等很多领域有着广泛的应用,因此该问题是值得研究的重要课题。
目前理论上还无法证明图的同构问题究竟属于NP—完全问题还是P问题。众多学者对该问题予以关注和研究,提出了多种同构判定算法。目前国际上比较好的算法主要有Ul 1mann算法、SD算法、VF算法和Nauty算法等。这些算法基本上都是基于搜索过程的,即在寻找同构的过程中将顶点进行细分,然后基于这些细分子集展开搜索,通过搜索得到图的顶点对应关系来判定同构。总体来说,这些算法都对特定种类的图有较好的判定效率,对于上千个顶点的图,能够在可以接受的时间内完成判定,但对其它种类的图则会失效,适用范围都较为有限。
本文以独特的视角对图的同构判定问题展开了研究。提出了一种新的同构判定算法:电路模拟法,即将图的同构问题转化为电路的相同问题。以此获得的同构判定算法在大多数情况下可有效判定两图是否同构。本课题的研究为图的同构判定及其实际应用提供了新的理论与方法。
本文主要完成了以下工作:
1)提出了电路模拟法所涉及的新概念:相同电路、图的伴随电路、全激励、节点电压序列以及节点电压序列集。给出了无向图的伴随电路模型。推导并证明了算法的理论依据。
2)提出了可应用于无向图同构判定的电路模拟法的基本算法,并在matlab环境下实现了该算法。
3)给出了混合图的伴随电路模型,将电路模拟法扩展到混合图的同构判定上。
4)进一步提出了改进的电路模拟法。
5)利用改进的电路模拟法对目前国际流行的测试图库进行了测试,而且和目前已有算法中表现较好的Nauty算法做了比较。测试表明,本算法在对几类常见图的同构判定中表现优于Nauty算法,而且可以适用于无向图、有向图及混合图等多种类型的图。
6)最后给出了电路模拟法在应用领域的成功应用实例,指出了电路模拟法的应用价值。
The graph isomorphism judgement is one of the hard problems in graph theory. As graph isomorphism judgement has been widely used in pattern recognition, computer vision, circuit analysis, molecule structure and many other related fields, it is a significant problem which is deserved to be researched.
As it is well known, the graph isomorphism problem is one of a very small number of problems neither known to be solvable in polynomial time nor NP-complete. The problem attracts many researchers' attentions and participations, for which various algorithms have been proposed. Currently, Ullmann algorithm, SD algorithm, VF algorithm, and Nauty algorithm are relatively good algorithms in the world. These algorithms are all based on a searching process, in which vertexes are refined first, and then the correspondence between vertexes is obtained through the searching process. As a whole, each of these algorithms performs efficiently on the judgement of certain kinds of graphs, which can finish the isomorphism judgement of graphs with 1000 vertexes within an acceptable time frame. However, all these algorithms are only efficient for certain kinds of graphs and will fail to judge other kinds of graphs.
A novel method, the circuit simulation algorithm, is proposed here, which transfers the graph isomorphism problem into the identical circuits problem. Most of the time, the algorithm, based on the proposed theory, is efficient to judge graph isomorphism. Thus the research of the topic provides a new theory and algorithm for graph isomorphism judgement and its applications.
The following jobs have been completed in the thesis:
1) New concepts about this algorithm are proposed, including identical circuits, adjoint circuits of graphs, full stimulation, node voltage sequence, and collection of node voltage sequences. Then the adjoint circuit model of an undirected graph is established. Finally the theoretical conditions for judging graph isomorphism are analyzed and proved.
2) A new algorithm, the circuit simulation algorithm, is proposed and then the complete matlab program is implemented.
3) The adjoint circuit model of a mixed graph is established and then the algorithm is extended to mixed graph isomorphism judgement.
4) The improved version of the circuit simulation algorithm is proposed.
5) The improved circuit simulation algorithm is tested on the popular graph database in the world and then the performance comparison of the algorithm with that of the existing algorithm, the Nauty algorithm which is relatively efficient, is performed. Simulation results demostrate that the circuit simulation algorithm performs better and it is applicable to more kinds of graphs, such as undirected graphs, directed graphs, and mixed graphs.
6) At the end of the article, the applications of the algorithm in several fields are described and the value of the method is pointed out.
目前理论上还无法证明图的同构问题究竟属于NP—完全问题还是P问题。众多学者对该问题予以关注和研究,提出了多种同构判定算法。目前国际上比较好的算法主要有Ul 1mann算法、SD算法、VF算法和Nauty算法等。这些算法基本上都是基于搜索过程的,即在寻找同构的过程中将顶点进行细分,然后基于这些细分子集展开搜索,通过搜索得到图的顶点对应关系来判定同构。总体来说,这些算法都对特定种类的图有较好的判定效率,对于上千个顶点的图,能够在可以接受的时间内完成判定,但对其它种类的图则会失效,适用范围都较为有限。
本文以独特的视角对图的同构判定问题展开了研究。提出了一种新的同构判定算法:电路模拟法,即将图的同构问题转化为电路的相同问题。以此获得的同构判定算法在大多数情况下可有效判定两图是否同构。本课题的研究为图的同构判定及其实际应用提供了新的理论与方法。
本文主要完成了以下工作:
1)提出了电路模拟法所涉及的新概念:相同电路、图的伴随电路、全激励、节点电压序列以及节点电压序列集。给出了无向图的伴随电路模型。推导并证明了算法的理论依据。
2)提出了可应用于无向图同构判定的电路模拟法的基本算法,并在matlab环境下实现了该算法。
3)给出了混合图的伴随电路模型,将电路模拟法扩展到混合图的同构判定上。
4)进一步提出了改进的电路模拟法。
5)利用改进的电路模拟法对目前国际流行的测试图库进行了测试,而且和目前已有算法中表现较好的Nauty算法做了比较。测试表明,本算法在对几类常见图的同构判定中表现优于Nauty算法,而且可以适用于无向图、有向图及混合图等多种类型的图。
6)最后给出了电路模拟法在应用领域的成功应用实例,指出了电路模拟法的应用价值。
The graph isomorphism judgement is one of the hard problems in graph theory. As graph isomorphism judgement has been widely used in pattern recognition, computer vision, circuit analysis, molecule structure and many other related fields, it is a significant problem which is deserved to be researched.
As it is well known, the graph isomorphism problem is one of a very small number of problems neither known to be solvable in polynomial time nor NP-complete. The problem attracts many researchers' attentions and participations, for which various algorithms have been proposed. Currently, Ullmann algorithm, SD algorithm, VF algorithm, and Nauty algorithm are relatively good algorithms in the world. These algorithms are all based on a searching process, in which vertexes are refined first, and then the correspondence between vertexes is obtained through the searching process. As a whole, each of these algorithms performs efficiently on the judgement of certain kinds of graphs, which can finish the isomorphism judgement of graphs with 1000 vertexes within an acceptable time frame. However, all these algorithms are only efficient for certain kinds of graphs and will fail to judge other kinds of graphs.
A novel method, the circuit simulation algorithm, is proposed here, which transfers the graph isomorphism problem into the identical circuits problem. Most of the time, the algorithm, based on the proposed theory, is efficient to judge graph isomorphism. Thus the research of the topic provides a new theory and algorithm for graph isomorphism judgement and its applications.
The following jobs have been completed in the thesis:
1) New concepts about this algorithm are proposed, including identical circuits, adjoint circuits of graphs, full stimulation, node voltage sequence, and collection of node voltage sequences. Then the adjoint circuit model of an undirected graph is established. Finally the theoretical conditions for judging graph isomorphism are analyzed and proved.
2) A new algorithm, the circuit simulation algorithm, is proposed and then the complete matlab program is implemented.
3) The adjoint circuit model of a mixed graph is established and then the algorithm is extended to mixed graph isomorphism judgement.
4) The improved version of the circuit simulation algorithm is proposed.
5) The improved circuit simulation algorithm is tested on the popular graph database in the world and then the performance comparison of the algorithm with that of the existing algorithm, the Nauty algorithm which is relatively efficient, is performed. Simulation results demostrate that the circuit simulation algorithm performs better and it is applicable to more kinds of graphs, such as undirected graphs, directed graphs, and mixed graphs.
6) At the end of the article, the applications of the algorithm in several fields are described and the value of the method is pointed out.
引文
[1]N.Deo,Graph Theory with Applications to Engineering and Computer Science.[M]Englewood Cliffs,N J:Prentice-Hall,1974.
[2]陈树柏,左垲,张良震.网络图论及其应用[M],北京:科学出版社,1982:176-181。
[3]Maurer,P.M.;Schapira,A.D.A logic-to-logic comparator for VLSI layout verification.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems[J].1988,7(8):897-907.
[4]左垲等.图论应用的新进展(译文集)[M].北京:中国电子学会,1989。
[5]H.Ehrig.Introduction to Graph Grammars with Applications to Semantic Networks[J].Comput.Math,1992,23(1):557-572.
[6]E.K.Wong,Model matching in robot vision by sub-graph isomorphism[J],Pattern Recognition,1992,25(3):287-304.
[7]J.Rocha and T.Pavlidis.A Shape Analysis Model With Applications to a Character Recognition System[J].IEEE Trans.Pattern Analysis and Machine Intelligence.1994,16(4):393-404.
[8]Kureichik V.,Tetelbaum A.,Graph Isomorfizm Algorithm for Regular VLSI Structure[In],Proc.28th Annual conf.in Information Sciences and systems,Prineenton,USA,1994:17-23.
[9]W.J.Christmas,J.Kittler,and M.Petrou.Structural Matching in Computer Vision Using Probabilistic Relaxation.[J]IEEE Trans.Pattern Analysis and Machine Intelligence.1995,17(1):749-764.
[10]兰家隆,刘军,应用图论及算法[M],成都:电子科技大学出版社,1995:230-235。
[11]Huang,K.-T.;Overhauser,D.A novel graph algorithm for circuit recognition(In);Circuits and Systems,1995.ISCAS '95.,1995 IEEE International Symposium on Volume 3,28 April-3 May 1995:1695-1698.
[12]X.Jiang,H.Bunke,Including geometry in graph representations:a quadratic time isomorphism algorithm and its applications(In),in Perner,P.,Wang,P.,Rosenfeld,A.(eds.):Advances in Structural and Syntactic Pattern Recognition,Springer Verlag,Lecture Notes in Computer Science 1121,1996:110-119.
[13]李锋,周新伦.甲骨文自动识别的图论方法[J].电子科学学刊,1996,18(S1):41-47.
[14]张培玉,金德闻,李瑰贤.平面运动链同构识别方法的研究[J].机械科学与技术.1997,16(1):95-99.
[15]K.Shearer,H.Bunke S.Venkatesh,D.Kieronska,Efficient Graph Matching for Video Indexing[J],Computing suppl.1998,12:53-62.
[16]M.Abdulrahim,M.Misra,A Graph Isomorphism Algorithm for Object Recognition[J],PattemAnalysis and Applic.1998,1(3):189-201,
[17]Li Feng,Woo Peng— Yung.Chinese signature verification:the topological approach and waveform matching approach[J].International Joumal of Imaging Systems and Technology.1999,10(4):355-361.
[18]L.P.Cordella and M.Vento.Symbol Recognition in Documents:A Collection of Techniques?[J].Document Analysis and Recognition.2000,3(3):73-88.
[19]Cordella,LP;Foggia,P;Sansone,C.Fast graph matching for detecting CAD image components.5th International Conference on Pattern Recognition (ICPR-2000),SEP 03-07,2000 BARCELONA SPAIN.15TH INTERNATIONAL CONFERENCE ON PATTERN RECOGNITION,VOL 2,PROCEEDINGS.2000:1034-1037.
[20]Foggia P,Genna R,Vento M.Introducing Generalized Attributed Relational Graphs(GARG's)as Prototypes of ARG'sin Graph-based Representations in Pattern Recognition[In].Kropatsch and Jolion eds,Vienna:Hosterreichische Computer Gesellschaft,2000:183-192.
[21]许禄,胡昌玉.应用化学图论[M].北京:科学出版社,2000.
[22]J.Liu and Y.T.Lee.A Graph-Based Method for Face Identification from a Single 2D Line Drawing[J].IEEE Trans.Pattern Analysis and Machine Intelligence.2001,23(10):1106-1119.
[23]J.Lados,E.Marti,and J.J.Villanueva.Symbol Recognition by Error-Tolerant Subgraph Matching between Region Adjacency Graphs[J].IEEE Trans.Pattern Analysis and Machine Intelligence.2001,23(10):1137-1143.
[24]洪家娣.一种识别运动链同构的新方法[J].机械设计,2001,1(11):21-23.
[25]李瑛,周家驹.VF算法在化学结构检索中的应用[J].计算机与应用化学,2002,19(5):575-580.
[26]T.A.Meynard,H.Foch,F.Forest,C.Turpin,F.Richardeau,L.Delmas,G.Gateau,E.Lefeuvre.Multicell converters:derived topologies[J].IEEE Trans.on Industrial Electronics.2002,49(5):978-987.
[27]王京梅,兰中文,余忠,王豪才零电压一零电流PWM软开关技术研究[J].电 子器件,2002,25(4):340-344.
[28]Meynard TA,FochH,ForestF.Multi-cell converters:derived topologies[J]-IEEE Trans.On Industrial Electronic,2002,49(5):978-987.
[29]石勇,杨旭,何群,王兆安.同构混合开关拓扑的辨识[J].中国电机工程学报,2003,23(11):117-121.
[30]Lados,J.;Sanchez,G.Symbol recognition using graphs[In];Image Processing,2003.ICIP 2003.Proceedings.2003 International Conference on Volume 2,14-17 Sept.2003 Page(s):Ⅱ-49-52.
[31]D.Conte,P.Foggia,C.Sansone,and M.Vento.Thirty Years of Graph Matching in Pattern Recognition[J].Pattern Recognition and Artificial Intelligence,2004,18(3):265-298.
[32]Bambha,N.K.;Bhattacharyya S.S.,Joint application mapping/interconnect synthesis techniques for embedded chip-scale multiprocessors[J].IEEE Transactions on Parallel and Distributed Systems[J].2005,16(2):99-112.
[33]J.Lee,J.Oh,and S.Hwang.Clustering of Video Objects by Graph Matching[In].Proc.of 2005 IEEE International Conference on Multimedia and Expo(ICME2005)Amsterdam,Netherlands,July 6-8,2005.
[34]Kumar,Y.;Gupta,P.An External Memory Circuit Validation Algorithm for Large VLSI Layouts[In];VLSI,2007.ISVLSI '07.IEEE Computer Society Annual Symposium on 9-11 March 2007:510-511.
[35]Dehmer,M;Mehler,A.New method of measuring similarity for a special class of directed graphs[In].Czech-Slovak Conference on Graphs.MAY 23-28,2004Vysne Ruzbachy SLOVAKIA.GRAPHS '04.2007:39-59.
[36]Al-Zabi,B.R.A.;Kernytskyy,A.;Lobur,M.;Tkatchenko,S.On graph isomorphisna determining problem;Perspective Technologies and Methods in MEMS Design[J],2008.MEMSTECH 2008.International Conference on 21-24May 2008 Page(s):84-84.
[37]Asadpour,M;Sproewitz,A;Billard,A,et al.Graph Signature for Self-Reconfiguration Planning[In].IEEE/RSJ International Conference on Intelligent Robots and Systems,SEP 22-26,2008 Nice FRANCE.2008IEEE/RSJ INTERNATIONAL CONFERENCE ON ROBOTS AND INTELLIGENT SYSTEMS,VOLS 1-3,CONFERENCE PROCEEDINGS.2008:863-869
[38]Ai-Zabi,BRA;Kernytskyy,A;Lobur,M,et al..On graph isomorphism determining problem[In].th Intemational Conference of Young Scientists (MEMSTECH 2008),MAY 21-24,2008 Polyana UKRAINE.PERSPECTIVE TECHNOLOGIES AND METHODS IN MEMS DESIGN.2008:84-84.
[39]Golovin,A;Henrick,K.Chemical Substructure Search in SQL[J].journal of chemical information and modeling.2009,49(1):22-27.
[40]Garey,Michael R.& Johnson,David S.Computers and Intractability:A Guide to the Theory ofNP-Completeness[M].1979.
[41]F.Harary著,李慰萱译.图论[M],上海:上海科学技术出版社,1981.
[42]D.G.Comeil,C.C.Gotlieb,An efficient algorithm for graph isomorphism[J],Journal of the Association for Computing Machinery.1970,17:51-64.
[43]J.Hopcrofl,J.Won& Linear time algorithm for isomorphism of planar graphs[In],Proc.6th Annual ACM Symp.Theory of Compuling,pp.172-184,1974.
[44]G.S.Leuker and K.S.Booth,“A linear time algorithm for deciding interval graph isomorphism[J],” J.Ass.Comput.Mach.,Apr.1979,26:183-185.
[45]J.R.Ullmann.An Algorithm for Subgraph Isomorphism[J].Journal of the Association for Computing Machinery,1976,23(1):31-42.
[46]A.V.Aho,J.E.Hopcroft,J.D.Ullman,The design and analysis of computer Algorithms[M],Addison Wesley,1974.
[47]D.C.Schmidt,L.E.Druffel,A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices,Journal of the Association for Computing Machinery,1976(23):433-445.
[48]E.M.Luks,Isomorphism of Graphs of bounded valence can be tested in polynomial time,Journal of Compurer Sysrem Science,1982:42-65.
[49]L.P.Cordella,P.Foggia,C.Sansone,M.Vento.Evaluating Performance of the VF Graph Matching Algorithm[In].Proc.of the 10th International Conference on Image Analysis and Processing,IEEE Computer Society Press,1999:1172-1177.
[50]B.D.McKay,Practical Graph Isomorphism[M],Congressus Numerantium,1981,30(1):45-87.
[51]马颂德,神经网络与组合优化[A].中国神经网络首届学术大会论文集,C2N2—90,北京:1990,22-28.
[52]陈国良,神经网络用于求解组合优化问题[A].中国神经网络首届学术大会论文集,C2N2—90,北京:1990,122-129.
[53]梁维发等,用神经网络求解一些困难的图论问题[A].中国神经网络首届学术大会论文集,C2N2—90,北京:1990,924-927.
[54]Agusa,K.,Fujita,S.,Yamashita,M.,Ae,T.On neural networks for graph isomorphism problem[In].Neuroinformatics and Neurocomputers,RNNS/IEEE Symposium on Volume.Rostov-on-Don,Russia:1992:1142-1148.
[55]许进,张军英,保铮.基于Hopfield网络的图的同构算法[J].电子科学学刊,1996,VOL18(12):116-121.
[56]DePiero F.Trivedi M.Graph matching using a direct classification of node attendance[J].Pattern Recognition.1996,29(6):1031-1048.
[57]C.M.Hoffman,Croup-rheoreric AIgorirhms and Graph Isomorphism[M],Springer,Berlin,1998.
[58]B.T.Messmer,H.Bunke,A decision tree approach to graph and subgraph isomorphism detection[J].Pattern Recognition.1999,32(1):1979-1998.
[59]Warnaar D.B.,Chew M.,Olarin S.Method for detecting isomorphism in graphs using vertex degree correspondence with partitioning[J].American society of Mechanical Engineers,DE,1993,47:219-224.
[60]李锋,李晓艳.图的同构判定算法关联度序列法及其应用[J].复旦学报(自然科学版),2001,40(3):318-325.
[61]李锋,商慧亮.有向图的同构判定算法-出入度序列法[J].应用科学学报,2002,20(3):258-260.
[62]Cordelia LP,Foggia P,Sansone C,Vento M.An improved algorithm for matching large graphs.In:Jolion JM,Kropatsch W,Vento M,eds.Proc.of the 3rd IAPR-TC15 Int'l Workshop on Graph-Based Representation in Pattern Recognition.Ischia,2001.149-159.http://amalfi.dis.unina.it/graph/db/papers/vf-algorithm.pdf.
[63]P.Foggia,C.Sansone,M.Vento.A Performance Comparison of Five Algorithms for Graph Isomorphism[in].Proceedings of International Workshop on Graph-based Representation in Pattern Recognition.2001:188-199.
[64]Foggia P,Sansone C,Vento M.A database of graphs for isomorphism and sub-graph isomorphism benchmarking[In].Jolion JM,Kropatsch W,Vento M,eds.Proc.of the 3rd IAPR-TC15 Int'l Workshop on Graph-Based Representation in Pattern Recognition.Ischia,2001:176-187.http://amalfi.dis.unina.it/graph/db/papers/database.pdf.
[65]Kelly AR,Hancock ER.Graph matching using adjacency matrix Markov chain[in].Cootes TF,Taylor C,eds.Proc.of the British Machine Vision Conf.2001,BMVC 2001.Manchester:British Machine Vision Association.2001: 383-390.
[66]Kukluk J.Algorithm and experiments in testing planar graphs for isomorphism[J].Journal of Graph Algorithms and Applications.2004,8(3):313-356.
[67]Oliveira M,Greve F.A new refinement procedure for graph isomorphism algorithms[In].Feofiloff P,de Figueiredo CMH,Wakabayashi Y,eds.Electronic Notes in Discrete Mathematics,Proc.of the GRACO 2005.Amsterdam:Elsevier North-Holland,2005:373-379.
[68]Bao Ngoc Tran;Thuc Dinh Nguyen.An Efficient Algorithm for Isomorphic Problem on Generic Simple Graphs Modeling & Simulation[In].2008.AICMS 08.Second Asia International Conference on 13-15 May 2008 Page(s):824-829
[69]Zahidi,U.A..Spectral Solution for Detecting Isomorphic Graphs with Nondegenerate Eigenvalues[in].Multitopic Conference,2007.INMIC 2007.IEEE International 28-30 Dec.2007:1-4.
[70]Battiti,R;Mascia,F,An algorithm portfolio for the sub-graph isomorphism problem[in].International Workshop on Stochastic Local Search Algorithms.SEP 06-08,2007 Brussels BELGIUM.Engineering Stochastic Local Search Algorithms:Designing,Implementing and Analyzing Effective Heuristics.2007:106-12.
[71]Huaan Wu.An Invariant of the Graph Isomorphism[in].Computational Intelligence and Industrial Application,2008.PACIIA '08.Pacific-Asia Workshop on Volume 2,19-20 Dec.2008 Page(s):307-310.
[72]Lin,MC;Soulignac,FJ;Szwarcfiter,JL.A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs[J].11th Scandinavian Workshop on Algorithm Theory(SWAT 2008.JUL 02-04,2008 Gothenburg SWEDEN.ALGORITHM THEORY-SWAT 2008.2008:355-366.
[73]J.A.Bondy,U.S.R.Murty.吴望名等译图论及其应用.科学出版社.1984.4
[74]潘双来.电路理论基础(第2版)[M]北京:清华大学出版社,2007.
[75]杨廷力.机械系统基本理论一结构学.运动学,动力学北京:机械工业出版社,1995:1-69.
[76]李团结,曹惟庆.利用邻接矩阵的幂序列进行运动链和机构的同构判定[J].机械科学与技术,1998,17(1):11-14。
[77]丁华锋.运动链的环路理论与同构判别及图谱库的建立[D].燕山大学,2007.
[78]尹玉英.有机化学[M].北京:烃加工出版社,1990.
[79]王京梅,兰中文,余忠,王豪才零电压一零电流PWM软开关技术研究[J].电子器件,2002,25(4):340-344.
[80]商慧亮,李锋.非线性代数方程组的信号流图解法及应用[J].应用科学学报.2004,22(2):173-178.
[81]商慧亮,李锋.二次物理分解法——一种大规模非线性电阻网络的并行分析方法[J].复旦学报[J].2003,42(1):29-34.
[82]李锋,商慧亮.节点撕裂信号流图法[J].复旦学报.2003,42(1):24-29.
[83]李锋,商慧亮.线性模拟集成电路故障测试与诊断:短路导纳参数法[J].应用科学学报[J].2001,19(3):228-232.
[84]Feng Li,Huiliang Shang,Peng-Yung Woo.Determination of Isomorphism and Its Applications for Arbitrary Graphs Based on Circuit Simulation[J].Circuits,Systems,and Signal Processing.2008,27(5):749-761.(SCI ISI:000259859900011EREF).
[85]商慧亮,李锋.图的同构判定算法:电路模拟法[A].图论与系统优化专业委员会学术年会论文集[C],哈尔滨,2005:56-63.
[86]Huiliang Shang,Feng Li,Peng-Yung Woo.An Important Property of Isomorphic Graphs and Its Application.投送IEEE Trans.Pattern Analysis and Machine Intelligence.通过初审,修改当中.
[2]陈树柏,左垲,张良震.网络图论及其应用[M],北京:科学出版社,1982:176-181。
[3]Maurer,P.M.;Schapira,A.D.A logic-to-logic comparator for VLSI layout verification.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems[J].1988,7(8):897-907.
[4]左垲等.图论应用的新进展(译文集)[M].北京:中国电子学会,1989。
[5]H.Ehrig.Introduction to Graph Grammars with Applications to Semantic Networks[J].Comput.Math,1992,23(1):557-572.
[6]E.K.Wong,Model matching in robot vision by sub-graph isomorphism[J],Pattern Recognition,1992,25(3):287-304.
[7]J.Rocha and T.Pavlidis.A Shape Analysis Model With Applications to a Character Recognition System[J].IEEE Trans.Pattern Analysis and Machine Intelligence.1994,16(4):393-404.
[8]Kureichik V.,Tetelbaum A.,Graph Isomorfizm Algorithm for Regular VLSI Structure[In],Proc.28th Annual conf.in Information Sciences and systems,Prineenton,USA,1994:17-23.
[9]W.J.Christmas,J.Kittler,and M.Petrou.Structural Matching in Computer Vision Using Probabilistic Relaxation.[J]IEEE Trans.Pattern Analysis and Machine Intelligence.1995,17(1):749-764.
[10]兰家隆,刘军,应用图论及算法[M],成都:电子科技大学出版社,1995:230-235。
[11]Huang,K.-T.;Overhauser,D.A novel graph algorithm for circuit recognition(In);Circuits and Systems,1995.ISCAS '95.,1995 IEEE International Symposium on Volume 3,28 April-3 May 1995:1695-1698.
[12]X.Jiang,H.Bunke,Including geometry in graph representations:a quadratic time isomorphism algorithm and its applications(In),in Perner,P.,Wang,P.,Rosenfeld,A.(eds.):Advances in Structural and Syntactic Pattern Recognition,Springer Verlag,Lecture Notes in Computer Science 1121,1996:110-119.
[13]李锋,周新伦.甲骨文自动识别的图论方法[J].电子科学学刊,1996,18(S1):41-47.
[14]张培玉,金德闻,李瑰贤.平面运动链同构识别方法的研究[J].机械科学与技术.1997,16(1):95-99.
[15]K.Shearer,H.Bunke S.Venkatesh,D.Kieronska,Efficient Graph Matching for Video Indexing[J],Computing suppl.1998,12:53-62.
[16]M.Abdulrahim,M.Misra,A Graph Isomorphism Algorithm for Object Recognition[J],PattemAnalysis and Applic.1998,1(3):189-201,
[17]Li Feng,Woo Peng— Yung.Chinese signature verification:the topological approach and waveform matching approach[J].International Joumal of Imaging Systems and Technology.1999,10(4):355-361.
[18]L.P.Cordella and M.Vento.Symbol Recognition in Documents:A Collection of Techniques?[J].Document Analysis and Recognition.2000,3(3):73-88.
[19]Cordella,LP;Foggia,P;Sansone,C.Fast graph matching for detecting CAD image components.5th International Conference on Pattern Recognition (ICPR-2000),SEP 03-07,2000 BARCELONA SPAIN.15TH INTERNATIONAL CONFERENCE ON PATTERN RECOGNITION,VOL 2,PROCEEDINGS.2000:1034-1037.
[20]Foggia P,Genna R,Vento M.Introducing Generalized Attributed Relational Graphs(GARG's)as Prototypes of ARG'sin Graph-based Representations in Pattern Recognition[In].Kropatsch and Jolion eds,Vienna:Hosterreichische Computer Gesellschaft,2000:183-192.
[21]许禄,胡昌玉.应用化学图论[M].北京:科学出版社,2000.
[22]J.Liu and Y.T.Lee.A Graph-Based Method for Face Identification from a Single 2D Line Drawing[J].IEEE Trans.Pattern Analysis and Machine Intelligence.2001,23(10):1106-1119.
[23]J.Lados,E.Marti,and J.J.Villanueva.Symbol Recognition by Error-Tolerant Subgraph Matching between Region Adjacency Graphs[J].IEEE Trans.Pattern Analysis and Machine Intelligence.2001,23(10):1137-1143.
[24]洪家娣.一种识别运动链同构的新方法[J].机械设计,2001,1(11):21-23.
[25]李瑛,周家驹.VF算法在化学结构检索中的应用[J].计算机与应用化学,2002,19(5):575-580.
[26]T.A.Meynard,H.Foch,F.Forest,C.Turpin,F.Richardeau,L.Delmas,G.Gateau,E.Lefeuvre.Multicell converters:derived topologies[J].IEEE Trans.on Industrial Electronics.2002,49(5):978-987.
[27]王京梅,兰中文,余忠,王豪才零电压一零电流PWM软开关技术研究[J].电 子器件,2002,25(4):340-344.
[28]Meynard TA,FochH,ForestF.Multi-cell converters:derived topologies[J]-IEEE Trans.On Industrial Electronic,2002,49(5):978-987.
[29]石勇,杨旭,何群,王兆安.同构混合开关拓扑的辨识[J].中国电机工程学报,2003,23(11):117-121.
[30]Lados,J.;Sanchez,G.Symbol recognition using graphs[In];Image Processing,2003.ICIP 2003.Proceedings.2003 International Conference on Volume 2,14-17 Sept.2003 Page(s):Ⅱ-49-52.
[31]D.Conte,P.Foggia,C.Sansone,and M.Vento.Thirty Years of Graph Matching in Pattern Recognition[J].Pattern Recognition and Artificial Intelligence,2004,18(3):265-298.
[32]Bambha,N.K.;Bhattacharyya S.S.,Joint application mapping/interconnect synthesis techniques for embedded chip-scale multiprocessors[J].IEEE Transactions on Parallel and Distributed Systems[J].2005,16(2):99-112.
[33]J.Lee,J.Oh,and S.Hwang.Clustering of Video Objects by Graph Matching[In].Proc.of 2005 IEEE International Conference on Multimedia and Expo(ICME2005)Amsterdam,Netherlands,July 6-8,2005.
[34]Kumar,Y.;Gupta,P.An External Memory Circuit Validation Algorithm for Large VLSI Layouts[In];VLSI,2007.ISVLSI '07.IEEE Computer Society Annual Symposium on 9-11 March 2007:510-511.
[35]Dehmer,M;Mehler,A.New method of measuring similarity for a special class of directed graphs[In].Czech-Slovak Conference on Graphs.MAY 23-28,2004Vysne Ruzbachy SLOVAKIA.GRAPHS '04.2007:39-59.
[36]Al-Zabi,B.R.A.;Kernytskyy,A.;Lobur,M.;Tkatchenko,S.On graph isomorphisna determining problem;Perspective Technologies and Methods in MEMS Design[J],2008.MEMSTECH 2008.International Conference on 21-24May 2008 Page(s):84-84.
[37]Asadpour,M;Sproewitz,A;Billard,A,et al.Graph Signature for Self-Reconfiguration Planning[In].IEEE/RSJ International Conference on Intelligent Robots and Systems,SEP 22-26,2008 Nice FRANCE.2008IEEE/RSJ INTERNATIONAL CONFERENCE ON ROBOTS AND INTELLIGENT SYSTEMS,VOLS 1-3,CONFERENCE PROCEEDINGS.2008:863-869
[38]Ai-Zabi,BRA;Kernytskyy,A;Lobur,M,et al..On graph isomorphism determining problem[In].th Intemational Conference of Young Scientists (MEMSTECH 2008),MAY 21-24,2008 Polyana UKRAINE.PERSPECTIVE TECHNOLOGIES AND METHODS IN MEMS DESIGN.2008:84-84.
[39]Golovin,A;Henrick,K.Chemical Substructure Search in SQL[J].journal of chemical information and modeling.2009,49(1):22-27.
[40]Garey,Michael R.& Johnson,David S.Computers and Intractability:A Guide to the Theory ofNP-Completeness[M].1979.
[41]F.Harary著,李慰萱译.图论[M],上海:上海科学技术出版社,1981.
[42]D.G.Comeil,C.C.Gotlieb,An efficient algorithm for graph isomorphism[J],Journal of the Association for Computing Machinery.1970,17:51-64.
[43]J.Hopcrofl,J.Won& Linear time algorithm for isomorphism of planar graphs[In],Proc.6th Annual ACM Symp.Theory of Compuling,pp.172-184,1974.
[44]G.S.Leuker and K.S.Booth,“A linear time algorithm for deciding interval graph isomorphism[J],” J.Ass.Comput.Mach.,Apr.1979,26:183-185.
[45]J.R.Ullmann.An Algorithm for Subgraph Isomorphism[J].Journal of the Association for Computing Machinery,1976,23(1):31-42.
[46]A.V.Aho,J.E.Hopcroft,J.D.Ullman,The design and analysis of computer Algorithms[M],Addison Wesley,1974.
[47]D.C.Schmidt,L.E.Druffel,A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices,Journal of the Association for Computing Machinery,1976(23):433-445.
[48]E.M.Luks,Isomorphism of Graphs of bounded valence can be tested in polynomial time,Journal of Compurer Sysrem Science,1982:42-65.
[49]L.P.Cordella,P.Foggia,C.Sansone,M.Vento.Evaluating Performance of the VF Graph Matching Algorithm[In].Proc.of the 10th International Conference on Image Analysis and Processing,IEEE Computer Society Press,1999:1172-1177.
[50]B.D.McKay,Practical Graph Isomorphism[M],Congressus Numerantium,1981,30(1):45-87.
[51]马颂德,神经网络与组合优化[A].中国神经网络首届学术大会论文集,C2N2—90,北京:1990,22-28.
[52]陈国良,神经网络用于求解组合优化问题[A].中国神经网络首届学术大会论文集,C2N2—90,北京:1990,122-129.
[53]梁维发等,用神经网络求解一些困难的图论问题[A].中国神经网络首届学术大会论文集,C2N2—90,北京:1990,924-927.
[54]Agusa,K.,Fujita,S.,Yamashita,M.,Ae,T.On neural networks for graph isomorphism problem[In].Neuroinformatics and Neurocomputers,RNNS/IEEE Symposium on Volume.Rostov-on-Don,Russia:1992:1142-1148.
[55]许进,张军英,保铮.基于Hopfield网络的图的同构算法[J].电子科学学刊,1996,VOL18(12):116-121.
[56]DePiero F.Trivedi M.Graph matching using a direct classification of node attendance[J].Pattern Recognition.1996,29(6):1031-1048.
[57]C.M.Hoffman,Croup-rheoreric AIgorirhms and Graph Isomorphism[M],Springer,Berlin,1998.
[58]B.T.Messmer,H.Bunke,A decision tree approach to graph and subgraph isomorphism detection[J].Pattern Recognition.1999,32(1):1979-1998.
[59]Warnaar D.B.,Chew M.,Olarin S.Method for detecting isomorphism in graphs using vertex degree correspondence with partitioning[J].American society of Mechanical Engineers,DE,1993,47:219-224.
[60]李锋,李晓艳.图的同构判定算法关联度序列法及其应用[J].复旦学报(自然科学版),2001,40(3):318-325.
[61]李锋,商慧亮.有向图的同构判定算法-出入度序列法[J].应用科学学报,2002,20(3):258-260.
[62]Cordelia LP,Foggia P,Sansone C,Vento M.An improved algorithm for matching large graphs.In:Jolion JM,Kropatsch W,Vento M,eds.Proc.of the 3rd IAPR-TC15 Int'l Workshop on Graph-Based Representation in Pattern Recognition.Ischia,2001.149-159.http://amalfi.dis.unina.it/graph/db/papers/vf-algorithm.pdf.
[63]P.Foggia,C.Sansone,M.Vento.A Performance Comparison of Five Algorithms for Graph Isomorphism[in].Proceedings of International Workshop on Graph-based Representation in Pattern Recognition.2001:188-199.
[64]Foggia P,Sansone C,Vento M.A database of graphs for isomorphism and sub-graph isomorphism benchmarking[In].Jolion JM,Kropatsch W,Vento M,eds.Proc.of the 3rd IAPR-TC15 Int'l Workshop on Graph-Based Representation in Pattern Recognition.Ischia,2001:176-187.http://amalfi.dis.unina.it/graph/db/papers/database.pdf.
[65]Kelly AR,Hancock ER.Graph matching using adjacency matrix Markov chain[in].Cootes TF,Taylor C,eds.Proc.of the British Machine Vision Conf.2001,BMVC 2001.Manchester:British Machine Vision Association.2001: 383-390.
[66]Kukluk J.Algorithm and experiments in testing planar graphs for isomorphism[J].Journal of Graph Algorithms and Applications.2004,8(3):313-356.
[67]Oliveira M,Greve F.A new refinement procedure for graph isomorphism algorithms[In].Feofiloff P,de Figueiredo CMH,Wakabayashi Y,eds.Electronic Notes in Discrete Mathematics,Proc.of the GRACO 2005.Amsterdam:Elsevier North-Holland,2005:373-379.
[68]Bao Ngoc Tran;Thuc Dinh Nguyen.An Efficient Algorithm for Isomorphic Problem on Generic Simple Graphs Modeling & Simulation[In].2008.AICMS 08.Second Asia International Conference on 13-15 May 2008 Page(s):824-829
[69]Zahidi,U.A..Spectral Solution for Detecting Isomorphic Graphs with Nondegenerate Eigenvalues[in].Multitopic Conference,2007.INMIC 2007.IEEE International 28-30 Dec.2007:1-4.
[70]Battiti,R;Mascia,F,An algorithm portfolio for the sub-graph isomorphism problem[in].International Workshop on Stochastic Local Search Algorithms.SEP 06-08,2007 Brussels BELGIUM.Engineering Stochastic Local Search Algorithms:Designing,Implementing and Analyzing Effective Heuristics.2007:106-12.
[71]Huaan Wu.An Invariant of the Graph Isomorphism[in].Computational Intelligence and Industrial Application,2008.PACIIA '08.Pacific-Asia Workshop on Volume 2,19-20 Dec.2008 Page(s):307-310.
[72]Lin,MC;Soulignac,FJ;Szwarcfiter,JL.A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs[J].11th Scandinavian Workshop on Algorithm Theory(SWAT 2008.JUL 02-04,2008 Gothenburg SWEDEN.ALGORITHM THEORY-SWAT 2008.2008:355-366.
[73]J.A.Bondy,U.S.R.Murty.吴望名等译图论及其应用.科学出版社.1984.4
[74]潘双来.电路理论基础(第2版)[M]北京:清华大学出版社,2007.
[75]杨廷力.机械系统基本理论一结构学.运动学,动力学北京:机械工业出版社,1995:1-69.
[76]李团结,曹惟庆.利用邻接矩阵的幂序列进行运动链和机构的同构判定[J].机械科学与技术,1998,17(1):11-14。
[77]丁华锋.运动链的环路理论与同构判别及图谱库的建立[D].燕山大学,2007.
[78]尹玉英.有机化学[M].北京:烃加工出版社,1990.
[79]王京梅,兰中文,余忠,王豪才零电压一零电流PWM软开关技术研究[J].电子器件,2002,25(4):340-344.
[80]商慧亮,李锋.非线性代数方程组的信号流图解法及应用[J].应用科学学报.2004,22(2):173-178.
[81]商慧亮,李锋.二次物理分解法——一种大规模非线性电阻网络的并行分析方法[J].复旦学报[J].2003,42(1):29-34.
[82]李锋,商慧亮.节点撕裂信号流图法[J].复旦学报.2003,42(1):24-29.
[83]李锋,商慧亮.线性模拟集成电路故障测试与诊断:短路导纳参数法[J].应用科学学报[J].2001,19(3):228-232.
[84]Feng Li,Huiliang Shang,Peng-Yung Woo.Determination of Isomorphism and Its Applications for Arbitrary Graphs Based on Circuit Simulation[J].Circuits,Systems,and Signal Processing.2008,27(5):749-761.(SCI ISI:000259859900011EREF).
[85]商慧亮,李锋.图的同构判定算法:电路模拟法[A].图论与系统优化专业委员会学术年会论文集[C],哈尔滨,2005:56-63.
[86]Huiliang Shang,Feng Li,Peng-Yung Woo.An Important Property of Isomorphic Graphs and Its Application.投送IEEE Trans.Pattern Analysis and Machine Intelligence.通过初审,修改当中.