Том 321 № 5 (2012): Управление, вычислительная техника и информатика
Решение задачи определения изоморфизма графов, представленных атрибутными матрицами
Предложен алгоритм решения задачи определения изоморфизма графов, вершинам и ребрам которых приписаны атрибуты, представляющие графовую модель объекта. В основу алгоритма положен метод интеграции структурных различий, модифицированный для работы с атрибутными матрицами графов. Для установления изоморфизма устойчивых групп разработано правило назначения абстрактных описателей при свободной и зависимой дифференциации вершин в этих группах. Работа алгоритма показана на примере определения изоморфизма двух графов общего вида.
Ключевые слова:
изоморфизмы, графы, атрибутные матрицы, структурные различия, устойчивые группы, дифференциация вершин, абстрактные описатели