Введение

Биекция между множествами вершин двух графов. В теории графов, изоморфизм графов G и H — это биекция между множествами вершин G и H, такая что любые две вершины u и v графа G смежны в G тогда и только тогда, когда f(u) и f(v) смежны в H. Этот вид биекции обычно описывается как "биекция, сохраняющая рёбра", в соответствии с общим понятием изоморфизма как биекции, сохраняющей структуру. Если между двумя графами существует изоморфизм, то графы называются изоморфными и обозначаются как G ≅ H. В случае, когда биекция является отображением графа на самого себя, то есть когда G и H — один и тот же граф, биекция называется автоморфизмом G. Если граф конечен, мы можем доказать его биективность, показав, что он инъективен (один к одному) или сюръективен (на); нет необходимости доказывать оба свойства. Изоморфизм графов является отношением эквивалентности на графах и, как таковое, разбивает класс всех графов на классы эквивалентности. Множество графов, изоморфных друг другу, называется классом изоморфизма графов. Вопрос о том, можно ли определить изоморфизм графа за полиномиальное время, является важной нерешённой проблемой в информатике, известной как проблема изоморфизма графов. Два графа, изображённые ниже, изоморфны, несмотря на их различный вид.

Граф G Граф H Изоморфизм между G и H:
f(a) = 1
f(b) = 6
f(c) = 8
f(d) = 3
f(g) = 5
f(h) = 2
f(i) = 4
f(j) = 7

Вариации

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

Изоморфизм обозначенных графов

Для помеченных графов используются два определения изоморфизма. Согласно одному из определений, изоморфизм — это биекция вершин, сохраняющая как рёбра, так и метки. Согласно другому определению, изоморфизм — это биекция вершин, сохраняющая рёбра и сохраняющая классы эквивалентности меток, то есть вершины с эквивалентными (например, одинаковыми) метками отображаются на вершины с эквивалентными метками и наоборот; то же самое относится и к меткам рёбер. Например, граф с двумя вершинами, помеченными 1 и 2, имеет единственный автоморфизм при первом определении, но два автоморфизма при втором определении. Второе определение используется в определенных ситуациях, когда графы снабжены уникальными метками, обычно выбираемыми из целого диапазона от 1 до n, где n — число вершин графа, и используемыми исключительно для однозначной идентификации вершин. В таких случаях два помеченных графа иногда называют изоморфными, если соответствующие базовые непомеченные графы изоморфны (иначе определение изоморфизма было бы тривиальным).

Мотивация

Формальное понятие "изоморфизма", например, "изоморфизма графов", отражает неформальное представление о том, что некоторые объекты имеют "одну и ту же структуру", если не учитывать индивидуальные особенности "атомных" компонентов рассматриваемых объектов. Если индивидуальность "атомных" компонентов (вершин и ребер, для графов) важна для корректного представления моделируемого графами, то модель уточняется путем введения дополнительных ограничений на структуру и используются другие математические объекты: ориентированные графы, помеченные графы, раскрашенные графы, корневые деревья и так далее. Отношение изоморфизма также может быть определено для всех этих обобщений графов: биекция изоморфизма должна сохранять элементы структуры, определяющие тип объекта – дуги, метки, цвета вершин/ребер, корень корневого дерева и т.п. Понятие "изоморфизма графов" позволяет отделить свойства графа, присущие его структуре, от свойств, связанных с его представлением: изображения графов, структуры данных для графов, маркировки графов и т.д. Например, если граф содержит ровно один цикл, то все графы в его классе изоморфизма также содержат ровно один цикл. С другой стороны, в типичном случае, когда вершины графа представлены целыми числами 1, 2, N, то выражение может отличаться для двух изоморфных графов.

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

Теорема Уитни об изоморфизме графов, доказанная Хасслером Уитни, утверждает, что два связных графа изоморфны тогда и только тогда, когда их линейные графы изоморфны, за исключением одного случая: K3, полный граф на трёх вершинах, и полный двудольный граф K1,3, которые не изоморфны, но оба имеют K3 в качестве своего линейного графа. Теорему Уитни об изоморфизме графов можно распространить на гиперграфы.

Признание изоморфизма графа

Хотя изоморфизм графа может изучаться классическим математическим способом, как это демонстрирует теорема Уитни, признается, что это задача, которую следует решать с помощью алгоритмического подхода. Вычислительная задача определения изоморфности двух конечных графов называется задачей об изоморфизме графа. Его практические применения включают, прежде всего, химиоинформатику, математическую химию (идентификацию химических соединений) и автоматизированное проектирование электронных схем (проверку эквивалентности различных представлений схемы электронной цепи). Задача об изоморфизме графа является одной из немногих стандартных задач в теории вычислительной сложности, принадлежащих классу NP, но не известных как принадлежащих ни к одному из его хорошо известных (и, если P ≠ NP, не пересекающихся) подмножеств: P и NP-полных. Это одна из двух из двенадцати задач, чья сложность остается неразрешенной, другая – факторизация целых чисел. Однако известно, что если задача является NP-полной, то полиномиальная иерархия схлопывается до конечного уровня. В ноябре 2015 года Ласло Бабаи, математик и ученый-компьютерщик из Чикагского университета, заявил, что доказал разрешимость задачи об изоморфизме графа за квазиполиномиальное время. Он опубликовал предварительные версии этих результатов в материалах Симпозиума по теории вычислений 2016 года и Международного конгресса математиков 2018 года. В январе 2017 года Бабаи временно отозвал утверждение о квазиполиномиальности и заявил о субекспоненциальной временной сложности. Он восстановил первоначальное утверждение через пять дней. По состоянию на 2020 год полная версия статьи Бабая еще не опубликована. Обобщение этой задачи, задача об изоморфизме подграфа, известна как NP-полная. Основные направления исследований в этой области – разработка быстрых алгоритмов и теоретические исследования вычислительной сложности, как для общей задачи, так и для специальных классов графов. Тест на изоморфизм графа Вайсфейлера — Лемана может использоваться для эвристической проверки изоморфности графов. Если тест не проходит, то два входных графа гарантированно неизоморфны. Если тест проходит успешно, графики могут быть как изоморфными, так и неизоморфными. Существуют обобщения этого алгоритма тестирования, которые гарантированно обнаруживают изоморфизмы, однако их время работы экспоненциально. Другой известный алгоритм для изоморфизма графов – алгоритм vf2, разработанный Корделлой и др. в 2001 году. Алгоритм vf2 – это алгоритм поиска в глубину, который пытается построить изоморфизм между двумя графами инкрементно. Он использует набор правил осуществимости для отсечения пространства поиска, что позволяет эффективно обрабатывать графы с тысячами вершин. Алгоритм vf2 широко используется в различных приложениях, таких как распознавание образов, компьютерное зрение и биоинформатика. Хотя в худшем случае он имеет экспоненциальную временную сложность, на практике он хорошо работает для многих типов графов.