赋权无向图的同构判别与应用研究

摘要

图的同构判别在机构运动链综合、电网络分析等诸多领域有着重要应用。图的同构判别问题至今还未被证明是P问题或NP问题，但由于近年来大量学者的努力，同构判别问题已取得了进展，部分学者提出了较有效的同构判别算法。而图的拓扑特性问题，例如独立回路、基本回路、网孔回路的选取问题。由于无向图的回路数量随着节点数的增加呈指数级别增加，因此某些回路问题计算量非常大。然而许多同构判别方法都是基于图的拓扑特性，使得图的同构判别算法的时间复杂度常常为指数级别。特别是对于赋权无向图，国内外一直没有较为有效的同构判别算法。
　　本文在同构判别的邻接矩阵动态修改法的基础上，提出了一种适用于赋权无向图顶点分类方法，将顶点度、赋权、自环分别用不同的素数区分，然后利用三者素数乘积形成顶点素数度，将素数度序列按相同元素分组，将每组元素与素数重新建立映射，该映射关系下的素数可作为赋权无向图顶点的唯一标识，最后对邻接矩阵动态修改法进行改进，即利用素数乘即将图顶点信息和边赋权信息综合反映在邻接矩阵中，通过对邻接矩阵动态修改进行赋权无向图同构判别。
　　将赋权无向图同构判别应用于以下两个问题。一是针对电网络图规模大，电路元器件构造复杂的特点，提出了一种将电路元器件进行分类赋权，将电网络图转化为赋权无向图的方法，使得电网络图的同构判别问题转化为赋权无向图的同构判别问题。二是研究了一种机构运动链拓扑图转化为赋权无向图的方法。将赋权无向图同构判别应用于机构运动链和电网络的同构判别。利用面向对象技术开发了赋权无向图同构判别软件，为机构运动链以及电网络同构判别提供了新的辅助工具。

目录

声明

1 引 言

1.1 论文研究的背景和意义

1.2 国内外研究状况

1.3 目前研究中所面临的问题

1.4 本文拟解决的问题

2 无向图基础理论

2.1 图的矩阵表示

2.2 无向图的独立回路

2.3 无向图的网孔回路选择方法

2. 4 本章小结

3 赋权无向图的同构判别

3.1 赋权无向图的同构判别

3.2 赋权无向图同构判别实例

3.3 本章小结

4 赋权无向图同构应用研究

4.1 机构运动链同构判别

4.2 电网络图同构判别

4.3 本章小结

5 同构判别软件开发

5.1 开发工具的选取

5.2 软件界面

5.3 拓扑图的生成功能

5.4 拓扑图的编辑功能

5.6 同构判别软件使用步骤

5.8 本章小结

6 结论及展望

6.1 结论

6.2 展望

致谢

参考文献