Как определить изоморфность графов
Перейти к содержимому

Как определить изоморфность графов

  • автор:

Проверка изоморфности графов

Два графа изоморфны, если с помощью переименования вершин и ребер их можно сделать одинаковыми. У изоморфных графов одни и те же свойства, выражаемые в терминах теории графов — например, одинаковое число вершин, ребер, висячих ребер, петель, вершин определенной степени.

Использование

Для проверки двух графов на изоморфность:

  1. Необходимо создать 2 отдельных графа для проверки.
  2. Выбрать алгоритм Алгоритм → Проверка изоморфности графов.
  3. Для проверки двух графов на изоморфность кликните по вершине первого графа, а потом по вершине второго графа.

Для поиска всех изоморфных подграфов в графе:

  1. Необходимо создать 2 отдельных графа для проверки.
  2. Выбрать алгоритм Алгоритм → Проверка изоморфности графов.
  3. Поставить галочку Поиск изоморфных подграфов.
  4. Выбрать граф, которому должны быть изоморфны подграфы.
  5. Выбрать граф, в котором необходимо искать изоморфные подграфы.
  6. В выпадающем списке вы можете выделить разные подграфы.

Алгоритм

Для данного алгоритма вы использовали библиотеку CBioInfCpp, которую разработал Сергей Черноухов.

© Граф Online — создание и визуализация графа в два клика или по матрице смежности и поиск кратчайшего пути, поиск компоненты связности, поиск Эйлеровго цикла. Поделиться: Twitter, Facebook, В Контакте. 2016. (Edit — History — Print — Recent Changes — Search)

Изоморфизм графов: определение, алгоритмы и применение

В данной статье мы рассмотрим определение и свойства задачи изоморфизма графов, а также алгоритмы ее решения и примеры применения в реальной жизни.

Изоморфизм графов: определение, алгоритмы и применение обновлено: 12 ноября, 2023 автором: Научные Статьи.Ру

Помощь в написании работы

Введение

Добро пожаловать на лекцию по Теории графов! В этой лекции мы будем изучать основные понятия и свойства графов, а также рассмотрим задачу изоморфизма графов и ее решение. Графы являются важным инструментом в различных областях, таких как компьютерные науки, математика, социология и другие. Понимание основных концепций и методов работы с графами поможет вам решать разнообразные задачи и анализировать сложные системы. Давайте начнем наше погружение в мир графов!

Нужна помощь в написании работы?

Написание учебной работы за 1 день от 100 рублей. Посмотрите отзывы наших клиентов и узнайте стоимость вашей работы.

Определение задачи изоморфизма графов

Задача изоморфизма графов является одной из основных задач в теории графов. Она заключается в определении, являются ли два графа изоморфными.

Графы считаются изоморфными, если существует биекция между их вершинами, такая что сохраняются все ребра. Иными словами, два графа изоморфны, если они имеют одинаковую структуру, но могут отличаться только в названиях вершин.

Формально, пусть G1 = (V1, E1) и G2 = (V2, E2) – два графа. Они считаются изоморфными, если существует биекция f: V1 -> V2, такая что для каждого ребра (u, v) из E1, существует ребро (f(u), f(v)) в E2, и наоборот.

Задача изоморфизма графов является NP-полной, что означает, что нет известного эффективного алгоритма для ее решения в общем случае. Однако, существуют различные эвристические алгоритмы и методы, которые позволяют приближенно решать эту задачу.

Алгоритмы решения задачи изоморфизма графов

Задача изоморфизма графов является NP-полной, что означает, что нет известного эффективного алгоритма для ее решения в общем случае. Однако, существуют различные эвристические алгоритмы и методы, которые позволяют приближенно решать эту задачу.

Переборный метод

Простейшим способом решения задачи изоморфизма графов является переборный метод. Он заключается в переборе всех возможных биекций между вершинами двух графов и проверке, соответствуют ли ребра в одном графе ребрам в другом графе. Этот метод является очень медленным и неэффективным для больших графов, но может быть полезен для небольших графов или в качестве базового алгоритма для проверки корректности более сложных методов.

Методы на основе перебора с отсечениями

Для ускорения процесса перебора можно использовать различные методы на основе отсечений. Например, можно проверять симметричные пары вершин только один раз, так как если вершина A из первого графа соответствует вершине B из второго графа, то вершина B также должна соответствовать вершине A. Также можно использовать различные эвристики для выбора наиболее перспективных вариантов биекций для проверки.

Методы на основе хэширования

Для ускорения процесса сравнения графов можно использовать методы на основе хэширования. Это позволяет сократить количество сравнений и исключить некоторые неподходящие варианты. Например, можно вычислить хэш-значение для каждой вершины и ребра в графе и сравнивать только те графы, у которых хэш-значения совпадают.

Методы на основе эвристик

Существуют различные эвристические методы, которые позволяют приближенно решать задачу изоморфизма графов. Например, можно использовать методы случайного поиска или методы на основе генетических алгоритмов. Эти методы не гарантируют точного решения, но могут быть полезны для приближенного решения задачи на больших графах.

В зависимости от конкретной задачи и требований к решению, можно выбрать подходящий алгоритм или комбинацию нескольких методов для решения задачи изоморфизма графов.

Свойства изоморфных графов

Изоморфные графы имеют ряд свойств, которые помогают определить их эквивалентность. Вот некоторые из них:

Количество вершин и ребер

Изоморфные графы имеют одинаковое количество вершин и ребер. Это означает, что если два графа изоморфны, то они содержат одинаковое количество точек и линий.

Степени вершин

Степени вершин в изоморфных графах также совпадают. Степень вершины – это количество ребер, связанных с данной вершиной. Если два графа имеют одинаковые степени для каждой вершины, то они могут быть изоморфными.

Циклы и пути

Изоморфные графы имеют одинаковое количество циклов и путей. Цикл – это замкнутый путь, который начинается и заканчивается в одной и той же вершине. Путь – это последовательность вершин, соединенных ребрами. Если два графа имеют одинаковое количество циклов и путей, то они могут быть изоморфными.

Структура подграфов

Изоморфные графы имеют одинаковую структуру подграфов. Подграф – это граф, полученный из исходного графа путем удаления некоторых вершин и ребер. Если два графа имеют одинаковую структуру подграфов, то они могут быть изоморфными.

Сохранение свойств

Изоморфные графы сохраняют некоторые свойства, такие как связность, эйлеровость, гамильтоновость и др. Если два графа имеют одинаковые свойства, то они могут быть изоморфными.

Эти свойства помогают определить, являются ли два графа изоморфными. Однако, необходимо помнить, что наличие этих свойств не является достаточным условием для изоморфизма графов. Для точного определения изоморфизма графов требуется применение алгоритмов и методов, которые учитывают все возможные комбинации вершин и ребер.

Примеры применения задачи изоморфизма графов

Криптография

Задача изоморфизма графов находит применение в криптографии, особенно в области создания и анализа криптографических алгоритмов. Изоморфные графы могут использоваться для создания шифров, где каждая вершина и ребро представляют определенные операции или преобразования данных. Использование изоморфных графов в криптографии позволяет создавать сложные и надежные шифры, которые трудно взломать.

Биоинформатика

В биоинформатике задача изоморфизма графов используется для анализа и сравнения генетических структур. Генетические структуры могут быть представлены в виде графов, где вершины представляют гены, а ребра – связи между генами. Сравнение изоморфных графов позволяет идентифицировать сходства и различия в генетических структурах, что помогает в понимании эволюции и функционирования организмов.

Социальные сети

Задача изоморфизма графов также находит применение в анализе социальных сетей. Социальные сети могут быть представлены в виде графов, где вершины представляют пользователей, а ребра – связи между пользователями (например, дружба или подписка). Сравнение изоморфных графов позволяет идентифицировать схожие группы пользователей или обнаружить подобные структуры в социальных сетях.

Распознавание образов

Задача изоморфизма графов используется в области распознавания образов. Графы могут быть использованы для представления образов, где вершины представляют особенности или характеристики образа, а ребра – связи между ними. Сравнение изоморфных графов позволяет определить, насколько похожи два образа, что может быть полезно в задачах распознавания и классификации образов.

Это лишь некоторые примеры применения задачи изоморфизма графов. В реальности она находит применение во многих других областях, таких как компьютерная графика, оптимизация, транспортная логистика и др.

Таблица свойств изоморфных графов

Свойство Описание
Рефлексивность Граф всегда изоморфен самому себе.
Симметричность Если граф G изоморфен графу H, то граф H также изоморфен графу G.
Транзитивность Если граф G изоморфен графу H, и граф H изоморфен графу K, то граф G также изоморфен графу K.
Сохранение степеней вершин Если граф G изоморфен графу H, то у каждой вершины в графе G будет такая же степень, как и у соответствующей вершины в графе H.
Сохранение связности Если граф G изоморфен графу H, то граф G будет связным тогда и только тогда, когда граф H также связный.

Заключение

Таким образом, изучение задачи изоморфизма графов является важным аспектом теории графов. Мы рассмотрели определение задачи, алгоритмы ее решения, а также свойства изоморфных графов. Понимание этой темы позволяет применять ее в различных областях, таких как компьютерная наука, биоинформатика и теория сетей. Изучение изоморфизма графов помогает нам лучше понять структуру и связи между объектами, представленными в виде графов, и применять этот анализ для решения различных задач.

Изоморфизм графов: определение, алгоритмы и применение обновлено: 12 ноября, 2023 автором: Научные Статьи.Ру

Изоморфизм — Теория графов

Термин «изоморфизм» буквально означает «одинаковая форма». Он встречается во многих отраслях математики, в том числе в теории графов. В этом уроке мы узнаем, что означает этот термин. Вы научитесь определять изоморфные графы и доказывать свою точку зрения математически.

Что такое изоморфные графы

Два графа изоморфны, если это один и тот же граф, просто нарисованный или представленный по-другому. Например, на этом рисунке показаны два графа, которые изоморфны друг другу:

В обоих графах каждая вершина смежна с каждой другой вершиной, поэтому это две изоморфные копии

Для такого простого примера несложно представить себе превращение одного графа в другой — надо просто переставить вершины местами. Но для графов с большим числом вершин такой подход не сработает.

На самом деле довольно сложно показать, что большие графы изоморфны. Например, здесь все три графа изоморфны, но это неочевидно с первого взгляда:

В таких неочевидных случаях мы можем математически доказать, изоморфны графы друг другу или нет.

Как доказать изоморфность графов

Чтобы доказать изоморфность, рассмотрим ее определение:

изоморфны, в функции

соблюдаются два условия одновременно:

  • является смежным с в
  • является смежным с в

Другими словами, два графа считаются изоморфными, если мы можем идеально сопоставить вершины одного графа с вершинами другого. При этом смежность тоже должна совпадать:

  • Если две вершины были смежными в первом графе, во втором они тоже должны быть смежными
  • Если две вершины не были смежными в первом графе, во втором они тоже не должны быть смежными

Попробуем применить это определение на практике и доказать изоморфность этих графов:

Для этого мы сопоставляем вершины следующим образом:

Так это выглядит в виде функции:

С вершинами разобрались, осталось проверить, все ли ребра совпадают:

  • Возьмем ребро в первом графе
  • Вспоминаем, что вершины и сопоставлены с и
  • Проверяем, есть ли ребро во втором графе
  • Такое ребро есть, так что можно идти дальше

Таким же образом проверяем не-ребра:

  • Посмотрим на первый граф и выясним, что на нем нет ребра от до
  • Вспоминаем, что вершины и сопоставлены с и
  • Проверяем, есть ли ребро во втором графе
  • Такого ребра нет, так что можно идти дальше

Эта проверка может показать долгой и утомительной, но таким образом можно точно проверить все ребра и не-ребра.

Эту работу можно ускорить с помощью алгоритмов графов, но это отдельная сфера математики, о которой пока мы не будем говорить подробно.

Как доказать неизоморфность графов

Как мы увидели на примере выше, изоморфность доказать не всегда легко. С другой стороны, доказать неизоморфность двух графов обычно проще — нужно найти свойство, которое эти два графа не разделяют.

Например, два графа могут отличаться такими свойствами:

  • Разное количество вершин или ребер
  • Разное количество компонент
  • Степени вершин в каждом графе

Чтобы лучше понять эти свойства, рассмотрим такой пример:
В этом примере графы имеют такие свойства:

  • Одинаковое количество вершин и ребер
  • Одна компонента в обоих случаях
  • По две вершины степени , три вершины степени , две вершины степени и одной вершине степени

Таким образом, первые три свойства не помогают. Однако нам на помощь приходит четвертое свойство: в первом графе нет треугольника-подграфа, а во втором — он есть.

Существует множество других возможностей доказать неизоморфность. Иногда для этого требуется немного творчества.

Например, вот эти графы неизоморфны:

Обратите внимание, что у них одинаковое количество вершин и ребер, степени почти всех вершин тоже одинаковы. Определим, в чем разница между ними. Второй граф содержит вершину степени

, смежную с двумя вершинами степени

— в первом графе это не так.

К этому же примеру можно подойти по-другому:

  1. На первом графе есть два пути длиной в пять вершин:
  • Прямой путь по горизонтали
  • Путь справа налево с поворотом вверх
  • Прямой путь по горизонтали в пять вершин
  • Путь в три вершины слева направо с поворотом вверх

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов

Наши выпускники работают в компаниях:

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Для перемещения по курсу нужно зарегистрироваться
1. Введение ↳ теория
2. Типы графов ↳ теория
3. Оптимизация маршрутов ↳ теория
4. Нотации ↳ теория
5. Подграфы ↳ теория
6. Связанность графов ↳ теория
7. Изоморфизм ↳ теория
8. Двудольные графы ↳ теория
9. Деревья ↳ теория
10. Остовные деревья ↳ теория
11. Взвешенный граф ↳ теория
12. Алгоритм Дейкстры ↳ теория
13. Эйлеровы схемы ↳ теория
14. Гамильтонов цикл ↳ теория
15. Доказательство гамильтонова цикла ↳ теория
16. NP-полнота ↳ теория
17. Раскрашивание графа ↳ теория
18. Диграфы ↳ теория
19. Связанность ↳ теория
20. Теорема Менгера ↳ теория
21. Поточная сеть ↳ теория

Поможем, если трудно

Порой обучение продвигается с трудом. Сложная теория, непонятные задания… Хочется бросить. Не сдавайтесь, все сложности можно преодолеть. Рассказываем, как

Не понятна формулировка, нашли опечатку?

Выделите текст, нажмите ctrl + enter и опишите проблему, затем отправьте нам. В течение нескольких дней мы улучшим формулировку или исправим опечатку

Что-то не получается в уроке?

Загляните в раздел «Обсуждение»:

  1. Изучите вопросы, которые задавали по уроку другие студенты — возможно, ответ на ваш уже есть
  2. Если вопросы остались, задайте свой. Расскажите, что непонятно или сложно, дайте ссылку на ваше решение. Обратите внимание — команда поддержки не отвечает на вопросы по коду, но поможет разобраться с заданием или выводом тестов
  3. Мы отвечаем на сообщения в течение 2-3 дней. К «Обсуждениям» могут подключаться и другие студенты. Возможно, получится решить вопрос быстрее!

Подробнее о том, как задавать вопросы по уроку

Проверка изоморфности двух графов и поиск изоморфных подграфов: подход на основе анализа NB-Paths

Есть такая задача – проверить, являются ли два графа изоморфными друг другу. Т.е., говоря по-простому, узнать, являются ли оба эти графа «одним и тем же» графом, но с разной нумерацией вершин и, в случае задания графов графически, с разным их пространственным расположением. Решение этой задачи не является таким уж очевидным, как может кому-то показаться на первый взгляд: даже для небольших графов взгляд на их графическое представление не всегда даст однозначный ответ. См., например, рисунок в той же Вики: ru.wikipedia.org/wiki/Изоморфизм_графов#Пример.

Ну как, очевидно?

А есть и более сложная задача: поиск в некотором «большом» графе всех подграфов, изоморфных некоторому другому графу «поменьше». Это еще более «темный лес». То есть, конечно, не совсем темный, но задача, согласитесь, не самая простая.

Итак, что же мы имеем?

1. Зачем вообще все это надо

И хотя задача про изоморфные (под)графы, как мы уже упомянули, сложная, она довольно нужная и полезная. А зачем? А затем, например, чтобы искать в базе данных химические соединения, подобные некоторой заданной молекуле по ее структурной формуле. Ведь ее можно представить себе в виде графа, не так ли? Этим занимается хемоинформатика – есть такая наука. А ведь есть еще задачи сопоставления с образцом, различные биоинформатические задачи, да много всего интересного.

2. Как решают эту задачу?

Классический подход к решению данной задачи был заложен Дж. Ульманом в 1976 году [3], впоследствии он существенно доработал свой алгоритм [4]. Также данный подход получил дальнейшее развитие в работах многих других авторов, например, Корделлы и соавторов [2] (алгоритм VF2), Бонници и соавторов [1] (алгоритм RI), и др.

Если кратко, то суть этого подхода заключается в «умном переборе» возможных соответствий вершин графа-образца B и графа A, в котором идет его поиск. «Умным» этот перебор делает ввод различных условий и ограничений, которые позволяют как можно раньше отсечь неподходящие варианты. Также для этих целей может проводиться различная предварительная обработка исходных данных.

Не будем здесь заниматься пересказом данных работ, а предложим читателю познакомиться с ними самостоятельно. Однако «показ лучше наказа», и, нужно отметить, что в Сети есть и неплохие графические примеры и объяснения этих алгоритмов. См., например, следующие:
coderoad.ru/17480142/Есть-ли-простой-пример-для-объяснения-алгоритма-Ульмана – очень хорошее и понятное объяснение с примером,
issue.life/questions/8176298 – шаги алгоритма VF2 с примером.

Однако возникает вопрос – возможны ли также еще какие-либо иные пути и подходы для решения этой задачи, пусть и для каких-то частных случаев? И вот с одним из возможных ответов на этот вопрос и хотелось бы Вас познакомить.

3. Изоморфизм графов и NB-пути

Давайте сразу договоримся: под NB-путями (и не из англомании, а просто потому, что так – короче) мы будем называть maximal non-branching paths, т.е. максимально протяженные неразветвляющиеся пути некоторого графа.

Итак, если у нас если два графа изоморфны друг другу, то для любого представления первого графа в виде последовательности максимально протяженных неразветвляющихся путей (т.е. этих наших NB-путей) всегда существует соответствующее ему такое же представление второго графа, и при этом:

  • для ориентированных графов соответствующие друг другу пути будут сонаправлены,
  • степени соответствующих друг другу вершин для неориентированных графов (а для ориентированных – количества входящих и исходящих ребер соответственно) будут равны,
  • при «совмещении» таких представлений в результате мы будем иметь соответствие вершин первого и второго графов.

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

A: 1, 2, 6, 4, 5, 3
B: 3, 4, 5, 1, 2, 6

Матрица смежности для A для заданного порядка вершин:

image

Матрица смежности для B для заданного порядка вершин:

image

Матрицы равны, следовательно, графы A и B – изоморфны.

При этом данный подход (1) применим как для ориентированных, так и неориентированных графов, (2) применим для графов, содержащих более одной компоненты связности/ сильной связности, (3) применим для графов, содержащих кратные (множественные) ребра и петли, однако (4) не учитывает вершины, для которых отсутствуют инцидентные им ребра.

4. Ну хорошо, проверили изоморфизм графов. А что же с поиском подграфов?

А тут, честно признаюсь, все значительно сложнее. Тут у нас будет следующее ограничение: исходя из самой сути метода можно находить не любые, но лишь «вписанные» подграфы. А «вписанным» подграфом графа A мы будем называть такой его подграф, который может быть «приклеен» к другим частям графа A только за счет ребер, инцидентных лишь граничным вершинам его (подграфа) неразветвляющихся путей максимальной длины (при этом граф A может содержать и иные компоненты связности). Не волнуйтесь, ниже будет пример, и все будет понятней. Прим. С 12.2020 все же удалось доработать данный метод для поиска всех (а не только «вписанных») подграфов, изоморфных данному. Но об этом в самом конце (см. Раздел 8. Вместо послесловия – Продолжение).

Кроме того, при решении данной задачи, помимо поиска соответствий NB-путей графов A и B по длине (как это было в рассмотренном выше примере с проверкой изоморфизма), также необходимо отдельно искать и следующие возможные соответствия между ними:

  • Соответствия NB-путей – простых цепей из графа B NB-путям – простым цепям/ простым из циклам графа A. При этом изначально такие пути в графе A могут быть длиннее – в этом случае берутся их отрезки, равные по длине искомому пути из B.
  • Соответствия NB-«концевых» путей графа B каким-либо NB-путям графа A (при этом пути из графа A также могут быть длиннее – в этом случае берутся их отрезки, равные по длине искомому пути из графа B).

image

При поиске «вписанного» изоморфного подграфа графа B в графе A (см. рис. выше) будут обнаружены следующие соответствия:

  • внутренний путь 2->3->4 графа B: внутренний путь 2->3->4 графа A,
  • концевые пути 1->2 и 10->2 графа B: концевой путь 0->2 графа A и фрагмент концевого пути 7->1->2 графа A, а именно 1->2,
  • простая цепь 7->8 графа B: отрезки простой цепи 9->10->11 графа A, а именно 9->10 и 10->11, а также отрезки простого цикла 12->13->14->12 графа A, а именно 12->13, 13->14, и 14->12.

A1 = 2, 1->2, 2->3, 3->4, 4->5, 4->6, 9->10>
A2 = 2, 1->2, 2->3, 3->4, 4->5, 4->6, 10->11>
A3 = 2, 1->2, 2->3, 3->4, 4->5, 4->6, 12->13>
A4 = 2, 1->2, 2->3, 3->4, 4->5, 4->6, 13->14>
A5 = 2, 1->2, 2->3, 3->4, 4->5, 4->6, 14->12>

Однако, если мы добавим к графу A дополнительное ребро 3->8, у нас получится граф A’ (ниже на том же рисунке). И в A’ уже будет не найти «вписанных» подграфов, изоморфных графу B. Действительно: ребро 3->8 «разбивает» путь 2->3->4 графа A на два и, значит, путей-кандидатов для внутреннего пути 2->3->4 графа B обнаружено не будет.

5. Теперь сам алгоритм

Теперь мы можем перейти к более детальному рассмотрению алгоритма поиска «вписанных» в граф А подграфов, изоморфных некоторому графу B.

Итак, алгоритм будет состоять из 4-х этапов:

  • Препроцессинг,
  • Сопоставление,
  • Прореживание,
  • Заключение.

Этап I. Препроцессинг


На данном этапе мы находим все NB-пути по каждому из графов, а также оцениваем факторы, ограничивающие пространство выбора при переборе. Т.е. мы делаем следующее:

  1. Находим все NB-пути в графе A и заносим их в динамический массив (в С++ – в вектор) PathsA
  2. Находим все NB-пути в графе B и заносим их в динамический массив (вектор) PathsB
  3. Вычисляем и запоминаем кратность всех ребер графов A и B. Дальнейшие действия по этапам II-IV проводятся исходя из допущения, что кратности всех ребер равны 1. Однако на финальной стадии производится сравнение кратности ребер подграфа графа A-кандидата на изоморорфизм с графом B и кратности ребер самого графа B: все ребра подходящего графа-кандидата должны иметь кратность не меньшую, чем сопоставляемое им ребро графа B.
  4. Подсчитываем степени всех вершин графов A и B (для ориентированных графов степени по входящим и исходящим ребрам учитываются отдельно).
  5. Вычисляем матрицы кратчайших путей между каждой парой вершин в A и в B: назовем их DA и DB соответственно.
  6. Формируем матрицу смежности – назовем ее B0 – для графа B таким же образом, как мы это делали выше, когда проверяли изоморфизм двух графов.

Этап II. Сопоставление


На данном этапе мы будем подбирать NB-пути-кандидаты (далее – просто «пути-кандидаты») из графа A для каждого из NB-путей графа B. Отметка о каждом пути-кандидате из PathsA для каждого i-го пути PathsB[i] будет записываться в двумерный динамический массив (в C++ – в вектор векторов) NPaths – соответственно в i-й вектор (i-ю строку) – в виде упорядоченного триплета чисел: номер соответствующего пути в PathsA – номер стартовой позиции в нем – длина пути.

Например, PathsB[2] = означает, что пути PathsB[2] сопоставлено 2 пути-кандидата из A: из PathsA[1] – 3 первых элемента пути начиная с нулевого (начального), и из PathsA[3] – также 3 элемента начиная с первого (следующего за начальным).

При этом поиск (подбор) путей-кандидатов мы будем производить по 4-м направлениям:

  1. Поиск путей-кандидатов для всех внутренних NB-путей графа B из PathsB, т.е. тех, обе граничных вершины которых соединены в графе B как минимум с 2-мя другими вершинами (независимо от направления такой связи) и при этом такой путь не является простым циклом (ориентированным – для ориентированных графов).
  2. Поиск путей-кандидатов для концевых NB-путей из PathsB.
  3. Поиск путей-кандидатов для NB-путей – простых циклов из PathsB.
  4. Поиск путей-кандидатов для NB-путей – простых цепей из PathsB.
  • его длина и длина пути-кандидата (должны быть равны для случаев 1 и 3, а для случаев 2 и 4 путь-кандидат из PathsA также может быть длиннее),
  • степени его граничных вершин и соответствующих им вершин пути-кандидата (у вершин из пути-кандидата данные значения должны быть не менее чем у пути из PathsB),
  • кратность ребра пути-кандидата должна быть не менее, чем у пути из PathsB,
  • другие возможные ограничения (например, совпадения меток вершин, если мы говорим о тех же химических соединениях, когда вершины можно маркировать соответствующими атомами, и т.д.)
Предварительное прореживание


Теперь давайте попробуем «ужать» граф A. Оставим в нем лишь те ребра, которые вошли в найденные нами пути-кандидаты. Если при этом граф A потерял хоть бы одно ребро по сравнению с его изначальным состоянием – возвращаемся на этап I “Препроцессинг”: степени вершин графа A и, соответственно, перечень путей-кандидатов может быть уменьшен и, соответственно, может быть сокращено пространство поиска.

Этап III. Прореживание перечня путей-кандидатов


Целью настоящего этапа является дальнейшее максимально возможное исключение неподходящих путей кандидатов. Для этого осуществим следующие действия.

  1. Исключение заведомо неподходящих путей-кандидатов исходя из минимальных расстояний между вершинами в графе B. Исключению подлежит тот путь-кандидат по каждому PathsB[i], для которого хотя бы по одному PathsB[j] не нашлось ни одного такого пути-кандидата, чтобы кратчайшие расстояния между их граничными вершинами в графе A было меньше или равно кратчайшему расстоянию между соответствующими им граничными вершинами путей PathsB[i] и PathsB[j] из графа B.
  2. Исключение для всех циклов из PathsB сопоставленных им нециклических путей-кандидатов и наоборот.
  3. Аналогичное п. 1 исключение путей-кандидатов, но не по критерию кратчайшего расстояния между граничными вершинами, а их (граничных вершин) взаимному равенству либо неравенству.
  • начальный элемент пути PathsB[i] не равен начальному элементу пути PathsB[j], и
  • конечный элемент пути PathsB[i] не равен конечному элементу пути PathsB[j], и
  • начальный элемент пути PathsB[i] равен конечному элементу пути PathsB[j], и
  • начальный элемент пути PathsB[j] не равен конечному элементу пути PathsB[i],

Т.е., грубо говоря, мы выкидываем те пути-кандидаты, которые заведомо не войдут в искомые подграфы – исходя из расстояния до всех прочих путей-кандидатов (страшно далеки эти пути от всех прочих), исходя из их цикличности/ нецикличности, а также исходя из должного равенства/ неравенства их граничных вершин с граничными вершинами других путей-кандидатов.

Если по результатам этапа III хотя бы 1 путь-кандидат был удален из PathsA, то – опять же – обновляется граф А – в нем остаются только те ребра, которые вошли в оставшиеся пути-кандидаты. И, опять же, если при этом граф A «похудел» хотя бы на одно ребро – снова возвращаемся на этап I “Препроцессинг”: степени вершин графа A и, соответственно, перечень путей-кандидатов может быть уменьшен и, соответственно, может быть сокращено пространство поиска.

Этап IV. Заключение


Каждое возможное сочетания всех оставшихся путей-кандидатов задает подграф графа A. Для каждого такого подграфа строится матрица смежности с учетом порядка следования путей кандидатов таким же образом, как была построена матрица смежности B0 для графа B, а затем эти матрицы смежности сравниваются между собой.

Если они равны, то сравниваются кратности ребер (см. п. 3 Этапа I Препроцессинг). Если все эти условия выполнены – найденный подграф считается изоморфным графу B и добавляется в множество найденных результатов.

При проведении этапа IV “Заключение” возможно применение различных дополнительных проверок, ускоряющих выявление и отбрасывание неподходящего подграфа.

6. Как все запутано… Рассмотрим пример работы алгоритма

Не знаю как Вам, а мне без примера было бы непонятно. Давайте рассмотрим все на примере.

На рис. ниже приведены графы A = 2, 2->5, 5->15, 16->15, 5->5, 5->5, 5->4, 5->6, 7->6, 6->8, 6->6, 6->9, 9->10, 9->11, 12->0, 0->12, 4->13, 13->14, 14->4> и B = 1, 4->5, 5->1, 1->3, 3->3, 3->2, 2->7, 2->8, 9->10, 10->9, 1->6, 6->11, 11->12, 12->6>. Нашей задачей является нахождение в графе A всех «вписанных» подграфов, изоморфных графу B. Результат также отражен на рисунке: найденные вершины и ребра графа A выделены толстой линией, а номера соответствующих вершин графа B указаны в скобках (если вариантов несколько – они указываются через дробь).

image

При решении задачи поиска в графе A «вписанных» подграфов, изоморфных графу B, имеем следующие результаты работы алгоритма.

Этап I: Выполнены все действия и расчеты по п.п. 1-5 данного этапа, ниже приводятся полученные PathsA и PathsB.

Этапы II-III. Сопоставление показало, что для каждого пути из PathsA находится как минимум один путь-кандидат из PathsB, а по результатам предварительного прореживания PathsA был сокращен. На этапе основного прореживания (III) дальнейшего сокращения PathsA не произошло. В результате PathsA и PathsB приняли вид:

Итоговое сопоставление NPaths имеет вид:
NPaths:

i=0: 3 0 2
i=1: 4 0 2
i=2: 2 0 2
i=3: 7 0 2 8 0 2
i=4: 7 0 2 8 0 2
i=5: 6 0 2
i=6: 5 0 2
i=7: 0 0 3
i=8: 1 0 4
i=9: 9 0 3

Здесь самое время вспомнить, что каждый упорядоченный триплет чисел в NPaths[i] задает соответствующий PathsB[i] путь-кандидат из A в формате: номер соответствующего пути из PathsA – стартовая позиция отрезка из данного пути – длина отрезка. Таким образом, нетрудно убедиться, что пути PathsB[0] = 1> (i=0: 3 0 2) соответствует единственный путь из A, а именно: отрезок из пути PathsA[3], начинающийся с его самого начала и имеющий длину 2.

Этап IV. В результате в графе A был найден единственный подграф A1, изоморфный графу B. A1 = 12, 1->2, 2->5, 4->13, 5->4, 5->5, 5->6, 6->6, 6->9, 9->10, 9->11, 12->0, 13->14, 14->4>.

7. Что же дальше?

А, дальше, в принципе, и все. Хотя не совсем: автор должен признаться, что алгоритм может еще дорабатываться и дорабатываться. Что тут нужно добавить?

  1. При введении дополнительных признаков вершин графов A и B (например, при задании графами химических соединений каждой вершине может быть сопоставлен числовой код, соответствующий одному и только одному атому (изотопу)) процесс поиска может быть ускорен за счет большей точности сопоставлений по Этапу II: дополнительным условием отбора путей-кандидатов будет соответствие меток вершин.
  2. Скорость работы представленного алгоритма очень сильно зависит от структур исходных графов и их взаимного соответствия. Алгоритм будет работать тем быстрее, чем более «уникальную», «нестандартную» и несимметричную структуру имеет граф-образец B.
  3. Исходя из этого, одним из возможных путей использования представленного алгоритма может являться, в том числе, «скриннинговый» поиск решения по любому из направлений:
    (1) поиск именно «вписанных» подграфов, изоморфных данному,
    (2) проверка изоморфности двух различных графов.
    «Скрининг» здесь подразумевает «предварительный экспресс-поиск решения», для чего необходимо задать некоторое предельное время его работы, по истечении которого при отсутствии результата можно считать, что данная задача подлежит решению другим алгоритмом.
  4. Возможно, для кого-то представленный алгоритм может оказаться полезным как при решении различных практических задач, так и при разработке новых алгоритмов решения задачи об изоморфном подграфе.

8. Вместо послесловия – Продолжение

В декабре 2020 случилось то, что должно было случиться: удалось как адаптировать данный подход для поиска всех (а не только «вписанных») подграфов в графе по образцу, так и воплотить это на практике. Решение, в принципе, лежало на поверхности: вместо non-branching paths (нет короткого аналога термина по-русски) были взяты сами ребра графов. И с января 2021 также на практике была реализована функция, позволяющая искать изоморфные подграфы с учетом меток вершин, причем произвольного типа (в т.ч. — строкового, что позволяет использовать «многогранные» метки; возможно, это может оказаться полезным для различных задач, в том числе, в области химии).

Литература

Общее по проблематике:
1. Bonnici, V., Giugno, R., Pulvirenti, A. et al. A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinformatics 14, S13 (2013). doi.org/10.1186/1471-2105-14-S7-S13.
2. Cordella L, Foggia P, Sansone C, Vento M: A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2004, 26 (10): 1367-1372. 10.1109/TPAMI.2004.75.
3. Ullmann Julian R.: An algorithm for Subgraph Isomorphism. Journal of the Association for Computing Machinery. 1976, 23: 31-42. 10.1145/321921.321925.
4. Ullmann Julian R.: Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism. J Exp Algorithmics. 2011, 15 (1.6): 1.1-1.6. 1.64

Написанный более официальным языком препринт автора про это самый «алгоритм на основе анализа NB-Paths», содержащий также инфу о предпринятой попытке его реализации на C++:
5. Черноухов С.А. 2020. Preprints.RU. Проверка изоморфности двух графов и поиск изоморфных подграфов: подход, основанный на анализе максимально протяженных неразветвляющихся путей / Maximal non-branching paths approach to solve (sub)graph isomorphism problem. DOI: dx.doi.org/10.24108/preprints-3111977

Полезные интернет-источники по теме:
6. coderoad.ru/17480142/Есть-ли-простой-пример-для-объяснения-алгоритма-Ульмана
7. issue.life/questions/8176298.
8. github.com/chernouhov/CBioInfCpp-0- — репозиторий свободной библиотеки функций для работы со строками и графами на C++, алгоритм реализован с помощью функции SubGraphsInscribed.

  • изоморфизм графов
  • подграф
  • поиск изоморфного подграфа
  • «вписанный» подграф
  • проверка изоморфности графов

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *