Polynomial algorithm of computing complete graph invariant on the basis of integral structure descriptor

Abstract

The relevance of the research is caused by the unsolved problem of searching for the complete graph invariant and polynomial algorithm for its computing. The aim of the research is in determining the complete invariant of an ordinary graph on the basis of integral descriptor of abstract structure and in developing the efficient algorithm for computing the complete invariant. The techniques of the research are based on the graph theory and the theory of structural differences code integration in abstract graph structures. The authors have proposed the algorithm for solving one of the most complex problems of graph theory. It is the computation of complete graph invariant. The algorithm is based on the methods of free and dependent integration of structural differences codes in a graph; it is characterized by simplicity, efficiency and it has polynomial estimation of the limiting amount of computation. The complete invariant is represented in the form of a vector of integral descriptor for graph abstract structure vertices and contains information for forming isomorphism substitution. Using Java the GraphISD software was developed implementing the proposed algorithm. The paper introduces the examples of computing the complete invariants at free and dependent integration.

Keywords

• complete graph invariant
• graph isomorphism
• integral structure descriptor
• abstract graph structure
• code integration area
• polynomial algorithm