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

Abstract

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

The urgency of the discussed issue is caused by the fact, that known approaches for the structures similarity estimation are limited by using a set of indirect properties. Effective similarity estimation algorithms on the basis of direct properties are necessary. Such algorithms can be applied for data compression in geographic information systems and systems of ecological monitoring if they are represented on vector map, or for pattern recognition and many other applications. Research of application of direct properties for similarity estimation on the basis of the combination of compared graphs and selecting equal parts as isomorphic subgraphs are almost absent. The problem of determining the partial isomorphism without exhaustive search permutations of similarity is considered unsolvable. Therefore researches of finding acceptable algorithms for solving this problem with limited count of permutations are relevant. The main aim of the study is to develop a method for determining the graphs structure similarity by selecting the highest common parts, i.e. highest partial isomorphism. The methods used in the study are based on the applied graph theory, theory of optimization and efficient algorithms development, modeling structures using automata models for vertices differentiation. The results. Introduced basic concepts and formulated provisions of the concept of the graphs structure similarity estimation based on a combination of vertices and selection of equal subgraphs ? partial isomorphism. Ideas of the vertices differentiation method are suggested to be used for reducing algorithm complexity. The method of the interdependent vertices differentiation is developed, which allows to form the similarity substitution and partial isomorphism. The algorithm of searching the similarity substitutions, relative to pair of vertices, and the algorithm of selection of substitution with highest partial isomorphism are developed. The algorithm of searching similarity substitution on the basis of the interdependent vertices differentiation is shown at the example of two graphs similarity estimation.