任意图同构判定及其应用

摘要

图的同构问题一直受到数学界与工程技术界的关注，其原因主要来自两个方面：第一，从理论上讲，一般认为该问题属于NP-完全问题；第二，图的同构问题具有很好的应用前景，在化学、运筹学，计算机科学、电子学、网络理论等诸多领域都有应用，但指数时间复杂度的算法以及算法本身适用对象的局限性使得涉及到复杂图形同构判定的应用问题难以入手。 本文提出了面向任意图的同构判定算法并系统的讨论了实际应用中基于任意图的建模方法。 在实现上述算法与应用过程中，本文完成了以下工作： 1．在分析了简单图拓扑结构描述的基础上提出了新的任意图拓扑结构描述方法和相应的同构判定条件。 2．建立了任意图的伴随电路模型，采用节点电压方法求取电压，将其作为同构判定的参数，使用物理方法解决图论问题。 3．针对部分特殊图形提出了相对位序表的概念，以改进算法在处理这类图形时的效率。 4．在具体应用中引入任意图建立模型，从而为一类很难采用单一拓扑图建模的复杂问题提供了一种新的解决方案。 区别于目前已有的同构判定算法，该算法对于待判定的拓扑图没有附加限定条件，能有效的应用于无向图，有向图，带权图以及由它们组成的混合图，因而适用于各类涉及到图的同构判定的应用领域。

目录

摘要

引言

第一章图的同构及其应用概况

第二章任意图同构判定的基本理论

第三章任意图的电路建模及算法实现

第四章应用建模

第五章结论与展望

参考文献

致谢

论文独创性声明及使用授权声明