Задача распознавания изоморфизма графов. Прикладное значение и подходы к решению

Карелин Владимир Петрович
Additional contact information
Карелин Владимир Петрович: НОУ ВПО "Таганрогский институт управления и экономики"

Вестник Таганрогского института управления и экономики, 2015, issue 1 (21), 102-106

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

Keywords: ИЗОМОРФИЗМ ГРАФОВ; МАТРИЦА СМЕЖНОСТИ; ИНВАРИАНТЫ ГРАФА; СООТНЕСЕННЫЕ ПОДМНОЖЕСТВА; ДВОИЧНЫЙ КОД МАТРИЦЫ; ИЗОМОРФНОЕ ОТОБРАЖЕНИЕ; ИЗОМОРФНАЯ ПОДСТАНОВКА; СОПУТСТВУЮЩАЯ ЗАДАЧА; УПОРЯДОЧЕННОСТЬ ВЕРШИН (search for similar items in EconPapers)
Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
http://cyberleninka.ru/article/n/zadacha-raspoznav ... -podhody-k-resheniyu

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:scn:030999:15895318

Access Statistics for this article

More articles in Вестник Таганрогского института управления и экономики from CyberLeninka, Негосударственное образовательное учреждение высшего профессионального образования «Таганрогский институт управления и экономики»
Bibliographic data for series maintained by CyberLeninka ().