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

В теории графов изоморфизмом графов $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$
		$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.