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

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

Определение и формальное описание

Пусть даны два графа \(G_1 = (V_1, E_1)\) и \(G_2 = (V_2, E_2)\), где \(V\) — множество вершин, а \(E\) — множество рёбер (неупорядоченных пар вершин). Изоморфизмом графов называется биекция \(f: V_1 \to V_2\), такая что для любых двух вершин \(u, v \in V_1\) выполняется условие:

\[ \{u, v\} \in E_1 \iff \{f(u), f(v)\} \in E_2. \]

Если такой изоморфизм существует, графы \(G_1\) и \(G_2\) называются изоморфными, что обозначается \(G_1 \cong G_2\). Для ориентированных графов дополнительно требуется сохранение направления дуг. Для графов с помеченными вершинами или рёбрами (например, взвешенных графов) изоморфизм должен также сохранять метки.

Изоморфизм графа на самого себя называется автоморфизмом. Множество всех автоморфизмов графа образует группу относительно композиции отображений, называемую группой автоморфизмов графа.

История

Понятие изоморфизма графов возникло одновременно с зарождением теории графов. В 1736 году Леонард Эйлер в своей работе о Кёнигсбергских мостах, положившей начало теории графов, фактически рассматривал структурные свойства графа, не зависящие от конкретного расположения вершин. Однако формальное определение изоморфизма было введено значительно позже, в конце XIX — начале XX века, в работах математиков, занимавшихся абстрактной теорией графов, таких как Артур Кэли и Денеш Кёниг.

В XX веке проблема изоморфизма графов стала одной из центральных задач теоретической информатики. В 1970-х годах было показано, что задача проверки изоморфизма графов принадлежит классу NP, но её точная вычислительная сложность долгое время оставалась открытой. В 2015 году Ласло Бабаи (László Babai) предложил квазиполиномиальный алгоритм для решения этой задачи, что стало значительным прорывом.

Критерии и инварианты изоморфизма

Для проверки изоморфизма графов используются инварианты — характеристики графа, которые сохраняются при изоморфизме. Если два графа различаются хотя бы по одному инварианту, они не могут быть изоморфны. К основным инвариантам относятся:

• Количество вершин и рёбер.
• Степени вершин (последовательность степеней, отсортированная по убыванию).
• Спектр графа (множество собственных значений матрицы смежности).
• Хроматическое число (минимальное количество цветов, необходимое для раскраски вершин графа).
• Число циклов фиксированной длины.
• Количество компонент связности и их размеры.
• Группа автоморфизмов (её порядок и структура).

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

Классификация и примеры

Простые случаи изоморфизма

• Полные графы: все полные графы с одинаковым числом вершин \(K_n\) изоморфны друг другу.
• Циклы: все циклы \(C_n\) (простые циклы длины \(n\)) изоморфны.
• Двудольные графы: полные двудольные графы \(K_{m,n}\) изоморфны при одинаковых \(m\) и \(n\).

Примеры неизоморфных графов

Два графа с четырьмя вершинами: один — цепь из четырёх вершин (путь \(P_4\)), другой — «звезда» \(K_{1,3}\). Оба имеют по 4 вершины и 3 ребра, но их последовательности степеней различны: у \(P_4\) — (1, 1, 2, 2), у \(K_{1,3}\) — (1, 1, 1, 3). Следовательно, они не изоморфны.

Изоморфизм и неориентированные графы

Изоморфизм не зависит от способа изображения графа на плоскости. Два графа могут выглядеть по-разному визуально, но быть изоморфными, если их можно «перерисовать», переставив вершины без разрыва рёбер.

Алгоритмические аспекты

Задача проверки изоморфизма графов (Graph Isomorphism Problem, GI) является одной из классических задач теории сложности. Она принадлежит классу NP: если предъявить отображение \(f\), его корректность можно проверить за полиномиальное время. Однако неизвестно, является ли эта задача NP-полной или решается за полиномиальное время.

Основные алгоритмы

• Наивный алгоритм: перебор всех биекций между вершинами — требует \(O(n!)\) операций, что практически нереализуемо для графов с \(n > 10\).
• Алгоритм Вейсфелера — Лемана (WL-алгоритм): итеративный метод раскраски вершин на основе их окрестностей. Является полиномиальным, но не полным: существуют неизоморфные графы, которые WL-алгоритм не различает (например, некоторые коспектральные графы).
• Алгоритм Маккея (nauty): один из самых быстрых на практике алгоритмов, основанный на канонической нумерации вершин. Широко используется в программных пакетах (nauty, Traces).
• Квазиполиномиальный алгоритм Бабаи (2015): время работы \(2^{O(\log n)^c}\) для некоторой константы \(c\). Этот результат показывает, что задача GI, вероятно, не является NP-полной.

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

На 2024 год задача изоморфизма графов не решена за полиномиальное время в общем случае, но существуют полиномиальные алгоритмы для многих частных классов графов: деревьев, планарных графов, графов ограниченной степени, графов с ограниченной древесной шириной.

Применение

Изоморфизм графов находит применение в различных областях:

• Химия: для идентификации изомеров — химических соединений с одинаковым составом, но разной структурой. Молекулы представляются в виде графов, где вершины — атомы, рёбра — химические связи. Изоморфизм графов позволяет определить, являются ли две структурные формулы эквивалентными.
• Информатика: в задачах сравнения баз данных, распознавания образов, анализа социальных сетей, верификации программного обеспечения (сравнение графов потоков управления).
• Криптография: некоторые криптосистемы основаны на сложности задачи изоморфизма графов (например, схема идентификации Гольдрейха — Микали).
• Биоинформатика: сравнение метаболических сетей, филогенетических деревьев, белковых взаимодействий.
• Теория сетей: анализ структурной эквивалентности в социальных и транспортных сетях.

Связь с другими математическими понятиями

Изоморфизм графов является частным случаем более общего понятия изоморфизма в математике — взаимно однозначного соответствия между объектами, сохраняющего их структуру. В теории категорий графы образуют категорию, где морфизмами являются гомоморфизмы графов, а изоморфизмы — обратимые гомоморфизмы.

Понятие гомоморфизма графов является более слабым: это отображение, сохраняющее смежность, но не обязательно биективное. Гомоморфизмы используются, например, в теории раскраски графов.

Интересные факты

• Задача изоморфизма графов входит в список «проблем тысячелетия» Института Клэя? Нет, она не входит, но считается одной из важнейших открытых проблем в теории сложности.
• Количество неизоморфных графов с \(n\) вершинами растёт экспоненциально: для \(n=10\) их около 12 миллионов, для \(n=20\) — более \(10^{36}\).
• Существуют графы, которые являются изоморфными своему дополнению (самодополнительные графы). Например, граф-цикл \(C_5\) изоморфен своему дополнению.
• Алгоритм nauty, разработанный Бренданом Маккеем, используется для генерации всех неизоморфных графов заданного размера и является стандартным инструментом в теории графов.

Источники

• Харари Ф. Теория графов. — М.: Мир, 1973.
• Babai L. Graph Isomorphism in Quasipolynomial Time // arXiv:1512.03547, 2015.
• McKay B. D., Piperno A. Practical graph isomorphism, II // Journal of Symbolic Computation, 2014.
• Arvind V., Torán J. The Graph Isomorphism Problem: Structural Complexity and Algorithms. — Springer, 2008.