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

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

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

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

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


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

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


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


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


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


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


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


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


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


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


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

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


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

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


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


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


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


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

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


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

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


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

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


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



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


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

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


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


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


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

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


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

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


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


[math]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.[/math]

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



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


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


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


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


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

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




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


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


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


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


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


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

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

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




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


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




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

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


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


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


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

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


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



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


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


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


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

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