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

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

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

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

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

Существуют также смежные задачи теории графов, такие как поиск изоморфного подграфа и Шаблон:Нп1, принадлежащие к классу NP-полных. В смежных разделах математики существуют схожие проблемы, например изоморфизма проективных плоскостей и изоморфизма конечных групп, которые полиномиально сводятся к проблеме изоморфизма графов (возможность обратной полиномиальной сводимости в общем случае не доказана).

Пример

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

Граф $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$	$\left(\begin{array}{cccccccc}a& b& c& d& g& h& i& j\\ 1& 6& 8& 3& 5& 2& 4& 7\end{array}\right)$

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

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

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

Файл:Graph isomorphism 3.gif

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

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

Инварианты

Существует набор числовых характеристик графов, называемых инвариантами, которые совпадают у изоморфных графов (совпадение инвариантов является необходимым, но не достаточным условием наличия изоморфизма). К ним относятся число вершин $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◊H$, предложенное В. Г. Визингом, позволяет свести задачу проверки изоморфизма к задаче определения плотности графа $\phi (Y)$, содержащего $n(G)\cdot n(H)$ вершин. Если $\phi (Y)=n(G)$, $n(G)\le n(H)$, то граф $H$ содержит подграф, изоморфный графу $G$.

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

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

Применения

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

См. также

• Инвариант (математика)
• Открытые математические проблемы
• Задача поиска изоморфного подграфа
• Шаблон:Нп1

Ссылки

• Проблема изоморфизма графов Шаблон:Wayback // Курс видео-лекций И. Пономаренко