Русская Википедия:Изоморфизм графов
В теории графов изоморфизмом графов <math>G=\left \langle V_G, E_G \right \rangle</math> и <math>H=\left \langle V_H, E_H \right \rangle</math> называется биекция между множествами вершин графов <math>f \colon\ V_G \rightarrow V_H</math> такая, что любые две вершины <math>u</math> и <math>v</math> графа <math>G</math> смежны тогда и только тогда, когда вершины <math>f(u)</math> и <math>f(v)</math> смежны в графе <math>H</math>. Здесь графы понимаются неориентированными и не имеющими весов вершин и ребер. В случае, если понятие изоморфизма применяется к ориентированным или взвешенным графам, накладываются дополнительные ограничения на сохранение ориентации дуг и значений весов. Если изоморфизм графов установлен, они называются изоморфными и обозначаются как <math>G\simeq H</math>.
Иногда биекция <math>f</math> записывается в виде подстановки изоморфизма <math>\begin{pmatrix} a_1 & a_2 & \dots & a_n \\ f(a_1) & f(a_2) & \dots & f(a_n) \end{pmatrix}</math>. Некоторые задачи обработки графов требуют не только проверки изоморфизма, но и выяснения его подстановки.
Отношение изоморфизма графов представляет собой отношение эквивалентности, определенное для графов, и позволяет произвести разбиение исходного класса всех графов на классы эквивалентности. Множество графов, изоморфных друг другу, называется Шаблон:Нп1, их число в зависимости от <math>n</math> представляет собой Шаблон:OEIS (1, 1, 2, 4, 11, 34, 156, 1044, 12346, ...).
В случае, если биекция <math>f</math> отображает граф сам на себя (графы <math>G</math> и <math>H</math> совпадают), она называется автоморфизмом графа <math>G</math>.
Существуют также смежные задачи теории графов, такие как поиск изоморфного подграфа и Шаблон:Нп1, принадлежащие к классу NP-полных. В смежных разделах математики существуют схожие проблемы, например изоморфизма проективных плоскостей и изоморфизма конечных групп, которые полиномиально сводятся к проблеме изоморфизма графов (возможность обратной полиномиальной сводимости в общем случае не доказана)[1].
Пример
Два графа, приведенные в примере, являются изоморфными.
| Граф <math>G</math> | Граф <math>H</math> | Изоморфизм между графами <math>G</math> и <math>H</math> | Подстановка изоморфизма <math>f</math> |
|---|---|---|---|
| Файл:Graph isomorphism 1.gif | Файл:Graph isomorphism 2.gif | <math>f(a)=1</math> <math>f(b)=6</math> |
<math>\begin{pmatrix} a & b & c & d & g & h & i & j \\ 1 & 6 & 8 & 3 & 5 & 2 & 4 & 7 \end{pmatrix}</math> |
Изоморфизм графов общего вида
Графы <math>G</math> и <math>H</math> являются изоморфными, если путём перестановки строк и столбцов матрицы смежности графа <math>G</math> удается получить матрицу смежности графа <math>H</math>. Однако перебор всех возможных перестановок характеризуется вычислительной сложностью <math>O(N!)</math> (при условии, что сравнение матриц смежности производится за время, не зависящее от <math>N</math>, что обычно несправедливо и дополнительно увеличивает приведенную оценку), что существенно ограничивает применение подобного подхода на практике. Существуют методы ограниченного перебора возможных пар предположительно-изоморфных вершин (аналог метода ветвей и границ), однако они незначительно улучшают приведенную выше асимптотику[2].
Теорема Уитни
Теорема Уитни об изоморфизме графов [3][4], сформулированная Хасслером Уитни в 1932 году, гласит, что два связных графа изоморфны, тогда и только тогда, когда их рёберные графы изоморфны, за исключением графов <math>K_3</math> (полного графа из 3 вершин) и полного двудольного графа <math>K_{1,3}</math>, которые не являются изоморфными, однако оба имеют граф <math>K_3</math> в качестве рёберного графа. Теорема Уитни может быть обобщена для гиперграфов [5].
Инварианты
Существует набор числовых характеристик графов, называемых инвариантами, которые совпадают у изоморфных графов (совпадение инвариантов является необходимым, но не достаточным условием наличия изоморфизма)[6]. К ним относятся число вершин <math>n(G)</math> и число дуг/ребер <math>m(G)</math> графа G, упорядоченный по возрастанию или убыванию вектор степеней вершин <math>s(G)=(\rho(v_1), \rho(v_2), \dots, \rho(v_n))</math>, упорядоченный по возрастанию или убыванию вектор собственных чисел матрицы смежности графа (спектр графа), хроматическое число <math>\chi(G)</math> и др. Факт совпадения инвариантов обычно не несет информации о подстановке изоморфизма.
Инвариант называется полным, если совпадения инвариантов графов необходимо и достаточно для установления изоморфизма. Например, каждое из значений <math>\mu_{min}(G)</math> и <math>\mu_{max}(G)</math> (мини- и макси-код матрицы смежности) является полным инвариантом для графа с фиксированным числом вершин <math>n</math>.
Различные инварианты имеют различную трудоемкость вычисления. В настоящее время полный инвариант графа, вычислимый за полиномиальное время, неизвестен, однако не доказано, что он не существует. Попытки его отыскания неоднократно предпринимались в 60-х — 80-х годах XX века, однако не увенчались успехом.
Модульное произведение Визинга
Модульное произведение графов <math>Y=G \lozenge H</math>, предложенное В. Г. Визингом, позволяет свести задачу проверки изоморфизма к задаче определения плотности графа <math>\varphi (Y)</math>, содержащего <math>n(G) \cdot n(H)</math> вершин. Если <math>\varphi(Y) = n(G)</math>, <math>n(G) \le n(H)</math>, то граф <math>H</math> содержит подграф, изоморфный графу <math>G</math>.
Изоморфизм графов специального вида
Вычислительная сложность
Шаблон:Falseredirect Хотя задача распознавания изоморфизма графов принадлежит классу NP, неизвестно, является ли она NP-полной или принадлежит классу P (при условии, что P ≠ NP). При этом задача поиска изоморфного подграфа в графе является NP-полной. Современные исследования направлены на разработку быстрых алгоритмов решения как общей задачи изоморфизма произвольных графов, так и графов специального вида.
Применения
На практике необходимость проверки изоморфизма графов возникает при решении задач хемоинформатики, математической (компьютерной) химии[7], автоматизации проектирования электронных схем (верификация различных представлений электронной схемы)[2], оптимизации программ (выделение общих подвыражений).
См. также
- Инвариант (математика)
- Открытые математические проблемы
- Задача поиска изоморфного подграфа
- Шаблон:Нп1
Ссылки
- Проблема изоморфизма графов Шаблон:Wayback // Курс видео-лекций И. Пономаренко
Примечания
- ↑ Пономаренко И. Н. Проблема изоморфизма графов: алгоритмические аспекты (записки к лекциям) Шаблон:Wayback
- ↑ 2,0 2,1 Шаблон:Книга
- ↑ Шаблон:Статья
- ↑ Шаблон:Книга (Изд. 3, М.: КомКнига, 2006. — 296 с.)
- ↑ Шаблон:Статья
- ↑ Шаблон:Книга
- ↑ Шаблон:Статья
