Публікація: Метод оцінки ступеню структурної близькості зв’язних неорієнтованих графів
Завантаження...
Дата
2017
Автори
Назва журналу
ISSN журналу
Назва тома
Видавництво
Анотація
Розглянуто задачу пошуку подібної структури в термінах теорії графів. Класифіковано основні випадки часткового ізоморфізму двох зв’язаних неорієнтованих графів. Визначена покрокова процедура диференціації вершин графів для пошуку найбільшого ізоморфного підграфу. Розроблено метод оцінки ступеню структурної близькості, що заснований на пошуку найбільшого спільного підграфу та визначенні функцій відстаней між графами.
Рассмотрена задача поиска подобной структуры в терминах теории графов. Классифицированы основные случаи частичного изоморфизма двух связанных неориентированных графов. Определена пошаговая процедура дифференциации вершин графов для поиска наибольшего изоморфного подграфа. Разработан метод оценки степени структурной близости, основанный на поиске наибольшего общего подграфа и определении функций расстояний между графами.
We consider the problem of searching for similar patterns in terms of graph theory. It classifies the main cases of partial isomorphism of two connected undirected graphs. Determined step by step procedure of differentiation of graph vertices to find the highest isomorphic subgraph. A method for assessing the structural similarity based on the search for a common sub-graph and determining the functions of the distance between the graphs.
Опис
Ключові слова
Зв’язний неорієнтований граф, ізоморфізм, інваріант графа, найбільший спільний підграф, диференціація вершин графа, метричні характеристики
Бібліографічний опис
Білова Т.Г. Метод оцінки ступеню структурної близькості зв’язних неорієнтованих графів / Т.Г. Білова, І.О. Побіженко // Системи обробки інформації. – 2017. – № 1(147). – С. 9-12. https://doi.org/10.30748/soi.2017.147.02