Изменения

Непустое множество А вместе с заданной на нем бинарной операцией, результат применения которой к элементам <tex>\alpha_1</tex> и <tex>\alpha_2</tex> из <tex>A</tex> обозначается через <tex>\alpha_1\alpha_2</tex> , образует '''группуАвтоморфизмом''', если выполняются следующие четыре аксиомы: # Аксиома замыкания(англ. <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''Automorphism'')\alpha_3графа </tex># Аксиома тождественности. В множестве <tex>AG</tex> существует такой элемент называется изоморфизм графа <tex>iG</tex>, что <tex>i\alpha = \alpha i = \alpha</tex> для <tex> \forall \alpha \in A </tex>. # Аксиома обращения. Если выполняется аксиома 3, то для <tex> \forall \alpha \in A \ \exists \alpha^{-1} : \alpha\alpha^{-1} = \alpha^{-1}\alpha = i </tex>. на себя

Автоморфизмы графа <tex> G </tex> образуют [[:группа#Группа_подстановок|группу подстановок]] <tex> \Gamma (G) </tex>, действующую на множестве вершин <tex>V(G)</tex>. Эту [[:группа|группу]] называют '''группой''' или иногда '''вершинной группой графа''Подстановка'<tex>G</tex> (англ. '' {{point---}} взаимно однозначное отображение конечного множества на себяgroup'').

Если некоторая совокупность Вершинная группа графа <tex>G</tex> индуцирует другую группу подстановок замкнута относительно композиции отображений<tex> \Gamma_1 (G) </tex>, определяющей бинарную операцию для подстановок на одном и том же множестве, то аксиомы 2, 3 и 4 автоматически выполняются и эта совокупность называется называемую '''реберной группой подстановокграфа''' <tex>G</tex> (англ. ''line-group'') {{---}} она действует на множестве ребер <tex>E(G)</tex>.

[[Файл:fordm.png|right]] Для иллюстрации различия групп <tex>\Gamma</tex> и <tex>\Gamma_1</tex> рассмотрим граф <tex>K_4 - x</tex>, показанный на рисунке; его вершины помечены <tex>v_1 , v_2, v_3, v_4 </tex> а ребра <tex>x_1, x_2, x_3, x_4, x_5 </tex>. Вершинная группа <tex>\Gamma (K_4 - x) </tex> состоит из четырех подстановок<tex>(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).</tex> Тождественная подстановка вершинной группы индуцирует тождественную подстановку на множестве ребер, в то время как подстановка <tex>(v_1)(v_3)(v_2v_4)</tex> индуцирует подстановку на множестве ребер, в которой ребро <tex>x_5</tex> остается на месте, <tex> x_1</tex> меняется с <tex>x_4</tex>, а <tex>x_2</tex> с <tex>x_3</tex>. Таким образом, реберная группа <tex>\Gamma_1 (K_4 - x) </tex> состоит из следующих подстановок, индуцируемых указанными выше элементами вершинной группы: <tex>(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).</tex> Понятно, что реберная и вершинная группы графа <tex>K_4 - x</tex> изоморфны. Но они, конечно, не могут быть идентичными, так как степень группы <tex>\Gamma_1 (K_4 - x) </tex> равна <tex>5</tex>, а степень группы <tex>\Gamma (K_4 - x) </tex> равна <tex>4</tex>.   {{ОпределениеТеорема|statement=Реберная и вершинная группы графа <tex>G</tex> изоморфны тогда и только тогда, когда граф <tex>G</tex> имеет не более одной изолированной вершины, а граф <tex>K_2</tex> не является его компонентой.|definitionproof= Пусть подстановка <tex>\alpha'</tex> группы <tex>\Gamma_1(G)</tex> индуцируется подстановкой <tex>\alpha</tex> группы <tex>\Gamma(G)</tex>. Из определения операции умножения в группе <tex>\Gamma_1(G)</tex> вытекает, что <tex>\alpha'\beta'Автоморфизмом=\alpha\beta</tex> для <tex>\forall \alpha,\beta \in \Gamma(G)</tex>. Поэтому отображение <tex>\alpha\rightarrow\alpha '</tex> является групповым гомоморфизмом группы <tex>\Gamma(G)</tex> на <tex>\Gamma_1(G)</tex>. Следовательно, <tex>\Gamma(G)\cong\Gamma_1(G)</tex> тогда и только тогда, когда ядро этого отображения тривиально.  <tex> \Rightarrow </tex> :Для доказательства необходимости предположим, что <tex>\Gamma(G)\cong\Gamma_1(G)</tex>. Тогда из неравенства <tex>\alpha\not=i</tex>(<tex>i</tex> — тождественная подстановка) следует, что <tex>\alpha'\not=i</tex>. Если в графе <tex>G</tex> существуют две различные изолированные вершины <tex>v_1</tex> и <tex>v_2</tex>, то можно определить подстановку <tex>\alpha\in\Gamma(G)</tex>, положив <tex>\alpha(v_1) = v_2, \alpha(v_2) = v_1, \alpha(v) = v</tex> для <tex>\forall v \not= v_1,v_2 </tex>. Тогда <tex>\alpha\not=i</tex>, но <tex>\alpha' =i</tex>. Если <tex>K_2</tex> {{---}} компонента графа <tex>G</tex> называется изоморфизм , то, записав ребро графа <tex>K_2</tex> в виде <tex>x = v_1v_2</tex> и определив подстановку <tex>\alpha\in\Gamma(g)</tex> точно так же, как выше, получим <tex>\alpha\not=i</tex>, но <tex>\alpha'=i</tex>.  <tex> \Leftarrow </tex> :Чтобы доказать достаточность, предположим, что граф <tex>G</tex> имеет не больше одной изолированной вершины и <tex>K_2</tex> не является его компонентой. Если группа <tex>\Gamma(G)</tex> тривиальна, то очевидно, что группа <tex>\Gamma_1(G)</tex> оставляет на себяместе каждое ребро и, следовательно, <tex>\Gamma_1(G)</tex> {{---}} тривиальная группа. Поэтому предположим, что существует подстановка <tex>\alpha\in\Gamma(G)</tex>, для которой <tex>\alpha(u)=v\not=u</tex>. Тогда степени вершин <tex>u</tex> и <tex>v</tex> равны. Поскольку вершины <tex>u</tex> и <tex>v</tex> не изолированы, их степени не равны нулю. Здесь возникает два случая. <tex<\par</tex> :''Случай 1.'' Вершины <tex>u</tex> и <tex>v</tex> смежны. Пусть <tex>x=uv</tex>. Так как <tex>K_2</tex> не является компонентой графа <tex>G</tex>, то степени обеих вершин <tex>u</tex> и <tex>v</tex> больше единицы. Следовательно, существует такое ребро <tex>y \not= x</tex> инцидентное вершине <tex>u</tex>, что ребро <tex>\alpha'(y)</tex> инцидентно вершине <tex>v</tex>. Отсюда <tex>\alpha'(y) \not= y</tex>, и тогда <tex>\alpha'\not=i</tex>.  :''Случай 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</tex> — группа подстановок порядка <tex>m = |A|</tex> и степени <tex>d</tex>, действующая на множестве <tex>X = \{x_1,x_2,\ldots,x_d\}</tex>, а <tex>B</tex> {{---}} другая группа подстановок порядка <tex>n = |B|</tex> и степени <tex>e</tex>, действующая на множестве <tex>Y = \{y_1,y_2,\ldots,y_e\}</tex>. Например, пусть <tex>A = C_3</tex> {Определение{---}} циклическая группа порядка <tex>3</tex>, действующая на множестве <tex>X={1, 2, 3}</tex>. Эта группа состоит из трех подстановок <tex>(1)(2)(3), (123)</tex> и <tex>(132)</tex>. Если взять в качестве <tex>B</tex> симметрическую группу <tex>S_2</tex> порядка <tex>2</tex>, действующую на множестве <tex>Y = \{a,b\}</tex>, то получим две подстановки <tex>(a)(b)</tex> и <tex>(ab)</tex>. Проиллюстрируем на этих двух группах подстановок действие нескольких бинарных операций.  |definition===Сумма подстановок===<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>C_3 + S_2</tex> содержит <tex>6</tex> подстановок, каждую из которых можно записать в виде суммы подстановок <tex>\alpha \in C_3</tex> и <tex>\beta\in S_2</tex>, как, например, <tex>(123)(ab)=(123)+(ab)</tex>. (степень равна <tex>5</tex>.) ===Произведение групп===<tex>A \times B </tex> {{---}} это группа подстановок, действующая на множестве <tex>X\times Y</tex>, элементы которой записываются в виде <tex>\alpha\times\beta</tex> и представляют собой упорядоченные пары подстановок <tex>\alpha</tex> графа из <tex>GA</tex> и <tex>\beta</tex> из <tex>B</tex>. Элемент <tex>(x,y)</tex> есть подстановка множества вершин <tex>VX\times Y</tex> преобразуется подстановкой <tex>\alpha\times\beta</tex>естественным образом:   <tex>(\alpha\times\beta)(x,y)=(\alpha x, сохраняющая смежность\beta y)</tex>  Подстановкой в группе <tex>C_3\times S_2</tex>, которая соответствует подстановке <tex>(123)+(ab)</tex> будет <tex>(1a\ 2b\ 3a\ 1b\ 2a\ 3b)</tex>, где для краткости символ <tex>(1,a)</tex> заменен на <tex>1a</tex>. (Порядок и степень равны <tex>6</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> G X\times Y</tex> образуют группу подстановок выполняется равенство   <tex> (\alpha;\beta_1,\beta_2,\Gamma ldots,\beta_d)(x_i , y_j) = (G\alpha x_i,\beta_i y_j) .</tex>  Композиция <tex>C_3 [S_2 ] </tex> имеет степень <tex>6</tex> и порядок <tex>24</tex>. Любую подстановку из <tex>C_3 [S_2 ] </tex>можно записать в таком виде, действующую как она действует на множестве вершин <tex>VX\times Y</tex>. Вводя опять обозначение <tex>1a</tex> для упорядоченной пары <tex>(1,a)</tex> и используя формулу выше можно представить подстановку <tex>((123);(a)(b),(ab),(a)(b))</tex> в виде <tex>(G1a\ 2a\ 3b\ 1b\ 2b\ 3a)</tex>. Эту группу называют '''группой''' или иногда '''вершинной группой графа''' Заметим, что группа <tex>S_2 [C_3 ] </tex> имеет порядок <tex>18</tex> и поэтому не изоморфна группе <tex>GC_3 [S_2 ] </tex>.}}

{{Определение|definition===Степенная группа===Вершинная группа графа G индуцирует другую группу подстановок (обозначается <tex>B^A</tex> \Gamma_1 (G) действует на множестве <tex>Y^X</tex>всех функций, называемую '''реберной группой графа''' отображающих <tex>X</tex> в <tex>GY</tex>; она . Будем всегда предполагать, что степенная группа действует на множестве ребер , состоящем более чем из одной функции. Для каждой пары подстановок <tex>\alpha</tex> из <tex>A</tex> и <tex>E\beta</tex> из <tex>B</tex> существует единственная подстановка из <tex>B^A</tex> (Gзаписывается <tex>\beta^\alpha</tex>), которая действует на любую функцию <tex>f</tex>. }}из <tex>Y^X</tex> в соответствии со следующим соотношением, определяющим образ каждого элемента <tex>x\in X</tex> при отображении <tex>\beta^\alpha f</tex>:

Для иллюстрации различия групп <tex>(\Gamma</tex> и <tex>beta^\Gamma_1</tex> рассмотрим граф <tex>K_4 - х</tex>, показанный на рисунке; его вершины помечены <tex>v_1 , v_2, v_3, v_4 </tex> а ребра <tex>x_1, x_2, x_3, x_4, x_5 </tex>. Вершинная группа <tex>\Gamma alpha f)(K_4 - x) </tex> состоит из четырех подстановок<tex>=\beta f(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\alpha x).</tex>

Понятно, что реберная Степенная группа <tex>S_{2}^{C_3}</tex> имеет порядок <tex>6</tex> и вершинная группы графа степень <tex>K_4 - х8</tex> изоморфны. Но ониПрименяя формулу выше, конечновидим, не могут быть идентичнымичто подстановка этой группы, так как степень группы полученная из подстановок <tex>\Gamma_1 alpha = (K_4 - x123) </tex> равна 5, а степень группы и <tex>\Gamma beta = (K_4 - xab) </tex> равна 4, имеет один цикл длины <tex>2</tex> и один цикл длины <tex>6</tex>.