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

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

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

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

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

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

Пример

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

Граф ${\displaystyle G}$	Граф ${\displaystyle H}$	Изоморфизм между графами ${\displaystyle G}$ и ${\displaystyle H}$	Подстановка изоморфизма ${\displaystyle f}$
		${\displaystyle f(a)=1}$ ${\displaystyle f(b)=6}$ ${\displaystyle f(c)=8}$ ${\displaystyle f(d)=3}$ ${\displaystyle f(g)=5}$ ${\displaystyle f(h)=2}$ ${\displaystyle f(i)=4}$ ${\displaystyle f(j)=7}$	${\displaystyle {\begin{pmatrix}a&b&c&d&g&h&i&j\\1&6&8&3&5&2&4&7\end{pmatrix}}}$

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

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

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

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

Инварианты

Существует набор числовых характеристик графов, называемых инвариантами, которые совпадают у изоморфных графов (совпадение инвариантов является необходимым, но не достаточным условием наличия изоморфизма)^[6]. К ним относятся число вершин ${\displaystyle n(G)}$ и число дуг/ребер ${\displaystyle m(G)}$ графа G, упорядоченный по возрастанию или убыванию вектор степеней вершин ${\displaystyle s(G)=(\rho (v_{1}),\rho (v_{2}),\dots ,\rho (v_{n}))}$, упорядоченный по возрастанию или убыванию вектор собственных чисел матрицы смежности графа (спектр графа), хроматическое число ${\displaystyle \chi (G)}$ и др. Факт совпадения инвариантов обычно не несет информации о подстановке изоморфизма.

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

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

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

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

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

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

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

Применения

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

См. также

• Инвариант (математика)
• Открытые математические проблемы
• Задача поиска изоморфного подграфа
• Проблема поиска максимального общего изоморфного подграфа^[en]

Ссылки

• Проблема изоморфизма графов Архивная копия от 18 мая 2015 на Wayback Machine // Курс видео-лекций И. Пономаренко

Примечания

Эта страница в последний раз была отредактирована 5 января 2023 в 11:43.