无向无权图同构判别算法

发布时间：2018-07-04 16:30

  本文选题：同构图 + Floyd算法　； 参考：《西南师范大学学报(自然科学版)》2017年03期

【摘要】：首先,分析判别同构图的一种常用实现方法:基于邻接矩阵存储,并讨论其存在的时间复杂度为O(N!).接着,针对两图中结点数、边数、每个结点的度均相同的特殊图形提出无向无权图同构判别的另一算法:采用结点之间距离及关联边进行判别.最后通过实例进行算法测试和比较,证明了该算法是完全行之有效的.
[Abstract]:Firstly, a common method to distinguish the same composition: memory based on adjacent matrix is analyzed, and the time complexity of its existence is discussed as O (N!). Then, another algorithm for isomorphism discrimination of undirected unauthorized graph is proposed for the special graph with the same number of nodes, edge numbers and the same degree of each node in two graphs: the distance between nodes and the associated edges are used to judge the isomorphism of the undirected unauthorized graph. Finally, the algorithm is tested and compared with an example, and it is proved that the algorithm is completely effective.
【作者单位】： 运城学院计算机科学与技术系;
【基金】：山西省运城学院131人才专项(JG201634)
【分类号】：O157.5

【参考文献】

相关期刊论文 前8条

1 赵路;王建锋;;图的第四大Q-特征值[J];西南师范大学学报(自然科学版);2016年04期

2 吴炎;林越;;局部环上n阶矩阵的{1}-逆作成的集合及其特征性质[J];西南师范大学学报(自然科学版);2015年12期

3 谢敏;杨帆;曾璇;;无向图的层次化谱分析同构判定算法[J];计算机辅助设计与图形学学报;2015年11期

4 侯爱民;;求解图同构的判定算法[J];计算机工程与应用;2011年16期

5 侯爱民;;图同构的一个充分必要条件[J];计算机工程与应用;2009年30期

6 燕子宗;张宝琪;;图论及其应用[J];重庆科技学院学报(自然科学版);2007年02期

7 李锋;陆韬;;任意图同构判定及其应用[J];复旦学报(自然科学版);2006年04期

8 李锋,商慧亮;有向图的同构判定算法:出入度序列法[J];应用科学学报;2002年03期

相关博士学位论文 前1条

1 商慧亮;一种新的图同构判定算法[D];复旦大学;2009年

相关硕士学位论文 前1条

1 赵男;基于MapReduce的分布式极图构造算法研究[D];北京交通大学;2013年

【共引文献】

相关期刊论文 前10条

1 王文霞;;无向无权图同构判别算法[J];西南师范大学学报(自然科学版);2017年03期

2 马纪英;陈文燕;于金青;;三角矩阵环及其上模的同调性分析[J];西南师范大学学报(自然科学版);2016年11期

3 张宗杰;吴炎;;对角线元为数量幂等矩阵的上三角矩阵及其应用[J];西南师范大学学报(自然科学版);2016年08期

4 陈中标;;基于关联点度矩阵的无向图同构判定[J];无线互联科技;2016年07期

5 罗贤海;李涛;;赋权混合图的拓扑转化与同构判别[J];陶瓷学报;2014年04期

6 王文霞;王春红;;基于无向图转有向图的同构判别[J];山西师范大学学报(自然科学版);2014年02期

7 王文霞;;有向图的同构判定算法:出入度序列法[J];山西大同大学学报(自然科学版);2014年02期

8 商慧亮;刘洋;柳志栋;董文杰;李锋;;改进电路模拟法的应用——同构混合开关拓扑辨识[J];应用科学学报;2014年02期

9 王建新;徐r，

本文编号：2096671