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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Иногда биекция записывается в виде подстановки изоморфизма . Некоторые задачи обработки графов требуют не только проверки изоморфизма, но и выяснения его подстановки.

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

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

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

Пример[править | править вики-текст]

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

Граф Граф Изоморфизм между графами и Подстановка изоморфизма
Graph isomorphism 1.gif Graph isomorphism 2.gif







Изоморфизм графов общего вида[править | править вики-текст]

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

Теорема Уитни[править | править вики-текст]

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

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

Инварианты[править | править вики-текст]

Существует набор числовых характеристик графов, называемых инвариантами, которые совпадают у изоморфных графов (совпадение инвариантов является необходимым, но не достаточным условием наличия изоморфизма)[6]. К ним относятся число вершин и число дуг/ребер графа G, упорядоченный по возрастанию или убыванию вектор степеней вершин , упорядоченный по возрастанию или убыванию вектор собственных чисел матрицы смежности графа (спектр графа), хроматическое число и др. Факт совпадения инвариантов обычно не несет информации о подстановке изоморфизма.

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

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

Модульное произведение Визинга[править | править вики-текст]

Модульное произведение графов , предложенное В. Г. Визингом (англ.), позволяет свести задачу проверки изоморфизма к задаче определения плотности графа , содержащего вершин. Если , , то граф содержит подграф, изоморфный графу .

Изоморфизм графов специального вида[править | править вики-текст]

Вычислительная сложность[править | править вики-текст]

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

Применения[править | править вики-текст]

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

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Пономаренко И.Н. Проблема изоморфизма графов: алгоритмические аспекты (записки к лекциям)
  2. 1 2 Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР. — М.: Радио и связь, 1990. — 216 с.
  3. H. Whitney (1932). «Congruent graphs and the connectivity of graphs». Am. J. Math. 54: 160-168. DOI:10.2307/2371086.
  4. Харари Ф. Теория графов. — М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
  5. 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.
  6. Зыков А. А.  Основы теории графов. — М.: Наука, 1986. — 384 с. — ISBN 978-5-9502-0057-1.
  7. Трофимов М. И., Смоленский Е. А. Применение индексов электроотрицательности органических молекул в задачах химической информатики // Известия Академии наук. Серия химическая. — 2005. — С. 2166—2176.