A New Graph With The Configuration Decision Algorithm

The graph isomorphism judgement is one of the hard problems in graph theory. As graph isomorphism judgement has been widely used in pattern recognition, computer vision, circuit analysis, molecule structure and many other related fields, it is a significant problem which is deserved to be researched.As it is well known, the graph isomorphism problem is one of a very small number of problems neither known to be solvable in polynomial time nor NP-complete. The problem attracts many researchers' attentions and participations, for which various algorithms have been proposed. Currently, Ullmann algorithm, SD algorithm, VF algorithm, and Nauty algorithm are relatively good algorithms in the world. These algorithms are all based on a searching process, in which vertexes are refined first, and then the correspondence between vertexes is obtained through the searching process. As a whole, each of these algorithms performs efficiently on the judgement of certain kinds of graphs, which can finish the isomorphism judgement of graphs with 1000 vertexes within an acceptable time frame. However, all these algorithms are only efficient for certain kinds of graphs and will fail to judge other kinds of graphs.A novel method, the circuit simulation algorithm, is proposed here, which transfers the graph isomorphism problem into the identical circuits problem. Most of the time, the algorithm, based on the proposed theory, is efficient to judge graph isomorphism. Thus the research of the topic provides a new theory and algorithm for graph isomorphism judgement and its applications.The following jobs have been completed in the thesis:1) New concepts about this algorithm are proposed, including identical circuits, adjoint circuits of graphs, full stimulation, node voltage sequence, and collection of node voltage sequences. Then the adjoint circuit model of an undirected graph is established. Finally the theoretical conditions for judging graph isomorphism are analyzed and proved.2) A new algorithm, the circuit simulation algorithm, is proposed and then the complete matlab program is implemented.3) The adjoint circuit model of a mixed graph is established and then the algorithm is extended to mixed graph isomorphism judgement.4) The improved version of the circuit simulation algorithm is proposed.5) The improved circuit simulation algorithm is tested on the popular graph database in the world and then the performance comparison of the algorithm with that of the existing algorithm, the Nauty algorithm which is relatively efficient, is performed. Simulation results demostrate that the circuit simulation algorithm performs better and it is applicable to more kinds of graphs, such as undirected graphs, directed graphs, and mixed graphs.6) At the end of the article, the applications of the algorithm in several fields are described and the value of the method is pointed out.