【作者】 张海龙；

【导师】 许进；

【作者基本信息】 华中科技大学 ， 系统工程， 2007， 硕士

【摘要】 图的同构问题一直受到数学界与工程技术界的关注,其原因主要来自两个方面:其一,从理论上讲,一般认为该问题属于NP-完全问题;其二,图的同构问题具有很好的应用前景,在化学、运筹学、计算机科学、电子学、网络理论等诸多领域都有应用,但指数时间复杂度的算法以及算法本身适用对象的局限性使得涉及到复杂图形同构判定的应用问题难以入手。本文对图同构问题运用不同的方法进行研究,首先是特殊图的同构问题,主要论述了最大外平面图和树图的多项式算法,并给出了必要的推理和改进策略。然后针对精确图同构问题,提出基于图的邻接矩阵变换的同构算法,可以快速判定图同构问题,但是并未从根本上在多项式时间内给出问题的解。为此,本文后续部分结合智能计算中的遗传算法、神经网络算法以及粒子群算法,对图同构问题进行求解。遗传算法中,把同构问题转化为求最小值问题,并对遗传算子进行优化改进,通过采取不同进化策略,使得种群在求解过程中保持良好的多样性和收敛性,得到了较好的实验结果。在神经网络部分介绍了一种基于Hopfield网络模型改进算法,把遗传算法同神经网络算法结合起来,有效地避免问题陷入局部最优解,并给出同构算法并对结果进行分析。最后针对同构问题给出粒子群计算模型,提出离散粒子群算法,对粒子群中的速度、位置重新定义,用于解决同构问题。由于同构问题的特殊性,在对算法的可行性、有效性测试操作中,本文采用多次实验,数据分析的方式对算法进行分析,虽然取得了较好的结果,但从改进策略角度和问题判定准确性角度,各种算法仍有待改进的空间,这也是我们以后研究的重点和难点。更多还原

【Abstract】 The problem of graph isomorphism has been concerned by the fields of mathematics and engineering for years. The main reason comes from two aspects: for one thing, theoretically, the problem is generally considered to be NP-complete; for another, graph isomorphism promises a wide application, such as chemistry, operational research, computer science, electronic engineering and network theory, but the exponential complexity of the algorithms and their harsh limitations put on testing graphs make it difficult to solve some applied problem referring to complicated graphs.In this paper we introduce the research we did on graph isomorphism problem using different methods. First, polynomial algorithms referring to special graph are discussed, in which part we give necessary reasoning and improvement strategy. Then An algorithms referring to exact graph isomorphism are discussed, which make use of the particularity of graph, get the results efficiently. But those are not radically solving this problem in polynomial time. So, in the following chapters, we solve this problem using intelligence computation, such as Genetic Algorithm, Neuro Network and PSO. As to GA, we transformed ISO problem to minimal value problem, and made improvement of the GA operator, which can keep the diversity and astringency of the population. In the part of NN, we introduced an improved network model based on Hopfield network which joins GA and NN together. At last, we gave the resultes of the problem and gave necessary analyze. In the end, we proposed discrete PSO model, introduced the definitions of PSO elements. In this paper, we do many experiment, analyze those algorithms by analyzing the data. Though the results seem very good, all these algorithms still need to be improved in the field of improvement strategy and veracity of the problem judgement.更多还原