Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]


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

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


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


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


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


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


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


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


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


Определение 5.14. Отображение h\colon V_1\to V_2 множества вершин графа G_1=(V_1,\rho_1) в множество вершин графа G_2=(V_2,\rho_2) называют гомоморфизмом графов (графа G_1 в граф G_2), если для любых двух вершин, смежных в первом графе, их образы при отображении h смежны во втором графе, т.е. если


(\forall u,v\in V_1)\bigl(u\,\rho_1\,v~ \Rightarrow~ h(u)\,\rho_2\,h(v)\bigr).

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


(\forall u,v\in V_1)\bigl(u\,\rho_1\,v~ \Leftrightarrow~ h(u)\,\rho_2\,h(v)\bigr),

называют изоморфизмом графов G_1 и G_2 (графа G_1 на граф G_2), а графы G_1 и G_2 — изоморфными, что записывают в виде G_1\cong G_2.


Гомоморфизм графов, который является эпиморфизмом, называется также гомоморфизмом одного графа на другой.


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


Гомоморфизм неориентированного графа G_1=(V_1,E_1) в неориентированный граф G_2=(V_2,E_2) есть такое отображение h\colon V_1\to V_2, что для любых двух вершин первого графа, соединенных ребром, их образы при отображении h также соединены ребром, т.е.


(\forall u,v\in V_1)\bigl(\{u,v\}\in E_1~ \Rightarrow~ \{h(u),h(v)\}\in E_2\bigr).

Гомоморфизм ориентированного графа G_1=(V_1,E_1) в ориентированный граф G_2=(V_2,E_2) есть такое отображение h\colon V_1\to V_2, что для любых двух вершин u,\,v первого графа, таких, что есть дуга, ведущая из u в {v}, из вершины h(u) тоже ведет дуга в h(v), т.е.


(\forall u,v\in V_1)\bigl((u,v)\in E_1~ \Rightarrow~ (h(u),h(v))\in E_2\bigr).

Изоморфизм неориентированного графа G_1 на неориентированный граф G_2 есть такая биекция h\colon V_1\to V_2, при которой две вершины u и {v} графа G_1 соединены ребром тогда и только тогда, когда соединены ребром их образы h(u) и h(v), т.е.


(\forall u,v\in V_1)\bigl(u \shortmid\!\!\!-\!\!\!\shortmid v~ \Leftrightarrow~ h(u) \shortmid\!\!\!-\!\!\!\shortmid h(v)\bigr).

Аналогично изоморфизм ориентированного графа G_1 на ориентированный граф G_2 есть такая биекция h\colon V_1\to V_2, при которой в ориентированном графе G_1 из вершины u ведет дуга в вершину {v} тогда и только тогда, когда в ориентированном графе G_2 из образа h(u) вершины u ведет дуга в образ h(v) вершины {v}, т.е.


(\forall u,v\in V_1)\bigl(u \to v~ \Leftrightarrow~ h(u) \to h(v)\bigr).



Пример 5.12. а. На рис. 5.29 отображение h, где h(v_1)= w_1, h(v_2)=w_2, h(v_3)=h(v_4)=w_3 есть гомоморфизм ориентированного графа G_1 в ориентированный граф G_2.


Гомоморфизм ориентированного графа в ориентированный граф

Обратим внимание на петлю (w_3,w_3): эта петля является образом дуги (v_4,v_3), так как h(v_4)=w_3 и h(v_3)=w_3. В противоположность этому петля (w_1,w_1) не имеет прообраза в G_1.


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


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


Неориентированный граф как строгий гомоморфный образ другого графа

в. На рис. 5.31 отображение h не является гомоморфизмом G_1 на G_2, поскольку v_1\to v_2, но h(v_1)\nrightarrow h(v_2) (петли (w_1,w_1) нет); h(v_2)\nrightarrow h(v_3), хотя v_2\to v_3 и т.д. Легко сообразить, что любой двухвершинный гомоморфный образ графа G_1 на рис. 5.31 должен иметь петлю, и, следовательно, G_2 не является гомоморфным образом G_1 ни при каком отображении.


Двухвершинный гомоморфный образ графа и один граф из множества двухвершинных гомоморфных образов

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


д. Графы, изображенные на рис. 5.33, изоморфны, и изоморфизмом является, например, отображение h, такое, что


h(v_1)=w_1,\quad h(v_2)=w_4,\quad h(v_3)=w_2,\quad h(v_4)=w_5,\quad h(v_5)=w_3,\quad h(v_6)=w_6.

Изоморфность графов



Дополнения графов


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


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


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


Изоморфность графов и их дополнений

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




Автоморфизм графов


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


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


Рассмотрим некоторые примеры групп автоморфизмов.


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


Примеры групп автоморфизмов графов

Нетривиальные (т.е. отличные от тождественной подстановки) автоморфизмы неориентированного графа

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




Пример 5.13. Найдем нетривиальные (т.е. отличные от тождественной подстановки) автоморфизмы неориентированного графа, изображенного на рис. 5.36. Так как среди вершин графа лишь одна вершина v_1 имеет степень 1 и лишь одна вершина v_4 имеет степень 2, то при любом изоморфизме эти вершины перейдут в себя. Значит, при изоморфизме возможны лишь перестановки вершин v_2,\,v_3 и v_5.


Итак, для любого автоморфизма h этого графа h(v_1)=v_1. Поскольку v_1 \shortmid\!\!\!-\!\!\!\shortmid v_2, то h(v_1) \shortmid\!\!\!-\!\!\!\shortmid h(v_2), и, следовательно, поскольку v_2 — единственная вершина, смежная с h_1, всегда h(v_2)=v_2, т.е. вершина v_2 переходит в себя. Таким образом, единственным нетривиальным автоморфизмом данного графа будет транспозиция (2~5) — "отражение" квадрата v_2v_3v_4v_5 относительно диагонали v_2v_4.




Граф и автоморфизм

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


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


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


\varphi=\begin{pmatrix}1&2&3\end{pmatrix}\!\! \begin{pmatrix}4&6&8\end{pmatrix}\!\! \begin{pmatrix}5&7&9\end{pmatrix}\,.

Заметим, что ни один цикл, входящий в \varphi, сам по себе не будет автоморфизмом данного графа. Так, если мы рассмотрим цикл


h=(1~2~3), то h(3)=1,~h(4)=4 и h(3)\shortmid\!\!\!-\!\!\!\shortmid h(4), но v_3 \shortmid\!\not\!-\!\!\!\shortmid v_4.



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


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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2019 MathHelpPlanet.com. All rights reserved