Унифицированный подход к решению задач морфизма на графах

• Published in: Электронное моделирование
• Date: 2008
• Main Author: Ильяшенко, М.Б.
• Format: Article
• Language: Russian
• Published: Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2008
• Subjects: Математические методы и модели
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/101550
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Унифицированный подход к решению задач морфизма на графах / М.Б. Ильяшенко // Электронное моделирование. — 2008. — Т. 30, № 1. — С. 19-41. — Бібліогр.: 21 назв. — рос.

Описаны алгоритмы определения изоморфизма и граф-подграф изоморфизма, основанные на использовании матрицы возможных совмещений и применении инвариантов к подграфам окружения вершин. Приведены результаты сравнительного анализа скорости работы алгоритмов. Показана высокая производительность разработанных алгоритмов для класса графов, не обладающих специальными свойствами. Наведено алгоритми визначення ізоморфізму та граф-підграф ізоморфізму на базі використання матриці можливих суміщень та застосування інваріантів до підграфів оточення вершин. Наведено результати порівнювального аналізу швидкості роботи алгоритмів. Показано високу продуктивність розроблених алгоритмів для класу графів, що не мають спеціальних властивостей. Algorithms are presented for isomorphism and graph-subgraph isomorphism determination. They are based on the use of possible coincidence matrix and invariants application to subgraphs for vertexes surrounding. Comparative analysis results are offered for speed of algorithms executing. High performance of algorithms developed is shown for those graphs class which are not possessed special properties.