36
правок
Изменения
Нет описания правки
Понятно, что реберная и вершинная группы графа <tex>K_4 - х</tex> изоморфны. Но они, конечно, не могут быть идентичными, так как степень группы <tex>\Gamma_1 (K_4 - x) </tex> равна 5, а степень группы <tex>\Gamma (K_4 - x) </tex> равна 4.
{{Теорема
|statement=
Реберная и вершинная группы графа <tex>G</tex> изоморфны тогда и только тогда, когда граф <tex>G</tex> имеет не более одной изолированной вершины, а граф <tex>K_2</tex> не является его компонентой.
|proof=
Пусть подстановка <tex>\alpha'</tex> группы <tex>\Gamma_1(G)</tex> индуцируется подстановкой <tex>\alpha</tex> группы <tex>\Gamma(g). Из определения операции умножения в группе <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>\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>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> не изолированы, их степени не равны нулю. Здесь возникает два случая.
''Случай 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>.
}}
==См. также==
