Изоморфизм графов
В теории графов изоморфизмом графов [math]\displaystyle{ G=\left \langle V_G, E_G \right \rangle }[/math] и [math]\displaystyle{ H=\left \langle V_H, E_H \right \rangle }[/math] называется биекция между множествами вершин графов [math]\displaystyle{ f \colon\ V_G \rightarrow V_H }[/math] такая, что любые две вершины [math]\displaystyle{ u }[/math] и [math]\displaystyle{ v }[/math] графа [math]\displaystyle{ G }[/math] смежны тогда и только тогда, когда вершины [math]\displaystyle{ f(u) }[/math] и [math]\displaystyle{ f(v) }[/math] смежны в графе [math]\displaystyle{ H }[/math]. Здесь графы понимаются неориентированными и не имеющими весов вершин и ребер. В случае, если понятие изоморфизма применяется к ориентированным или взвешенным графам, накладываются дополнительные ограничения на сохранение ориентации дуг и значений весов. Если изоморфизм графов установлен, они называются изоморфными и обозначаются как [math]\displaystyle{ G\simeq H }[/math].
Иногда биекция [math]\displaystyle{ f }[/math] записывается в виде подстановки изоморфизма [math]\displaystyle{ \begin{pmatrix} a_1 & a_2 & \dots & a_n \\ f(a_1) & f(a_2) & \dots & f(a_n) \end{pmatrix} }[/math]. Некоторые задачи обработки графов требуют не только проверки изоморфизма, но и выяснения его подстановки.
Отношение изоморфизма графов представляет собой отношение эквивалентности, определенное для графов, и позволяет произвести разбиение исходного класса всех графов на классы эквивалентности. Множество графов, изоморфных друг другу, называется классом изоморфизма графов[англ.], их число в зависимости от [math]\displaystyle{ n }[/math] представляет собой последовательность A000088 в OEIS (1, 1, 2, 4, 11, 34, 156, 1044, 12346, ...).
В случае, если биекция [math]\displaystyle{ f }[/math] отображает граф сам на себя (графы [math]\displaystyle{ G }[/math] и [math]\displaystyle{ H }[/math] совпадают), она называется автоморфизмом графа [math]\displaystyle{ G }[/math].
Существуют также смежные задачи теории графов, такие как поиск изоморфного подграфа и поиск максимального общего изоморфного подграфа[англ.], принадлежащие к классу NP-полных. В смежных разделах математики существуют схожие проблемы, например изоморфизма проективных плоскостей и изоморфизма конечных групп, которые полиномиально сводятся к проблеме изоморфизма графов (возможность обратной полиномиальной сводимости в общем случае не доказана)[1].
Пример
Два графа, приведенные в примере, являются изоморфными.
| Граф [math]\displaystyle{ G }[/math] | Граф [math]\displaystyle{ H }[/math] | Изоморфизм между графами [math]\displaystyle{ G }[/math] и [math]\displaystyle{ H }[/math] | Подстановка изоморфизма [math]\displaystyle{ f }[/math] |
|---|---|---|---|
|
|
[math]\displaystyle{ f(a)=1 }[/math] [math]\displaystyle{ f(b)=6 }[/math] |
[math]\displaystyle{ \begin{pmatrix} a & b & c & d & g & h & i & j \\ 1 & 6 & 8 & 3 & 5 & 2 & 4 & 7 \end{pmatrix} }[/math] |
Изоморфизм графов общего вида
Графы [math]\displaystyle{ G }[/math] и [math]\displaystyle{ H }[/math] являются изоморфными, если путём перестановки строк и столбцов матрицы смежности графа [math]\displaystyle{ G }[/math] удается получить матрицу смежности графа [math]\displaystyle{ H }[/math]. Однако перебор всех возможных перестановок характеризуется вычислительной сложностью [math]\displaystyle{ O(N!) }[/math] (при условии, что сравнение матриц смежности производится за время, не зависящее от [math]\displaystyle{ N }[/math], что обычно несправедливо и дополнительно увеличивает приведенную оценку), что существенно ограничивает применение подобного подхода на практике. Существуют методы ограниченного перебора возможных пар предположительно-изоморфных вершин (аналог метода ветвей и границ), однако они незначительно улучшают приведенную выше асимптотику[2].
Теорема Уитни
Теорема Уитни об изоморфизме графов [3][4], сформулированная Хасслером Уитни в 1932 году, гласит, что два связных графа изоморфны, тогда и только тогда, когда их рёберные графы изоморфны, за исключением графов [math]\displaystyle{ K_3 }[/math] (полного графа из 3 вершин) и полного двудольного графа [math]\displaystyle{ K_{1,3} }[/math], которые не являются изоморфными, однако оба имеют граф [math]\displaystyle{ K_3 }[/math] в качестве рёберного графа. Теорема Уитни может быть обобщена для гиперграфов [5].
Инварианты
Существует набор числовых характеристик графов, называемых инвариантами, которые совпадают у изоморфных графов (совпадение инвариантов является необходимым, но не достаточным условием наличия изоморфизма)[6]. К ним относятся число вершин [math]\displaystyle{ n(G) }[/math] и число дуг/ребер [math]\displaystyle{ m(G) }[/math] графа G, упорядоченный по возрастанию или убыванию вектор степеней вершин [math]\displaystyle{ s(G)=(\rho(v_1), \rho(v_2), \dots, \rho(v_n)) }[/math], упорядоченный по возрастанию или убыванию вектор собственных чисел матрицы смежности графа (спектр графа), хроматическое число [math]\displaystyle{ \chi(G) }[/math] и др. Факт совпадения инвариантов обычно не несет информации о подстановке изоморфизма.
Инвариант называется полным, если совпадения инвариантов графов необходимо и достаточно для установления изоморфизма. Например, каждое из значений [math]\displaystyle{ \mu_{min}(G) }[/math] и [math]\displaystyle{ \mu_{max}(G) }[/math] (мини- и макси-код матрицы смежности) является полным инвариантом для графа с фиксированным числом вершин [math]\displaystyle{ n }[/math].
Различные инварианты имеют различную трудоемкость вычисления. В настоящее время полный инвариант графа, вычислимый за полиномиальное время, неизвестен, однако не доказано, что он не существует. Попытки его отыскания неоднократно предпринимались в 60-х — 80-х годах XX века, однако не увенчались успехом.
Модульное произведение Визинга
Модульное произведение графов [math]\displaystyle{ Y=G \lozenge H }[/math], предложенное В. Г. Визингом, позволяет свести задачу проверки изоморфизма к задаче определения плотности графа [math]\displaystyle{ \varphi (Y) }[/math], содержащего [math]\displaystyle{ n(G) \cdot n(H) }[/math] вершин. Если [math]\displaystyle{ \varphi(Y) = n(G) }[/math], [math]\displaystyle{ n(G) \le n(H) }[/math], то граф [math]\displaystyle{ H }[/math] содержит подграф, изоморфный графу [math]\displaystyle{ G }[/math].
Изоморфизм графов специального вида
 | Этот раздел не завершён. |
Вычислительная сложность
Хотя задача распознавания изоморфизма графов принадлежит классу NP, неизвестно, является ли она NP-полной или принадлежит классу P (при условии, что P ≠ NP). При этом задача поиска изоморфного подграфа в графе является NP-полной. Современные исследования направлены на разработку быстрых алгоритмов решения как общей задачи изоморфизма произвольных графов, так и графов специального вида.
Применения
На практике необходимость проверки изоморфизма графов возникает при решении задач хемоинформатики, математической (компьютерной) химии[7], автоматизации проектирования электронных схем (верификация различных представлений электронной схемы)[2], оптимизации программ (выделение общих подвыражений).
См. также
- Инвариант (математика)
- Открытые математические проблемы
- Задача поиска изоморфного подграфа
- Проблема поиска максимального общего изоморфного подграфа[англ.]
Ссылки
- Проблема изоморфизма графов Архивная копия от 18 мая 2015 на Wayback Machine // Курс видео-лекций И. Пономаренко
Примечания
- ↑ Пономаренко И. Н. Проблема изоморфизма графов: алгоритмические аспекты (записки к лекциям) Архивная копия от 22 июня 2018 на Wayback Machine
- ↑ 2,0 2,1 Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР. — М.: Радио и связь, 1990. — 216 с.
- ↑ H. Whitney. Congruent graphs and the connectivity of graphs // Am. J. Math.. — 1932. — Т. 54. — С. 160-168. — doi:10.2307/2371086.
- ↑ Харари Ф. Теория графов. — М.: Мир, 1973. Архивировано 10 сентября 2011 года. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
- ↑ Dirk L. Vertigan, Geoffrey P. Whittle. A 2-Isomorphism Theorem for Hypergraphs // J. Comb. Theory, Ser. B. — 1997. — Т. 71, вып. 2. — С. 215-230. — doi:10.1006/jctb.1997.1789. Архивировано 28 февраля 2013 года.
- ↑ Зыков А. А. . Основы теории графов. — М.: Наука, 1986. — 384 с. — ISBN 978-5-9502-0057-1.
- ↑ Трофимов М. И., Смоленский Е. А. Применение индексов электроотрицательности органических молекул в задачах химической информатики // Известия Академии наук. Серия химическая. — 2005. — С. 2166—2176.