Полный инвариант графа и алгоритм его вычисления

Abstract

Актуальность научной работы определяется тем, что в теории графов начиная со средины прошлого века все попытки найти вид полного инварианта и разработать для него эффективный алгоритм вычисления оказывались безуспешными. Предложенное в статье решение данной проблемы будет способствовать развитию методов инвариантного представления и анализа абстрактных структур графов. Цель исследования: сформулировать теоретические положения метода независимой интеграции кодов структурных различий и на этой основе разработать эффективный алгоритм вычисления полного инварианта графа. Методы исследования основаны на теории графов и методах свободной и зависимой интеграции кодов структурных различий для получения интегральных описателей вершин абстрактных структур графов. Результаты. Предложено новое правило назначения кодов структурных различий для дифференциации вершин структуры графа. Правило отличается простотой, представляет независимую систему кодирования и гарантирует получение интегрального описателя структуры (Integral Structure Descriptor - ISD), инвариантного относительно исходной нумерации её вершин. Используя данное правило, разработан метод независимой интеграции кодов структурных различий в графе. На основе этого метода разработан эффективный алгоритм вычисления полного инварианта графа. Показано, что для самых неблагоприятных случаев предельные объёмы вычислений ограничиваются полиномиальными оценками. На языке Java разработано программное средство GraphISD и проведены экспериментальные исследования эффективности работы алгоритма. Эксперименты показали, что предложенный полный инвариант и алгоритм его вычисления способны эффективно работать с библиотеками графов, содержащих до 5000 вершин, инвариантно представлять графы в библиотеке, выделять изоморфные графы на основе сравнения полных инвариантов, формировать подстановки изоморфизма и исходные представления графов.

The relevance of the discussed issue is caused by the fact, that in graph theory, since the mid of the last century, all attempts to find the form of complete invariant and to develop the effective algorithm for it computation have been failed. The proposed solution of the problem will contribute to development of methods of invariant representation and graphs structure analysis. The main aim of the study is to form theoretical basis of independent integration method of codes of structural differences and to develop the effective algorithm for complete invariant computation. The methods of the study are based on graph theory and methods of free and dependent integration of codes of structural differences for obtaining integral descriptors of vertices of abstract graph structures. The results. The author has proposed a new rule of assigning structural differences code to differentiate graph vertices. The rule is simple, it is represented as an independent encoding system and ensures the obtain the integral structure descriptor (ISD), invariant with respect to the vertices original numbering. Based on this method the effective algorithm of complete graph computation was developed. It is shown, that even for the worst cases the computation complexity is limited by polynomial evaluation. Software GraphISD was written on Java language. It was used for experimental researches of algorithm effectiveness. The experiments showed that the proposed complete graph invariant and algorithm of its computation are capable of working effectively with libraries of graph invariants, containing up to 5000 vertices, of distinguishing isomorphic graphs based on comparison of the complete invariants, of forming isomorphism substitutions and initial graph representations.