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

Решение задачи определения изоморфизма графов, представленных атрибутными матрицами

Предложен алгоритм решения задачи определения изоморфизма графов, вершинам и ребрам которых приписаны атрибуты, представляющие графовую модель объекта. В основу алгоритма положен метод интеграции структурных различий, модифицированный для работы с атрибутными матрицами графов. Для установления изоморфизма устойчивых групп разработано правило назначения абстрактных описателей при свободной и зависимой дифференциации вершин в этих группах. Работа алгоритма показана на примере определения изоморфизма двух графов общего вида.

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

изоморфизмы, графы, атрибутные матрицы, структурные различия, устойчивые группы, дифференциация вершин, абстрактные описатели

Авторы:

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

Скачать bulletin_tpu-2012-321-5-11.pdf