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

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

Непустое множество А вместе с заданной на нем бинарной операцией, результат применения которой к элементам [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].

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

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

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

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