Processing And Optimization Technology Of Graph Isomorphism Query Based On Encoding On Intersection Graph

Intersection graphs are very important and widely investigated graphs in graph theory. Intersection graph is used in the field of biology, the analysis of matrix, statics task assignment and so on. It has a rapid development because its widely application in the nearly30years. There are some very import graph classes in intersection graph, on these classes, a lot of usually NP-Complete problems admit very efficient and elegant solutions which are polynomial time algorithm. In intersection graph, such as the interval graphs and intersection graphs, they are extensively studied. One of the reason is they naturally appear in many contexts such as scheduling, genomics, phylogeny and archeology.This thesis focus on the study of graph encoding of intersectin graph and graph isomorphism based on graph encoding, because they have a very important practical applications in real world. Firstly, starting from the relevant research background, including the development graph history, and the situation home and abroad research on graph encoding and graph isomorphism.Secondly, to the research of encoding and representation of graphs, the main purpose of grap encoding as follows:first, shortest string to represent a graph, compress storage space; second, encode and decode in the simple way to get the best time complexity; third, response quickly to all kinds of query. There does not exist a common encoding technology that can reach the entire requests on arbitrary graph. This thesis mainly focused on the purpose, after graph encoding that can support efficient graph query. For graph isomorphism, on some classes of intersection graph, this thesis give an efficient isomorphism algothrim based on labeled PQ-tree on interval graph, namely GIBPQ-Tree algorithm. The algorithm use the data structre of PQ-tree, get labeled PQ-tree and the canonical form of it. The time complexity of the algorithm is linearity. For general intersection graph isomorphism, we propose another graph isomorphism based on spectral encoding, the GIBS algorithm is an improved algorithm of ordinary graph isomorphism based on graph adjacency matrix eigenvalue. The GIBS add degree of vertex to as encoding information, so has good performance and can be used in other graph isomorphism such as planar graph.At last, the efficientness of the two algothrims and the comparation result of GIBPQ-Tree algorithm and GIBS algorithm is given at the last of the thesis. And the result shows that the two algorithms have good time complexity and effectiveness.