Theory Research And Algorithm Design On Hamiltonian Cycle And Graph Isomorphism Problems

HC (i.e. Hamiltonian Cycle) problem and GI (i.e. Graph Isomorphism) problem are two special NP problems. For these two problems, an algorithm with polynomial time of input scale has not been found so far. The known algorithms have a factorial or exponential worst case time complexity of input scale. Therefore, except for continuing finding a polynomial time algorithm, how to enhance the known algorithms’efficiency is a significant method for solving these two NP problems practically.As a subgraph isomorphism, HC problem has many application areas such as computational complexity, job planning, computer wiring, vehicle routing, robot path control, drilling of printed circuit boards. GI problem has many application areas such as computational complexity, pattern recognition, computer vision processing, information retrieval, data mining, verifying VLSI layout, chemical molecular structure recognition. Especially, in the new era of "great data", great data mining becomes one of the most urgent problems which should be solved practically and effectively. Among them, graph data mining represents one of the kernel developing subarea and the hot topic of computer science research. Doubtlessly, graph matching techniques, whether the original graph matching or the subgraph matching, play an important role in graph data mining.Finding new decision conditions and/or new decision algorithms, or enhancing the known algorithms’efficiency are always the key topics of HC and GI. In this dissertation, some works on theorems and algorithms have been carried out for HC and GI problems, emphasizing on new decision conditions and decision algorithms based on these conditions. Not only do our conditions provide the theoretical results for designing the new algorithms and indicate the valid methods for enhancing the efficiency of the known algorithms, but also they have very high efficiency in most cases so far. Their correctnesses are proved and their time complexity and space complexity are analysed. The performance testing and comparison with other algorithms are carried out on the experimental platform programming in C language. Details are as follows:1. On the analysis of the merging pattern of Hamiltonian cycles, the necessary and sufficient condition based on the mergence of basic cycles connected in a common edge is proved, and the necessary condition formula is derived from this condition. This necessary and sufficient condition is the most effective condition because it can treat all Hamiltonian graphs some of whom cannot be treated by the other known closure condition. Furthermore, the formula derived from the necessary and sufficient condition is also the most effective formula because it can treat all non-Hamiltonian graphs some of whom cannot be treated by the two known necessary conditions, i.e. connectivity branch number condition and Grinberg condition. Besides, our formula can deal with not only planar graphs but also non-planar graphs. When planar graphs are treated, the Grinberg condition is the special form of our condition, that is, our formula is the generation of the Grinberg formula.2. Almost sufficient conditions for Hamiltonian graphs are related to the connectivity and independence of graphs so as to try to "spread out" the edges as far as possible such that the number of edges can be reduced while Hamiltonian cycles are still guaranteed. A Hamiltonian cycle will be constituted during the proof of these conditions. In contrast to the proof of these conditions, Erdos used a function of the edge bound to compute the maximum number of edges in maximal non-Hamiltonian graphs in order to analyze the algebra characteristic of non-Hamiltonian graphs. To overcome the defect of the Erdos condition which is explained in some examples, the feature of non-Hamiltonian graph, which fails to meet the degree sequence of the Chvatal sufficient condition, is studied and a new function of the edge bound for the maximal non-Hamiltonian graphs is proposed. The maximum number of edges in maximal non-Hamiltonian graphs is derived from this new function with mathematical analysis for extreme values. This new maximum number of edges not only proves the Erdos condition in a new way, but also improves it with a better threshold. Furthermore, it implies that there exist only two types of maximal non-Hamiltonian graphs of n vertices with minimum degree k.3. According to our results on decision conditions, a decision algorithm based on the necessary and sufficient condition for Hamiltonian graphs is designed and programmed in C language for the performance testing and comparison with other algorithms. Because the chromosome code is designed with the properties of splicing and decomposing, the algorithm can adjust the search direction adaptively by itself and go forward to generate a Hamiltonian cycle or a longest cycle during the process of searching for Hamiltonian Cycle. Besides, because the condition effectively limits the search space scope for candidate solutions, it succeeds in averting the exhaustive search on the whole permutation and combination of edge selection. Therefore, our algorithm based on this condition is an exhaustive search algorithm with a high efficiency which has a well performance even in the worst case and has not a factorial or exponential worst case time complexity of input scale. By analyzing the algorithm complexity, the following results are obtained that the space complexity is O(n×am×nscmaxk-1), the worst time complexity is O(n×am×nscmaxk-1) where am is the size of initial genus population, nscmax is the maximum value of selection plans during every iteration process of merging basic cycles successfully, and k is the iteration steps of merging basic cycles successfully during the process of generating a longest cycle. They are related to the number and construction of basic cycles and depended on the topological structure of the original graph.4. On the analysis of the pattern of subgraph isomorphism resulting in supergraph isomorphism, the necessary and sufficient condition based on subgraph isomorphism deciding supergraph isomorphism is proved. According to our results on decision conditions, a decision algorithm based on the necessary and sufficient condition for graph isomorphism is designed and programmed in C language for the performance testing and comparison with other algorithms. Meanwhile our condition provides a theorical explain for another known efficient algorithm VF2. By analyzing the algorithm complexity, the following results are obtained that the space complexity is O(n) and the time complexity is O(rm×n) where rm=kП(|celli|!) is the size of potential identical row-row mapping space of subgraphs with order one.5. On the analysis of the pattern of the common vertices and/or the distinct vertices in the adjacent field of a vertex, the necessary condition based on xor/nxor (i.e. exclusive-OR/exclusive-NOR) row code distance is proved. This necessary condition has a more efficiency on the refinement of vertex partitions than others for almost non-tree connected graphs. After comparing the refinement abilities of vertex partitions of five necessary conditions and discussing some methods for making further refinement, a general decision algorithm based on vertex partition and refinement for graph isomorphism is designed and programmed in C language for the performance testing and comparison with other algorithms. Because the intersecting operation should be implemented on the partition cells obtained at every iteration cycle, our algorithm with the self adaptive mapping characteristic can run on the special dimension areas of the search space. This means that the exhaustive search on the whole permutation and combination of vertex mapping relationship is averted and the candidate space scope is decreased effectively. By using some heuristic methods to prune the redundant branches, the depth of the search tree can be decreased further. Therefore, our algorithm based on this strategy is an exhaustive search algorithm with a high efficiency which has a well performance even in the worst case and has not a factorial or exponential worst case time complexity of input scale. By analyzing the algorithm complexity, the following results are obtained that the space complexity is O(rX n2) and the time complexity is O(rX n3) where r is the total iteration steps. For the most cases, r=O(n3). For the worst case, r=O(nh) where h=1/2*log2n.In this dissertation, focusing on two special types of NP problems such as Hamiltonian Cycle problem and Graph Isomorphism problem, the new practical technologies of resolving these two NP problems are studied on the analysis of decision condition, time complexity and space complexity. It provides significant result and reference value to realize these two problems’decision algorithms by using a programming language and improving the performance. Besides, these technologies advance some high efficient methods for solving the practical problems on application areas.