Группы графов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 17 промежуточных версий 2 участников)
Строка 1: Строка 1:
 +
==Вершинная и рёберная группы графов==
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Непустое множество А вместе с заданной на нем бинарной операцией, результат применения которой к элементам <tex>\alpha_1</tex> и <tex>\alpha_2</tex> из <tex>A</tex> обозначается через <tex>\alpha_1\alpha_2</tex> , образует '''группу''', если выполняются следующие четыре аксиомы:
+
'''Автоморфизмом''' (англ. ''Automorphism'') графа <tex>G</tex> называется изоморфизм графа <tex>G</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)\alpha_3</tex>
 
# Аксиома тождественности. В множестве <tex>A</tex> существует такой элемент <tex>i</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>\alpha</tex> графа <tex>G</tex> есть [[:группа#Группа_подстановок|подстановка]] множества вершин <tex>V</tex>, сохраняющая смежность. Конечно, подстановка <tex>\alpha</tex> переводит любую вершину графа в вершину той же степени. Очевидно, что последовательное выполнение двух автоморфизмов есть также автоморфизм;
|definition=
 
'''Подстановка''' {{---}} взаимно однозначное отображение конечного множества на себя.  
 
}}
 
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Если некоторая совокупность подстановок замкнута относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве, то аксиомы 2, 3 и 4 автоматически выполняются и эта совокупность называется '''группой подстановок'''.  
+
Автоморфизмы графа <tex> G </tex> образуют [[:группа#Группа_подстановок|группу подстановок]] <tex> \Gamma (G) </tex>, действующую на множестве вершин <tex>V(G)</tex>. Эту [[:группа|группу]] называют '''группой''' или иногда '''вершинной группой графа''' <tex>G</tex> (англ. ''point-group'').
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Автоморфизмом''' графа <tex>G</tex> называется изоморфизм графа <tex>G</tex> на себя
+
Вершинная группа графа <tex>G</tex> индуцирует другую группу подстановок <tex> \Gamma_1 (G) </tex>, называемую '''реберной группой графа''' <tex>G</tex> (англ. ''line-group'') {{---}} она действует на множестве ребер <tex>E(G)</tex>.
 
}}
 
}}
  
{{Определение
+
[[Файл:fordm.png|right]]
|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>.
 
}}
 
  
{{Определение
+
Для иллюстрации различия групп <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> состоит из четырех подстановок
|definition=
 
Вершинная группа графа <tex>G</tex> индуцирует другую группу подстановок <tex> \Gamma_1 (G) </tex>, называемую '''реберной группой графа''' <tex>G</tex>; она действует на множестве ребер <tex>E(G)</tex>.
 
}}
 
 
 
Для иллюстрации различия групп <tex>\Gamma</tex> и <tex>\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 (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_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>
  
Строка 39: Строка 25:
 
<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>(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 - х</tex> изоморфны. Но они, конечно, не могут быть идентичными, так как степень группы <tex>\Gamma_1 (K_4 - x) </tex> равна 5, а степень группы <tex>\Gamma (K_4 - x) </tex> равна 4.  
+
Понятно, что реберная и вершинная группы графа  <tex>K_4 - x</tex> изоморфны. Но они, конечно, не могут быть идентичными, так как степень группы <tex>\Gamma_1 (K_4 - x) </tex> равна <tex>5</tex>, а степень группы <tex>\Gamma (K_4 - x) </tex> равна <tex>4</tex>.  
 +
 
  
 
{{Теорема
 
{{Теорема
Строка 45: Строка 32:
 
Реберная и вершинная группы графа <tex>G</tex> изоморфны тогда и только тогда, когда граф <tex>G</tex> имеет не более одной изолированной вершины, а граф <tex>K_2</tex> не является его компонентой.
 
Реберная и вершинная группы графа <tex>G</tex> изоморфны тогда и только тогда, когда граф <tex>G</tex> имеет не более одной изолированной вершины, а граф <tex>K_2</tex> не является его компонентой.
 
|proof=
 
|proof=
  Пусть подстановка <tex>\alpha'</tex> группы <tex>\Gamma_1(G)</tex> индуцируется подстановкой <tex>\alpha</tex> группы <tex>\Gamma(g). Из определения операции умножения в группе <tex>\Gamma_1(G)</tex> вытекает, что  
+
  Пусть подстановка <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>\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>\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>\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> \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>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>.  
+
:''Случай 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>.
+
:''Случай 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>. Проиллюстрируем на этих двух группах подстановок действие нескольких бинарных операций.
 +
 +
===Сумма подстановок===
 +
<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>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>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>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>C_3 [S_2 ] </tex> имеет степень <tex>6</tex> и порядок <tex>24</tex>. Любую подстановку из <tex>C_3 [S_2 ] </tex> можно записать в таком виде, как она действует на множестве <tex>X\times Y</tex>. Вводя опять обозначение <tex>1a</tex> для упорядоченной пары <tex>(1,a)</tex> и используя формулу выше можно представить подстановку <tex>((123);(a)(b),(ab),(a)(b))</tex> в виде <tex>(1a\ 2a\ 3b\ 1b\ 2b\ 3a)</tex>. Заметим, что группа <tex>S_2 [C_3 ] </tex> имеет порядок <tex>18</tex> и поэтому не изоморфна группе <tex>C_3 [S_2 ] </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>
 +
 +
 +
Степенная группа <tex>S_{2}^{C_3}</tex> имеет порядок <tex>6</tex> и степень <tex>8</tex>. Применяя формулу выше, видим, что подстановка этой группы, полученная из подстановок <tex>\alpha = (123)</tex> и <tex>\beta = (ab)</tex>, имеет один цикл длины <tex>2</tex> и один цикл длины <tex>6</tex>.
  
 
==См. также==
 
==См. также==
Строка 66: Строка 102:
 
* Харари Ф. Теория графов. М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
 
* Харари Ф. Теория графов. М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
  
[[Категория: Алгоритмы и структуры данных]]
+
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Основные определения теории графов]]
 
[[Категория: Основные определения теории графов]]
 
[[Категория: Теория групп]]
 
[[Категория: Теория групп]]

Текущая версия на 19:17, 4 сентября 2022

Вершинная и рёберная группы графов

Определение:
Автоморфизмом (англ. Automorphism) графа [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] (англ. point-group).


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


Fordm.png

Для иллюстрации различия групп [math]\Gamma[/math] и [math]\Gamma_1[/math] рассмотрим граф [math]K_4 - x[/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 - x[/math] изоморфны. Но они, конечно, не могут быть идентичными, так как степень группы [math]\Gamma_1 (K_4 - x) [/math] равна [math]5[/math], а степень группы [math]\Gamma (K_4 - x) [/math] равна [math]4[/math].


Теорема:
Реберная и вершинная группы графа [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] \Rightarrow [/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] \Leftarrow [/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] не изолированы, их степени не равны нулю. Здесь возникает два случая. <tex<\par</tex>
Случай 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]

Операции на группах подстановок

Пусть [math]A[/math] — группа подстановок порядка [math]m = |A|[/math] и степени [math]d[/math], действующая на множестве [math]X = \{x_1,x_2,\ldots,x_d\}[/math], а [math]B[/math] — другая группа подстановок порядка [math]n = |B|[/math] и степени [math]e[/math], действующая на множестве [math]Y = \{y_1,y_2,\ldots,y_e\}[/math]. Например, пусть [math]A = C_3[/math] — циклическая группа порядка [math]3[/math], действующая на множестве [math]X={1, 2, 3}[/math]. Эта группа состоит из трех подстановок [math](1)(2)(3), (123)[/math] и [math](132)[/math]. Если взять в качестве [math]B[/math] симметрическую группу [math]S_2[/math] порядка [math]2[/math], действующую на множестве [math]Y = \{a,b\}[/math], то получим две подстановки [math](a)(b)[/math] и [math](ab)[/math]. Проиллюстрируем на этих двух группах подстановок действие нескольких бинарных операций.

Сумма подстановок

[math]A + B[/math] — это группа подстановок, действующая на объединении [math]X \cup Y[/math] непересекающихся множеств [math]X[/math] и [math]Y[/math] элементы которой записываются в виде [math]\alpha + \beta[/math] и представляют собой упорядоченные пары подстановок [math]\alpha[/math] из [math]A[/math] и [math]\beta[/math] из [math]B[/math]. Каждый элемент [math]z[/math], принадлежащий множеству [math]X \cup Y[/math] преобразуется подстановкой [math]\alpha + \beta[/math] по правилу

[math] (\alpha + \beta)(z) = \begin{cases} \alpha z, z \in X, \\ \beta z, z \in Y. \end{cases} [/math]


Таким образом, группа [math]C_3 + S_2[/math] содержит [math]6[/math] подстановок, каждую из которых можно записать в виде суммы подстановок [math]\alpha \in C_3[/math] и [math]\beta\in S_2[/math], как, например, [math](123)(ab)=(123)+(ab)[/math]. (степень равна [math]5[/math].)

Произведение групп

[math]A \times B [/math] — это группа подстановок, действующая на множестве [math]X\times Y[/math], элементы которой записываются в виде [math]\alpha\times\beta[/math] и представляют собой упорядоченные пары подстановок [math]\alpha[/math] из [math]A[/math] и [math]\beta[/math] из [math]B[/math]. Элемент [math](x,y)[/math] множества [math]X\times Y[/math] преобразуется подстановкой [math]\alpha\times\beta[/math] естественным образом:


[math](\alpha\times\beta)(x,y)=(\alpha x,\beta y)[/math]


Подстановкой в группе [math]C_3\times S_2[/math], которая соответствует подстановке [math](123)+(ab)[/math] будет [math](1a\ 2b\ 3a\ 1b\ 2a\ 3b)[/math], где для краткости символ [math](1,a)[/math] заменен на [math]1a[/math]. (Порядок и степень равны [math]6[/math].)

Композиция групп

[math]A[B][/math] группы [math]A[/math] относительно группы [math]B[/math] также действует на множестве [math]X\times Y[/math]. Для любой подстановки [math]\alpha[/math] из [math]A[/math] и любой последовательности [math](\beta_1,\beta_2,\ldots,\beta_d)[/math], содержащей [math]d[/math] (не обязательно различных) подстановок из [math]B[/math], существует единственная подстановка из [math]A[B][/math], которая записывается в виде [math](\alpha;\beta_1,\beta_2,\ldots,\beta_d)[/math], такая, что для всякой пары [math](x_i , y_i)[/math] из [math]X\times Y[/math] выполняется равенство


[math](\alpha;\beta_1,\beta_2,\ldots,\beta_d)(x_i , y_j) = (\alpha x_i,\beta_i y_j).[/math]


Композиция [math]C_3 [S_2 ] [/math] имеет степень [math]6[/math] и порядок [math]24[/math]. Любую подстановку из [math]C_3 [S_2 ] [/math] можно записать в таком виде, как она действует на множестве [math]X\times Y[/math]. Вводя опять обозначение [math]1a[/math] для упорядоченной пары [math](1,a)[/math] и используя формулу выше можно представить подстановку [math]((123);(a)(b),(ab),(a)(b))[/math] в виде [math](1a\ 2a\ 3b\ 1b\ 2b\ 3a)[/math]. Заметим, что группа [math]S_2 [C_3 ] [/math] имеет порядок [math]18[/math] и поэтому не изоморфна группе [math]C_3 [S_2 ] [/math].

Степенная группа

(обозначается [math]B^A[/math]) действует на множестве [math]Y^X[/math] всех функций, отображающих [math]X[/math] в [math]Y[/math]. Будем всегда предполагать, что степенная группа действует на множестве, состоящем более чем из одной функции. Для каждой пары подстановок [math]\alpha[/math] из [math]A[/math] и [math]\beta[/math] из [math]B[/math] существует единственная подстановка из [math]B^A[/math] (записывается [math]\beta^\alpha[/math]), которая действует на любую функцию [math]f[/math] из [math]Y^X[/math] в соответствии со следующим соотношением, определяющим образ каждого элемента [math]x\in X[/math] при отображении [math]\beta^\alpha f[/math]:


[math](\beta^\alpha f)(x)=\beta f(\alpha x).[/math]


Степенная группа [math]S_{2}^{C_3}[/math] имеет порядок [math]6[/math] и степень [math]8[/math]. Применяя формулу выше, видим, что подстановка этой группы, полученная из подстановок [math]\alpha = (123)[/math] и [math]\beta = (ab)[/math], имеет один цикл длины [math]2[/math] и один цикл длины [math]6[/math].

См. также

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

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