Polynomiality of method for computing graph structure integral descriptor

Abstract

The relevance of the research is caused by the necessity of developing the efficient method of invariant description and analysis of abstract structures of graph models. The aim of the research is to substantiate the polinomiality of the method for computing the integral descriptor of graph abstract structure proposed by the authors. The research techniques are based on application of machinery of graph theory and methods of free and dependent integration of codes of graph structural differences. The authors have introduced the notion of stable group of vertices in graph and stated the conditions of occurrence and existence of such groups at integration of structural differences codes when computing the integral structure descriptor. A number of features which disclose the appropriateness of application of the main rules of the integral structure descriptor and its polinomiality was determined for stable groups. It was ascertained on the basis of the defined features that the conditions for stable group existing are conditioned by hard limits; the vertices of different stable groups can not generate new stable groups. The authors have also defined the factor of full isolation of stable groups that predetermined considerably the efficiency of algorithm for computing the full graph structure descriptor. Polinomiality of the technique is demonstrated for the most complex case when graphs are homogeneous and contain stable groups. The authors developed Java GraphISD software for the experimental investigations of integral structure descriptor technique and introduced the results of its operation.

Keywords

• integral structure descriptor
• graph isomorphism
• abstract graph structure
• stable group of vertices
• code integration area
• algorithm polynomiality