Т. 326, № 6

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

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

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

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

Авторы:

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

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

Скачать PDF