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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории графов изоморфизмом графов G=\left \langle V_G, E_G \right \rangle и H=\left \langle V_H, E_H \right \rangle называется биекция между множествами вершин графов f \colon\ V_G \rightarrow V_H такая, что любые две вершины u и v графа G смежны тогда и только тогда, когда вершины f(u) и f(v) смежны в графе H. Здесь графы понимаются неориентированными и не имеющими весов вершин и ребер. В случае, если понятие изоморфизма применяется к ориентированным или взвешенным графам, накладываются дополнительные ограничения на сохранение ориентации дуг и значений весов. Если изоморфизм графов установлен, они называются изоморфными и обозначаются как G\simeq H.

Иногда биекция f записывается в виде подстановки изоморфизма \begin{pmatrix} a_1 & a_2 & \dots & a_n \\ f(a_1) & f(a_2) & \dots & f(a_n) \end{pmatrix}. Некоторые задачи обработки графов требуют не только проверки изоморфизма, но и выяснения его подстановки.

Отношение изоморфизма графов представляет собой отношение эквивалентности, определенное для графов, и позволяет произвести разбиение исходного класса всех графов на классы эквивалентности. Множество графов, изоморфных друг другу, называется классом изоморфизма графов (англ.), их число в зависимости от n представляет собой последовательность A000088 в OEIS (1, 1, 2, 4, 11, 34, 156, 1044, 12346, ...).

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

Пример[править | править вики-текст]

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

Граф G Граф H Изоморфизм между графами G и H Подстановка изоморфизма f
Graph isomorphism 1.gif Graph isomorphism 2.gif f(a)=1

f(b)=6
f(c)=8
f(d)=3
f(g)=5
f(h)=2
f(i)=4
f(j)=7

\begin{pmatrix} a & b & c & d & g & h & i & j \\ 1 & 6 & 8 & 3 & 5 & 2 & 4 & 7 \end{pmatrix}

Изоморфизм графов общего вида[править | править вики-текст]

Графы G и H являются изоморфными, если путем перестановки строк и столбцов матрицы смежности графа G удается получить матрицу смежности графа H. Однако перебор всех возможных перестановок характеризуется вычислительной сложностью O(N!) (при условии, что сравнение матриц смежности производится за время, не зависящее от N, что обычно несправедливо и дополнительно увеличивает приведенную оценку), что существенно ограничивает применение подобного подхода на практике. Существуют методы ограниченного перебора возможных пар предположительно-изоморфных вершин (аналог метода ветвей и границ), однако они незначительно улучшают приведенную выше асимптотику[1].

Теорема Уитни[править | править вики-текст]

Исключение из теоремы Уитни: представленные графы K_3 (слева) и K_{1,3} (справа) не изоморфны, однако их рёберные графы изоморфны

Теорема Уитни об изоморфизме графов[2][3], сформулированная Хасслером Уитни в 1932 году, гласит, что два связных графа изоморфны, если и только если их рёберные графы изоморфны, за исключением графов K_3 (полного графа из 3 вершин) и полного двудольного графа K_{1,3}, которые не являются изоморфными, однако оба имеют граф K_3 в качестве рёберного графа. Теорема Уитни может быть обобщена для гиперграфов[4].

Инварианты[править | править вики-текст]

Существует набор числовых характеристик графов, называемых инвариантами, которые совпадают у изоморфных графов (совпадение инвариантов является необходимым, но не достаточным условием наличия изоморфизма)[5]. К ним относятся число вершин n(G) и число дуг/ребер m(G) графа G, упорядоченный по возрастанию или убыванию вектор степеней вершин s(G)=(\rho(v_1), \rho(v_2), \dots, \rho(v_n)), упорядоченный по возрастанию или убыванию вектор собственных чисел матрицы смежности графа (спектр графа), хроматическое число \chi(G) и др. Факт совпадения инвариантов обычно не несет информации о подстановке изоморфизма.

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

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

Модульное произведение Визинга[править | править вики-текст]

Модульное произведение графов Y=G \lozenge H, предложенное В. Г. Визингом (англ.), позволяет свести задачу проверки изоморфизма к задаче определения плотности графа \varphi (Y), содержащего n(G) \cdot n(H) вершин. Если \varphi(Y) = n(G), n(G) \le n(H), то граф H содержит подграф, изоморфный графу G.

Изоморфизм графов специального вида[править | править вики-текст]

Вычислительная сложность[править | править вики-текст]

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


Применения[править | править вики-текст]

На практике необходимость проверки изоморфизма графов возникает при решении задач хемоинформатики, математической (компьютерной) химии[6], автоматизации проектирования электронных схем (верификация различных представлений электронной схемы)[1], оптимизации программ (выделение общих подвыражений).

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР. — М.: Радио и связь, 1990. — 216 с.
  2. H. Whitney (1932). «Congruent graphs and the connectivity of graphs». Am. J. Math. 54: 160-168. DOI:10.2307/2371086.
  3. Харари Ф. Теория графов. — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
  4. Dirk L. Vertigan, Geoffrey P. Whittle (1997). «A 2-Isomorphism Theorem for Hypergraphs». J. Comb. Theory, Ser. B 71 (2): 215-230. DOI:10.1006/jctb.1997.1789.
  5. Зыков А. А.  Основы теории графов. — М.: Наука, 1986. — 384 с. — ISBN 978-5-9502-0057-1
  6. Трофимов М. И., Смоленский Е. А. Применение индексов электроотрицательности органических молекул в задачах химической информатики // Известия Академии наук. Серия химическая. — 2005. — С. 2166—2176.