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

Изоморфизм графов

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

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

В случае, если биекция отображает граф сам на себя (графы и совпадают), она называется автоморфизмом графа .

Содержание

Пример

Два графа, приведенные в примере, являются изоморфными.

Граф	Граф	Изоморфизм между графами и	Подстановка изоморфизма

Изоморфизм графов общего вида

Теорема Уитни

Инварианты

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

Различные инварианты имеют различную трудоемкость вычисления. В настоящее время полный инвариант графа, вычислимый за полиномиальное время, неизвестен, однако не доказано, что он не существует. Попытки его отыскания неоднократно предпринимались в 60-х — 80-х годах XX века, однако не увенчались успехом.

Модульное произведение Визинга

Модульное произведение графов , предложенное В. Г. Визингом (англ.), позволяет свести задачу проверки изоморфизма к задаче определения плотности графа , содержащего вершин. Если , , то граф содержит подграф, изоморфный графу .

Изоморфизм графов специального вида

Вычислительная сложность

Хотя задача распознавания изоморфизма графов принадлежит классу NP, неизвестно является ли она NP-полной или принадлежит классу P (при условии, что P ≠ NP). При этом задача поиска изоморфного подграфа (англ.) в графе является NP-полной. Современные исследования направлены на разработку быстрых алгоритмов решения как общей задачи изоморфизма произвольных графов, так и графов специального вида.

Применения

См. также

Примечания

Полезное

Смотреть что такое «Изоморфизм графов» в других словарях:

Изоморфизм — У этого термина существуют и другие значения, см. Изоморфизм (значения). Изоморфизм (от др. греч. ἴσος «равный, одинаковый, подобный» и μορφή «форма») это очень общее понятие, которое употребляется в различных разделах математики. В общих… … Википедия

ГРАФОВ ИЗОМОРФИЗМ — отношение эквивалентности на множестве графов. Изоморфным отображением одного неориентированного графа на другой наз. взаимно однозначное отображение вершин и ребер одного графа соответственно на вершиныи ребра другого графа, при к ром… … Математическая энциклопедия

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

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

ГРАФОВ ГОМЕОМОРФИЗМ — отношение эквивалентности на множестве графов, характеризующее их геометрия, свойства. Г. г. определяется следуюпшм образом. Подразбиением ребра ( а, b).графа Gназ. операция, состоящая в добавлении новой вершины v, удалении ребра (а, b).и… … Математическая энциклопедия

Теория графов — Граф с шестью вершинами и семью рёбрами Теория графов раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строго … Википедия

Теория графов и мографов — Теорема 3.27. замена любого ребра (a, b)in Gкритического графа G на k вершинно непересекающихся простых цепей длинны 3 тогда и только тогда приводят к образованию критического графа T 3(G), когда k удовлетворяет одному из следующих условий: # k=1 … Википедия

Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) … Википедия

Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия

Дуга (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

Источник

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

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

Изоморфные графы

Два графа G ₁ и G ₂ называются изоморфными, если —

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

Степени последовательности G ₁ и G ₂ одинаковы.

Степени последовательности G ₁ и G ₂ одинаковы.

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

(G ₁ ≡ G ₂ ) тогда и только тогда, когда ( G ₁ — ≡ G ₂ — ), где G ₁ и G ₂ — простые графы.

(G ₁ ≡ G ₂ ), если матрицы смежности G ₁ и G ₂ совпадают.

(G ₁ ≡ G ₂ ) тогда и только тогда, когда соответствующие подграфы G ₁ и G ₂ (полученные путем удаления некоторых вершин в G ₁ и их изображений в графе G ₂ ) изоморфны.

(G ₁ ≡ G ₂ ) тогда и только тогда, когда ( G ₁ — ≡ G ₂ — ), где G ₁ и G ₂ — простые графы.

(G ₁ ≡ G ₂ ), если матрицы смежности G ₁ и G ₂ совпадают.

(G ₁ ≡ G ₂ ) тогда и только тогда, когда соответствующие подграфы G ₁ и G ₂ (полученные путем удаления некоторых вершин в G ₁ и их изображений в графе G ₂ ) изоморфны.

пример

Какие из следующих графов изоморфны?

Планарные Графики

Граф «G» называется плоским, если его можно нарисовать на плоскости или сфере так, чтобы никакие два ребра не пересекали друг друга в не вершинной точке.

пример

районы

Каждый плоский план делит плоскость на связанные области, называемые областями.

пример

На плоских графиках действуют следующие свойства:

1. В плоском графе с n вершинами сумма степеней всех вершин равна

1. В плоском графе с n вершинами сумма степеней всех вершин равна

Источник

4. Изоморфные графы. Алгоритм распознования изоморфизма графов.

Изоморфные графы.

Два графа G1 и G2 называются изоморфными, если существует взаимно однозначное соответствие между множествами их вершин, обладающее тем свойством, что число ребер, соединяющих любые две вершины в G1, равно число ребер, соединяющих соответствующие вершины в G2.

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

Изоморфизм графов есть отношение эквивалентности.

Алгоритм распознования изоморфизма графов.

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

Неориентированные графы G и H с конечным числом вершин изоморфны тогда и только тогда, когда матрицы смежности A(G) и A(H) этих графов связаны соотношением , где T — подстановочная матрица, то есть матрица, в каждой строке и в каждом столбце которой имеется ровно один ненулевой элемент, равный 1.

Теорема. Для того, чтобы граф G1 был изоморфен графу G2, необходимо и достаточно выполнения следующих условий:
1. Полустепени входа и исхода соответствующих вершин равны.
2. Существует подстановка, переводящая граф G1 в граф G2.

Cформулируем алгоритм распознавания изоморфизма двух графов G1 и G2:

Источник

Проверка изоморфности двух графов и поиск изоморфных подграфов: подход на основе анализа 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 для заданного порядка вершин:

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

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

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

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

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

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

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

A1 = <0->2, 1->2, 2->3, 3->4, 4->5, 4->6, 9->10>
A2 = <0->2, 1->2, 2->3, 3->4, 4->5, 4->6, 10->11>
A3 = <0->2, 1->2, 2->3, 3->4, 4->5, 4->6, 12->13>
A4 = <0->2, 1->2, 2->3, 3->4, 4->5, 4->6, 13->14>
A5 = <0->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-пути по каждому из графов, а также оцениваем факторы, ограничивающие пространство выбора при переборе. Т.е. мы делаем следующее:

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

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

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

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

Предварительное прореживание

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

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

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

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

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

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

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

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

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

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

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

На рис. ниже приведены графы A = <1->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->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 указаны в скобках (если вариантов несколько – они указываются через дробь).

При решении задачи поиска в графе 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->1> (i=0: 3 0 2) соответствует единственный путь из A, а именно: отрезок из пути PathsA[3], начинающийся с его самого начала и имеющий длину 2.

Этап IV. В результате в графе A был найден единственный подграф A1, изоморфный графу B. A1 = <0->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. Что же дальше?

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

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

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

Источник