Известия Томского политехнического университета: Инжиниринг георесурсов (May 2019)
Method of graph vertices differentiation and solution of the isomorphism problem
Abstract
Modelling the relations between the structure of the object and its properties is one of the current problems in the modern applied graph theory. The problem of identification and evaluation of structures similarity plays the important role in solving this task. The known approaches to the structures similarity estimation in power engineering, geographic information systems, computer chemistry, including petrochemistry, are limited by using a set of indirect properties and do not consider the possibility of solving the structures similarity problem with the help of direct properties, associated with isomorphism. The main aim of the study is to state the theoretical bases of graph vertices differentiation method and to show the method possible applications for estimating the structures similarity and for solving the isomorphism problem, considering it as a special case of complete structures similarity. The methods used in the study are based on the applied graph theory, efficient algorithms analysis and construction theory, simulating structures using automata models and application of theory of integration of codes of structural differences. The results. The authors have stated the problem of graph structure identification, which unites invariant description, complete invariant, graph isomorphism and structures similarity problems. It is shown that the solution of these problems is reduced in general to solving vertices differentiation problem. The paper introduces three types of structural differences in a graph - basic, hidden and virtual. The authors offered a graph structure automata model as the basis of the vertices differentiation method and development of complete graph invariant computation algorithms with free (algorithm ISD-F), dependent (ISD-D) and independent (ISD-I) integration of structure differences codes. The paper considers the features of these algorithms application for solving the isomorphism problem and the possibility of developing the algorithm for evaluating the structures similarity based on the interdependent codes integration. The authors carried out the experimental studies of algorithms for computing complete invariant for graphs containing up to 5000 vertices. The experiments have shown high efficiency of these algorithms.
