36
правок
Изменения
Нет описания правки
{{Определение
|definition=
Непустое множество А вместе с заданной на нем бинарной операцией, результат применения которой к элементам <tex>\alpha_1</tex> и <tex>\alpha_2</tex> из <tex>A</tex> обозначается через <tex>\alpha_1\alpha_2</tex> , образует '''группу'''(англ. ''group''), если выполняются следующие четыре аксиомы:
# Аксиома замыкания. <tex>\forall \alpha_1, \alpha_2 \in A </tex>, элемент <tex>\alpha_1\alpha_2 \in A </tex>.
# Аксиома ассоциативности. <tex>\forall \alpha_1, \alpha_2, \alpha_3 \in A </tex>, справедливо равенство <tex>\alpha_1(\alpha_2\alpha_3) = (\alpha_1\alpha_2)\alpha_3</tex>
{{Определение
|definition=
'''Подстановка''' (англ. ''Permutation'') {{---}} взаимно однозначное отображение конечного множества на себя.
}}
{{Определение
|definition=
Если некоторая совокупность подстановок замкнута относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве, то аксиомы 2, 3 и 4 автоматически выполняются и эта совокупность называется '''группой подстановок'''(англ. ''permutation group'').
}}
{{Определение
|definition=
'''Автоморфизмом''' (англ. ''Automorphism'') графа <tex>G</tex> называется изоморфизм графа <tex>G</tex> на себя
}}
{{Определение
|definition=
Каждый автоморфизм <tex>\alpha</tex> графа <tex>G</tex> есть подстановка множества вершин <tex>V</tex>, сохраняющая смежность. Конечно, подстановка <tex>\alpha</tex> переводит любую вершину графа в вершину той же степени. Очевидно, что последовательное выполнение двух автоморфизмов есть также автоморфизм; поэтому автоморфизмы графа <tex> G </tex> образуют группу подстановок <tex> \Gamma (G) </tex>, действующую на множестве вершин <tex>V(G)</tex>. Эту группу называют '''группой''' или иногда '''вершинной группой графа''' <tex>G</tex>(англ. ''point-group'').
}}
{{Определение
|definition=
Вершинная группа графа <tex>G</tex> индуцирует другую группу подстановок <tex> \Gamma_1 (G) </tex>, называемую '''реберной группой графа''' <tex>G</tex>; она действует на множестве ребер <tex>E(G)</tex>(англ. ''line-group'').
}}
''Случай 2.'' Вершины <tex>u</tex> и <tex>v</tex> не смежны. Пусть <tex>x</tex> — произвольное ребро, инцидентное вершине <tex>u</tex>. Тогда <tex>\alpha'(x) \not= x</tex>, следовательно, <tex>\alpha'\not=i</tex>.
}}
==Операции на группах подстановок==
'''Сумма подстановок''' <tex>A + B</tex> {{---}} это группа подстановок, действующая на объединении <tex>X \cup Y</tex> непересекающихся множеств <tex>X</tex> и <tex>Y</tex> элементы которой записываются в виде <tex>\alpha + \beta</tex> и представляют собой упорядоченные пары подстановок <tex>\alpha</tex> из <tex>A</tex> и <tex>\beta</tex> из <tex>B</tex>. Каждый элемент <tex>z</tex>, принадлежащий множеству <tex>X \cup Y</tex> преобразуется подстановкой <tex>\alpha + \beta</tex> по правилу
<tex>
(\alpha + \beta)(z) =
\begin{cases}
\alpha z, z \in X, \\
\beta z, z \in Y.
\end{cases}
</tex>
'''Произведение групп''' <tex>A \times B </tex> {{---}} это группа подстановок, действующая на множестве <tex>X\times Y</tex>, элементы которой записываются в виде <tex>\alpha\times\beta</tex> и представляют собой упорядоченные пары подстановок <tex>\alpha</tex> из <tex>A</tex> и <tex>\beta</tex> из <tex>B</tex>. Элемент <tex>(x,y)</tex> множества <tex>X\times Y</tex> преобразуется подстановкой <tex>\alpha\times\beta</tex> естественным образом:
<tex>(\alpha\times\beta)(x,y)=(\alpha x,\beta y)</tex>
'''Композиция групп''' <tex>A[B]</tex> группы <tex>A</tex> относительно группы <tex>B</tex> также действует на множестве <tex>X\times Y</tex>. Для любой подстановки <tex>\alpha</tex> из <tex>A</tex> и любой последовательности <tex>(\beta_1,\beta_2,\ldots,\beta_d)</tex>, содержащей <tex>d</tex> (не обязательно различных) подстановок из <tex>B</tex>, существует единственная подстановка из <tex>A[B]</tex>, которая записывается в виде <tex>(\alpha;\beta_1,\beta_2,\ldots,\beta_d)</tex>, такая, что для всякой пары <tex>(x_i , y_i)</tex> из <tex>X\times Y</tex> выполняется равенство
<tex>(\alpha;\beta_1,\beta_2,\ldots,\beta_d)(x_i , y_j) = (\alpha x_i,\beta_i y_j).</tex>
'''Степенная группа''' (обозначается <tex>B^A</tex>) действует на множестве <tex>Y^X</tex> всех функций, отображающих <tex>X</tex> в <tex>Y</tex>. Будем всегда предполагать, что степенная группа действует на множестве, состоящем более чем из одной функции. Для каждой пары подстановок <tex>\alpha</tex> из <tex>A</tex> и <tex>\beta</tex> из <tex>B</tex> существует единственная подстановка из <tex>B^A</tex> (записывается <tex>\beta^\alpha</tex>), которая действует на любую функцию <tex>f</tex> из <tex>Y^X</tex> в соответствии со следующим соотношением, определяющим образ каждого элемента <tex>x\in X</tex> при отображении <tex>\beta^\alpha f</tex>:
<tex>(\beta^\alpha f)(x)=\beta f(\alpha x).</tex>
==См. также==
