种新的图同构判定算法——电路模拟法

《种新的图同构判定算法——电路模拟法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、8.2展望...............................................................……，..……958.3作者发表文章列表.........................................................……%8.4科研活动列表...............................................................……97参考文献....................................

2、.............................................……98致谢.......................................................................................……105图的同构判定是图论学科中诸多难题之一，由于它在模式识别、人工视觉、电路分析、分子结构等很多领域有着广泛的应用，因此该问题是值得研究的重要课题。目前理论上还无法证明图的同构问题究竟属于NP一完全问题还是P问题。众多学者对该问题予以关注和研究，提

3、出了多种同构判定算法。目前国际上比较好的算法主要有Ullmann算法、SD算法、VF算法和Nauty算法等。这些算法基本上都是基于搜索过程的，即在寻找同构的过程中将顶点进行细分，然后基于这些细分子集展开搜索，通过搜索得到图的顶点对应关系来判定同构。总体来说，这些算法都对特定种类的图有较好的判定效率，对于上千个顶点的图，能够在可以接受的时间内完成判定，但对其它种类的图则会失效，适用范围都较为有限。本文以独特的视角对图的同构判定问题展开了研究。提出了一种新的同构判定算法:电路模拟法，即将图的同构问题转化为电路的相同问题。以此获

4、得的同构判定算法在大多数情况下可有效判定两图是否同构。本课题的研究为图的同构判定及其实际应用提供了新的理论与方法。本文主要完成了以下工作:l)提出了电路模拟法所涉及的新概念:相同电路、图的伴随电路、全激励、节点电压序列以及节点电压序列集。给出了无向图的伴随电路模型。推导并证明了算法的理论依据。2)提出了可应用于无向图同构判定的电路模拟法的基本算法，并在matlab环境下实现了该算法。3)给出了混合图的伴随电路模型，将电路模拟法扩展到混合图的同构判定上。4)进一步提出了改进的电路模拟法。5)利用改进的电路模拟法对目前国际流行

5、的测试图库进行了测试，而且和目前已有算法中表现较好的Nanty算法做了比较。测试表明，本算法在对几类常见图的同构判定中表现优于Nauty算法，而且可以适用于无向图、有向图及混合图等多种类型的图。6)最后给出了电路模拟法在应用领域的成功应用实例，指出了电路模拟法的应用价值。关键词:图的同构，电路模拟法，图的伴随电路，全激励，节点电压序列AbstraetAbstfaCtThegraPhisomorphismjudgement15oneofthehardProblemsingraPhtheory.AsgraPhisomorphi

6、smjudgementhasbeenwidelyusedinPatternrecognition，eomPutervision，eireuitanalysis，moleeulestructureandmanyotherrelatedfields，it15asignifieantProblemwhieh15deservedtoberesearched.Asit15well肋own，thegraPhisomorphismProblem15oneofaverysmallnumberofProblemsneither比owntob

7、esolvableinPol户omialtimenorNP一eomPlete.TheProblemattraetsmanyresearehers’attentionsandParticiPations，forwhichvariousalgorithmshavebeenProPosed.Currently，Ullmannalgoritllm，SDalgoritlllli，VFalgorithm，andNautyalgoritlnnarerelativelygoodalgorithmsintheworld.Thesealgor

8、ithmsareallbasedonasearehingProeess，inwhiehvertexesarerefinedfirst，andthenthecorresPondeneebetweenvertexes15obtainedthroughthesearchingProcess.Asawhole，