The Research On Graph Isomorphism Problem

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.