Метод дифференциации вершин графа и решение проблемы изоморфизма

Abstract

Актуальность. Одной из актуальных проблем современной прикладной теории графов является моделирование связей между структурой объекта и его свойствами. Важное место при установлении такой связи занимает проблема идентификации и оценивания сходства структур. Известные подходы к оцениванию сходства структур в энергетике, геоинформационных системах, компьютерной химии, и, в частности в нефтехимии, ограничиваются использованием набора косвенных признаков и не рассматривают возможности решения проблемы, основываясь на прямых признаках, связанных с изоморфизмом. Цель научной работы: сформулировать теоретические основы метода дифференциации вершин графов, показать возможные применения метода для оценки сходства структур и решения проблемы изоморфизма, рассматривая его как частный случай полного сходства структур. Методы исследования основаны на применении прикладной теории графов, теории построения и анализа эффективных алгоритмов, моделирования структур с помощью автоматных моделей, применении теории интеграции кодов структурных различий в процессе дифференциации вершин. Результаты. Сформулирована проблема идентификации структуры графа, объединяющая проблемы инвариантного описания структуры и получения полного инварианта графа, изоморфизма графов, оценивания сходства структур. Показано, что решение перечисленных задач в основном сводится к решению проблемы дифференциации вершин в структуре графа. Введено три вида структурных различий в графе - базовые, скрытые, виртуальные. Предложена автоматная модель структуры графа, положенная в основу метода дифференциации вершин и разработки алгоритмов вычисления полных инвариантов со свободной интеграцией кодов структурных различий (алгоритм ISD-F), зависимой (ISD-D) и независимой (ISD-I). Рассмотрены особенности применения данных алгоритмов при решении проблемы изоморфизма и возможности разработки алгоритма для оценивания сходства структур на основе взаимозависимой интеграции кодов. Проведены экспериментальные исследования алгоритмов при вычислении полных инвариантов и проверке на изоморфизм графов, содержащих до 5000 вершин. Эксперименты показали высокую эффективность алгоритмов при решении этих задач.

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.