Т. 326, № 11

Метод определения сходства структур графов на основе выделения частичного изоморфизма в задачах геоинформатики

Актуальность работы обусловлена тем, что исследования по проблемам сходства структур ограничиваются применением косвенных признаков оценивания сходства. Необходимы эффективные алгоритмы определения сходства структур графов на основе прямых признаков в категориях изоморфизма. Такие алгоритмы могут применяться, например, для сжатия данных при работе геоинформационных систем и систем экологического мониторинга с векторными картами, для распознавания образов и в других приложениях. Исследования по применению прямых признаков для оценивания сходства на основе совмещения сравниваемых графов и выделения в них общих частей в виде изоморфных подграфов, названных частичными изоморфизмами, практически отсутствуют. Считается, что задача определения частичного изоморфизма без полного перебора подстановок сходства не может быть решена. Поэтому актуальными являются исследования по поиску приемлемых решений данной задачи при ограниченном переборе подстановок сходства. Цель исследования заключается в разработке метода определения сходства структур графов путём выделения в них наибольшей общей части, т. е. наибольшего частичного изоморфизма. Методы исследования основаны на применении прикладной теории графов, теории оптимизации и разработки алгоритмов, моделирования структуры графов сетью автоматов с целью дифференциации вершин. Результаты. Введены основные понятия и сформулированы положения концепции оценивания сходства структур графов на основе совмещения вершин и выделения общих подграфов - частичных изоморфизмов. Для сокращения переборов при решении проблемы определения наибольшего частичного изоморфизма предложено использовать идеи метода дифференциации вершин с помощью моделирования структур графов на основе сетей автоматов. Разработан метод взаимозависимой дифференциации вершин в сравниваемых графах, который позволяет формировать подстановку сходства и соответствующий частичный изоморфизм, а также алгоритм поиска подстановок сходства, локализованных относительно определенных пар вершин, и алгоритм выделения подстановки с наибольшим частичным изоморфизмом. Работа алгоритма поиска подстановки сходства на основе взаимозависимой дифференциации вершин показана на примере определения сходства двух графов.

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

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

Авторы:

Скачать PDF