36
правок
Изменения
Нет описания правки
{{Определение
|definition=
Вершинная группа графа <tex>G </tex> индуцирует другую группу подстановок <tex> \Gamma_1 (G) </tex>, называемую '''реберной группой графа''' <tex>G</tex>; она действует на множестве ребер <tex>E(G)</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>х_1x_1</tex> меняется с <tex>х_4x_4</tex>, а <tex>х_2x_2</tex> с <tex>х_3x_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 - х</tex> изоморфны. Но они, конечно, не могут быть идентичными, так как степень группы <tex>\Gamma_1 (K_4 - x) </tex> равна 5, а степень группы <tex>\Gamma (K_4 - x) </tex> равна 4.
==См. также==
*[[Группа]]
*[[wikipedia:ru:Автоморфизм_графа | Википедия {{---}} Автоморфизм_графа]]
==Источники информации==
* Харари Ф. Теория графов. М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]
[[Категория: Теория групп]]
