36
правок
Изменения
Нет описания правки
Вершинная группа графа G индуцирует другую группу подстановок <tex> \Gamma_1 (G) </tex>, называемую '''реберной группой графа''' <tex>G</tex>; она действует на множестве ребер <tex>E(G)</tex>.
}}
[[Файл:fordm.png|thumb|200px|thumb|leftright]] Для иллюстрации различия групп <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_3)(v_2v_4)</tex> индуцирует подстановку на множестве ребер, в которой ребро <tex>x_5</tex> остается на месте, <tex>х_1</tex> меняется с <tex>х_4</tex>, а <tex>х_2</tex> с <tex>х_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.
==Источники информации==
* Харари Ф. Теория графов. М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
