求解图同构的判定算法

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (16): 52-57.

求解图同构的判定算法

侯爱民

东莞理工学院计算机科学与技术系，广东东莞 523808

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-06-01 发布日期:2011-06-01

Determining algorithm for solving graph isomorphism

HOU Aimin

Department of Computer Science and Technology，Dongguan University of Technology，Dongguan，Guangdong 523808，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-06-01 Published:2011-06-01

摘要/Abstract

摘要： 图同构的判定性问题是图论理论中的一个难题，至今没有得到彻底解决。受Ulam猜想的启发，提出了一个新的判定图同构的充分必要条件：在子图同构的前提下，根据新增顶点及相应关联边的关系，利用子图同构函数，判断父图同构的充分必要条件。基于具有同构关系的对应点无限衍生技术，采用反证法证明了这个充分必要条件的成立。设计并实现了图同构的一个判定算法，通过实例验证了算法的正确性和有效性。

关键词: 子图同构, 图同构, 对应点无限衍生技术, 判定算法

Abstract: How to determine the isomorphism of graphs is a difficult problem of graph theory，which has not been completely solved so far.From the idea of Ulam conjecture concerning graph isomorphism，a new necessary and sufficient condition of graph isomorphism is presented，which is stated as following：two graphs are isomorphic if and only if their subgraphs are isomorphic and the new vertices as well as their adjacency edges are corresponding.With the help of the technique for unlimitedly generating the corresponding pairs of vertices，this condition is proved with the method of reduction to absurdity.An algorithm for determining graph isomorphism is designed and implemented，whose correctness and validity are tested and verified with some concrete examples.

Key words: subgraph isomorphism, graph isomorphism, technique for unlimitedly generating the corresponding pairs of vertices, determining algorithm

侯爱民. 求解图同构的判定算法[J]. 计算机工程与应用, 2011, 47(16): 52-57.

HOU Aimin. Determining algorithm for solving graph isomorphism[J]. Computer Engineering and Applications, 2011, 47(16): 52-57.

[1]	鲁润泽，张海平. 应用机器学习方法的设计模式挖掘研究[J]. 计算机工程与应用, 2019, 55(6): 113-119.
[2]	朱文涛. 逻辑LTS预备模拟关系的判定算法[J]. 计算机工程与应用, 2016, 52(17): 41-48.
[3]	陈立宁，罗可. Apriori算法用于频繁子图挖掘的改进方法[J]. 计算机工程与应用, 2011, 47(10): 113-117.
[4]	侯爱民. 图同构的一个充分必要条件[J]. 计算机工程与应用, 2009, 45(30): 57-61.