Please use this identifier to cite or link to this item: http://earchive.tpu.ru/handle/11683/5390
Title: Полный инвариант графа и алгоритм его вычисления
Other Titles: Complete graph invariant and algorithm of its computation
Authors: Погребной, Андрей Владимирович
Keywords: полный инвариант; графы; абстрактные структуры; однородные графы; интегральный описатель структур; устойчивые группы; вершины; симметричные графы; изоморфизмы; complete graph invariant; abstract graph structure; homogeneous graph; integral structure descriptor; stable group of vertices; symmetric graph; graph isomorphism
Issue Date: 2014
Publisher: Томский политехнический университет
Citation: Погребной А. В. Полный инвариант графа и алгоритм его вычисления / А. В. Погребной // Известия Томского политехнического университета [Известия ТПУ]. — 2014. — Т. 325, № 5 : Информационные технологии. — [С. 110-122].
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.
URI: http://earchive.tpu.ru/handle/11683/5390
ISSN: 1684-8519
Appears in Collections:Известия ТПУ

Files in This Item:
File Description SizeFormat 
bulletin_tpu-2014-325-5-14.pdf317,36 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.