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

Для ориентированного графа (V, Е) множество Е дуг можно рассматривать как график бинарного отношения непосредственной достижимости, заданного на множестве вершин.

В неориентированном графе (V, Е) множество Е ребер является множеством неупорядоченных пар. Для каждой неупорядоченной пары {u, v} ∈ Е можно считать, что вершины u и v связаны симметричным бинарным отношением р, т.е. (u, v) ∈ р и (v, u) ∈ р.

Таким образом, с каждым неориентированым и ориентированным графом связано бинарное отношение р. Это отношение будем называть отношением смежности.

С алгебраической точки зрения как ориентированный, так и неориентированный граф можно рассматривать как модель, сигнатура которой состоит из одного бинарного отношения: g = (V, р). В классической теории графов изучаются преимущественно конечные модели такого рода.

При указанном подходе различия между ориентированным и неориентированным графами проявляется только в свойствах отношения смежности р. Если это отношение симметрично, то граф называют неориентированным, и с этой точки зрения неориентированный граф можно считать частным случаем ориентированного*.

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

Определение 5.14. Отображение h: V₁ → V₂ множества вершин графа G₁ = (V₁, р₁) в множество вершин графа G₂ = (V₂, р₂) называют гомоморфизмом графов (графа G₁ в граф G₂), если для любых двух вершин, смежных в первом графе, их образы при отображении h смежны во втором графе, т.е. если

(∀u,v ∈ V₁)(u p₁ v ⇒ h(u) p₂ h(v)),

Биективный гомоморфизм h, такой, что любые две вершины смежны в первом графе тогда и только тогда, когда их образы смежны во втором графе, т.е.

(∀u,v ∈ V₁)(u p₁ v ⇔ h(u) p₂ h(v)),

называют изоморфизмом графов G₁ и G₂ (графа G₁ на граф G₂), а графы G₁ и G₂ — изоморфными, что записывают в виде G_{1 ≅ G2}.

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

*При таком подходе в неориентированном графе могут быть петли, если отношение р содержит некоторые элементы диагонали, в частности является рефлексивным.

Гомоморфизм неориентированного графа G₁ = (V₁, E₁) в неориентированный граф G₂ = (V₂, E₂) есть такое отображение h: V₁ → V₂, что для любых двух вершин первого графа, соединенных ребром, их образы при отображении h также соединены ребром, т.е.

(∀u,v ∈ V₁)({u,v} ∈ E₁ ⇒ {h(u), h(v)} ∈ E₂).

Гомоморфизм ориентированного графа G₁ = (V₁, E₁) в ориентированный граф G₂ = (V₂, E₂) есть такое отображение h: V₁ → V₂, что для любых двух вершин u, v первого графа, таких, что есть дуга, ведущая из u в v, из вершины h(u) тоже ведет дуга в h(v), т.е.

(∀u,v ∈ V₁)((u,v) ∈ E₁ ⇒ (h(u), h(v)) ∈ E₂).

Изоморфизм неориентированного графа G₁ на неориентированный граф G₂ есть такал биекция h: V₁ → V₂, при которой две вершины u и v графа G₁ соединены ребром тогда и только тогда, когда соединены ребром их образы h(u) и h(v), т.е.

(∀u,v ∈ V₁)(uv ⇔ h(u)h(v)).

Аналогично изоморфизм ориентированного графа G₁ на ориентированный граф G₂ есть такая биекция h: V₁ → V₂, при которой в ориентированном графе G₁ из вершины u ведет дуга в вершину v тогда и только тогда, когда в ориентированном графе G₂ из образа h(u) вершины и ведет дуга в образ h(v) вершины v, т.е.

(∀u,v ∈ V₁)(u → v ⇔ h(u) → h(v)).

Пример 5.12. а. На рис. 5.29 отображение h, где h(v₁) = w₁, h(v₂) = w₂, h(v₃) = h(v₄) = w₃, есть гомоморфизм ориентированного графа G₁ в ориентированный граф G₂.

Обратим внимание на петлю (w₃, w₃): эта петля является образом дуги (v₄, v₃), так как h(v₄) = w₃ и h(v₃) = w₃. В противоположность этому петля (w₁, w₁) не имеет прообраза в G₁.

На этом же рисунке более толстыми стрелками выделен подграф G'₂ графа G₂, порожденный подмножеством вершин {w₁, w₂, w₁}. Этот подграф будет гомоморфным образом графа G₁. Удаляя петлю в вершине w₁, получим (для того же подмножества вершин) порожденный подграф, являющийся строгим гомоморфным образом графа G₁. Отметим, что каждая дуга в строгом гомоморфном образе ориентированного графа G₁ имеет прообраз в G₁.

б. На рис. 5.30 неориентированный граф G₂ есть строгий гомоморфный образ графа G₁ (если рассматривать неориентированные графы без петель).

в. На рис. 5.31 отображение h не является гомоморфизмом G₁ на G₂, поскольку v₁ → v₂, но h(v₁) ≁ h(v₂) (петли (w₁, w₁) нет); h(v₂) ≁ h(v₃), хотя v₂ → v₃ и т.д. Легко сообразить, что любой двухвершинный гомоморфный образ графа G₁ на рис. 5.31 должен иметь петлю, и, следовательно, G₂ не является гомоморфным образом G₁ ни при каком отображении.

г. На рис. 5.32 изображен один граф из множества двухвершинных гомоморфных образов G₁.

д. Графы, изображенные на рис. 5.33, изоморфны, и изоморфизмом является, например, отображение h, такое, что h(v₁) = w₁, h(v₂) = w₄, h(v₃) = w₂, h(v₄) = w₅, h(v₅) = w₃, h(v₆) = w₆. #

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

Определение 5.15. Неориентированный (ориентированный) граф G = V;E называют дополнением неориентированного (ориентированного) графа G = (V, E), где E — дополнение множества Е до множества всех неупорядоченных (упорядоченных пар) на V.

Можно доказать, что графы изоморфны тогда и только тогда, когда изоморфны их дополнения. Например, перейдем к дополнениям графов, изображенных на рис. 5.33. Анализ указанных дополнений (рис. 5.34) позволяет сразу обнаружить их изоморфизм, а следовательно, и изоморфизм исходных графов.

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

Определение 5.16. Автоморфизм графа G = (V, р) — это любая подстановка множества его вершин, являющаяся изоморфизмом G на себя.

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

Для графа, изображенного на рис. 5.35, а, группа автоморфизмов порождается транспозициями (1 4) и (2 3), что легко усматривается из анализа дополнения этого графа (рис. 5.35, б). Очевидно, что группа автоморфизмов графа есть подгруппа группы перестановок множества его вершин. Поэтому, согласно теореме 2.13 Лагранжа, порядок группы автоморфизмов графа есть делитель факториала числа его вершин. В частности, для графа на рис. 5.35, а группа автоморфизмов имеет порядок 4 и состоит из тождественной подстановки ε и подстановок (1 4), (2 3), (1 4) (2 3). Очевидно, что 4! делится на 4.

Можно доказать, что автоморфизмы неориентированного графа сохраняют степени, а ориентированого графа — полустепени исхода и захода всех его вершин. Это свойство позволяет упростить описание автоморфизмов графа.

Пример 5.13. Найдем нетривиальные (т.е. отличные от тождественной подстановки) автоморфизмы неориентированного графа, изображенного на рис. 5.36. Так как среди вершин графа лишь одна вершина v1 имеет степень 1 и лишь одна вершина v4 имеет степень 2, то при любом изоморфизме эти вершины перейдут в себя. Значит, при изоморфизме возможны лишь перестановки вершин v2, v3 и v5.

Итак, для любого автоморфизма h этого графа h(v₁) = v₁. Поскольку v₁v₂ то h(v₁)h(v₂), и, следовательно, поскольку v₂ — единственная вершина, смежная с v₁, всегда h(v₂) = v₂, т.е. вершина v₂ переходит в себя. Таким образом, единственным нетривиальным автоморфизмом данного графа будет транспозиция (3 5) — „отражение" квадрата v₂v₃v₄v₅ относительно диагонали v₂v₄. #

Иногда группу автоморфизмов графа легко найти именно из чисто геометрических соображений при удачном изображении графа. Автоморфизм есть не что иное, как преобразование графа (геометрической фигуры), при котором граф совмещается с самим собой. Поэтому группу автоморфизмов графа можно изучать, анализируя его как геометрическую фигуру.

Пример 5.14. Для графа, изображенного на рис. 5.37, из геометрических соображений вытекает, что автоморфизм φ сводится к повороту графа на 60° по часовой стрелке вокруг центра тяжести треугольника v₁v₂v₃.

Следовательно, группа автоморфизмов порождается подстановкой φ, являющейся композицией трех циклов:

φ = (1 2 3)(4 6 8)(5 7 9).

Заметим, что ни один цикл, входящий в φ, сам по себе не будет автоморфизмом данного графа. Так, если мы рассмотрим цикл h = (1 2 3), то h(3) = 1, h(4) = 4, и h(3)h(4), но v₃v₄. #

В заключение сформулируем без доказательства теорему, доказанную Фрухтом в 1938 г. и характеризующую все конечные группы в терминах групп автоморфизмов конечных неориентированных графов.

Теорема 5.5 (теорема Фрухта). Каждая конечная группа изоморфна группе автоморфизмов конечного неориентированного графа.