Т. 325, № 5 : Информационные технологии

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

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

Ключевые слова:

электронный ресурс, труды учёных ТПУ, полный инвариант, графы, абстрактные структуры, однородные графы, интегральный описатель структур, устойчивые группы, вершины, симметричные графы, изоморфизмы,

Авторы:

Скачать PDF