Т. 323, № 5 : Управление, вычислительная техника и информатика

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

Актуальность исследования заключается в том, что проблема поиска полного инварианта графа и полиномиального алгоритма его вычисления остаётся нерешенной. Цель работы состоит в нахождении полного инварианта обыкновенного графа на основе интегрального описателя абстрактной структуры и в разработке эффективного алгоритма вычисления полного инварианта. Методы исследования базируются на теории графов и теории интеграции кодов структурных различий в абстрактных структурах графов. В результате исследований предложен алгоритм решения одной из наиболее сложных задач теории графов - вычисление полного инварианта графа. Алгоритм основан на методах свободной и зависимой интеграции кодов структурных различий в графе и характеризуется простотой, эффективностью, и имеет полиномиальную оценку предельного объема вычислений. Полный инвариант представлен в виде вектора интегральных описателей вершин абстрактной структуры графа и содержит информацию для формирования подстановки изоморфизма. На языке Java разработано программное средство GraphISD, реализующее предложенный алгоритм. Приведены примеры вычисления полных инвариантов при свободной и зависимой интеграции.

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

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

Авторы:

Погребной Владимир Кириллович

Погребной Александр Владимирович

Скачать PDF