Группы графов

Определение:

Непустое множество А вместе с заданной на нем бинарной операцией, результат применения которой к элементам [math]\alpha_1[/math] и [math]\alpha_2[/math] из [math]A[/math] обозначается через [math]\alpha_1\alpha_2[/math] , образует группу, если выполняются следующие четыре аксиомы: Аксиома замыкания. [math]\forall \alpha_1, \alpha_2 \in A [/math], элемент [math]\alpha_1\alpha_2 \in A [/math]. Аксиома ассоциативности. [math]\forall \alpha_1, \alpha_2, \alpha_3 \in A [/math], справедливо равенство [math]\alpha_1(\alpha_2\alpha_3) = (\alpha_1\alpha_2)\alpha_3[/math] Аксиома тождественности. В множестве [math]A[/math] существует такой элемент [math]i[/math], что [math]i\alpha = \alpha i = \alpha[/math] для [math] \forall \alpha \in A [/math]. Аксиома обращения. Если выполняется аксиома 3, то для [math] \forall \alpha \in A \ \exists \alpha^{-1} : \alpha\alpha^{-1} = \alpha^{-1}\alpha = i [/math].

Определение:

Подстановка — взаимно однозначное отображение конечного множества на себя.

Определение:

Если некоторая совокупность подстановок замкнута относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве, то аксиомы 2, 3 и 4 автоматически выполняются и эта совокупность называется группой подстановок.

Определение:

Автоморфизмом графа [math]G[/math] называется изоморфизм графа [math]G[/math] на себя

Определение:

Каждый автоморфизм [math]\alpha[/math] графа [math]G[/math] есть подстановка множества вершин [math]V[/math], сохраняющая смежность. Конечно, подстановка [math]\alpha[/math] переводит любую вершину графа в вершину той же степени. Очевидно, что последовательное выполнение двух автоморфизмов есть также автоморфизм; поэтому автоморфизмы графа [math] G [/math] образуют группу подстановок [math] \Gamma (G) [/math], действующую на множестве вершин [math]V(G)[/math]. Эту группу называют группой или иногда вершинной группой графа [math]G[/math].

Определение:

Вершинная группа графа [math]G[/math] индуцирует другую группу подстановок [math] \Gamma_1 (G) [/math], называемую реберной группой графа [math]G[/math]; она действует на множестве ребер [math]E(G)[/math].

Для иллюстрации различия групп [math]\Gamma[/math] и [math]\Gamma_1[/math] рассмотрим граф [math]K_4 - х[/math], показанный на рисунке; его вершины помечены [math]v_1 , v_2, v_3, v_4 [/math] а ребра [math]x_1, x_2, x_3, x_4, x_5 [/math]. Вершинная группа [math]\Gamma (K_4 - x) [/math] состоит из четырех подстановок [math](v_1)(v_2)(v_3)(v_4); (v_1)(v_3)(v_2v_4); (v_2)(v_4)(v_1v_3); (v_1v_3)(v_2v_4).[/math]

Тождественная подстановка вершинной группы индуцирует тождественную подстановку на множестве ребер, в то время как подстановка [math](v_1)(v_3)(v_2v_4)[/math] индуцирует подстановку на множестве ребер, в которой ребро [math]x_5[/math] остается на месте, [math] x_1[/math] меняется с [math]x_4[/math], а [math]x_2[/math] с [math]x_3[/math]. Таким образом, реберная группа [math]\Gamma_1 (K_4 - x) [/math] состоит из следующих подстановок, индуцируемых указанными выше элементами вершинной группы: [math](x_1)(x_2)(x_3)(x_4)(x_5); (x_1x_4)(x_2x_3)(x_5); (x_1x_2)(x_3x_4)(x_5); (x_1x_3)(x_2x_4)(x_5).[/math]

Понятно, что реберная и вершинная группы графа [math]K_4 - х[/math] изоморфны. Но они, конечно, не могут быть идентичными, так как степень группы [math]\Gamma_1 (K_4 - x) [/math] равна 5, а степень группы [math]\Gamma (K_4 - x) [/math] равна 4.

Теорема:

Реберная и вершинная группы графа [math]G[/math] изоморфны тогда и только тогда, когда граф [math]G[/math] имеет не более одной изолированной вершины, а граф [math]K_2[/math] не является его компонентой.

Доказательство:

[math]\triangleright[/math]

Пусть подстановка [math]\alpha'[/math] группы [math]\Gamma_1(G)[/math] индуцируется подстановкой [math]\alpha[/math] группы [math]\Gamma(G)[/math]. Из определения операции умножения в группе [math]\Gamma_1(G)[/math] вытекает, что [math]\alpha'\beta'=\alpha\beta[/math] для [math]\forall \alpha,\beta \in \Gamma(G)[/math]. Поэтому отображение [math]\alpha\rightarrow\alpha '[/math] является групповым гомоморфизмом группы [math]\Gamma(G)[/math] на [math]\Gamma_1(G)[/math]. Следовательно, [math]\Gamma(G)\cong\Gamma_1(G)[/math] тогда и только тогда, когда ядро этого отображения тривиально. Для доказательства необходимости предположим, что [math]\Gamma(G)\cong\Gamma_1(G)[/math]. Тогда из неравенства [math]\alpha\not=i[/math]([math]i[/math] — тождественная подстановка) следует, что [math]\alpha'\not=i[/math]. Если в графе [math]G[/math] существуют две различные изолированные вершины [math]v_1[/math] и [math]v_2[/math], то можно определить подстановку [math]\alpha\in\Gamma(G)[/math], положив [math]\alpha(v_1) = v_2, \alpha(v_2) = v_1, \alpha(v) = v[/math] для [math]\forall v \not= v_1,v_2 [/math]. Тогда [math]\alpha\not=i[/math], но [math]\alpha'=i[/math]. Если [math]K_2[/math] — компонента графа [math]G[/math], то, записав ребро графа [math]K_2[/math] в виде [math]x = v_1v_2[/math] и определив подстановку [math]\alpha\in\Gamma(g)[/math] точно так же, как выше, получим [math]\alpha\not=i[/math], но [math]\alpha'=i[/math]. Чтобы доказать достаточность, предположим, что граф [math]G[/math] имеет не больше одной изолированной вершины и [math]K_2[/math] не является его компонентой. Если группа [math]\Gamma(G)[/math] тривиальна, то очевидно, что группа [math]\Gamma_1(G)[/math] оставляет на месте каждое ребро и, следовательно, [math]\Gamma_1(G)[/math] — тривиальная группа. Поэтому предположим, что существует подстановка [math]\alpha\in\Gamma(G)[/math], для которой [math]\alpha(u)=v\not=u[/math]. Тогда степени вершин [math]u[/math] и [math]v[/math] равны. Поскольку вершины [math]u[/math] и [math]v[/math] не изолированы, их степени не равны нулю. Здесь возникает два случая. Случай 1. Вершины [math]u[/math] и [math]v[/math] смежны. Пусть [math]x=uv[/math]. Так как [math]K_2[/math] не является компонентой графа [math]G[/math], то степени обеих вершин [math]u[/math] и [math]v[/math] больше единицы. Следовательно, существует такое ребро [math]y \not= x[/math] инцидентное вершине [math]u[/math], что ребро [math]\alpha'(y)[/math] инцидентно вершине [math]v[/math]. Отсюда [math]\alpha'(y) \not= y[/math], и тогда [math]\alpha'\not=i[/math]. Случай 2. Вершины [math]u[/math] и [math]v[/math] не смежны. Пусть [math]x[/math] — произвольное ребро, инцидентное вершине [math]u[/math]. Тогда [math]\alpha'(x) \not= x[/math], следовательно, [math]\alpha'\not=i[/math].

[math]\triangleleft[/math]

См. также

• Группа
• Википедия — Автоморфизм_графа

Источники информации

• Харари Ф. Теория графов. М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)