Группы графов
| Определение: |
| Автоморфизмом (англ. Automorphism) графа называется изоморфизм графа на себя |
Каждый автоморфизм графа есть подстановка множества вершин , сохраняющая смежность. Конечно, подстановка переводит любую вершину графа в вершину той же степени. Очевидно, что последовательное выполнение двух автоморфизмов есть также автоморфизм;
| Определение: |
| Автоморфизмы графа образуют группу подстановок , действующую на множестве вершин . Эту группу называют группой или иногда вершинной группой графа (англ. point-group). |
| Определение: |
| Вершинная группа графа индуцирует другую группу подстановок , называемую реберной группой графа (англ. line-group) — она действует на множестве ребер . |
Для иллюстрации различия групп и рассмотрим граф , показанный на рисунке; его вершины помечены а ребра . Вершинная группа состоит из четырех подстановок
Тождественная подстановка вершинной группы индуцирует тождественную подстановку на множестве ребер, в то время как подстановка индуцирует подстановку на множестве ребер, в которой ребро остается на месте, меняется с , а с . Таким образом, реберная группа состоит из следующих подстановок, индуцируемых указанными выше элементами вершинной группы:
Понятно, что реберная и вершинная группы графа изоморфны. Но они, конечно, не могут быть идентичными, так как степень группы равна , а степень группы равна .
| Теорема: |
Реберная и вершинная группы графа изоморфны тогда и только тогда, когда граф имеет не более одной изолированной вершины, а граф не является его компонентой. |
| Доказательство: |
|
Пусть подстановка группы индуцируется подстановкой группы . Из определения операции умножения в группе вытекает, что для . Поэтому отображение является групповым гомоморфизмом группы на . Следовательно, тогда и только тогда, когда ядро этого отображения тривиально.
Для доказательства необходимости предположим, что . Тогда из неравенства ( — тождественная подстановка) следует, что . Если в графе существуют две различные изолированные вершины и , то можно определить подстановку , положив для . Тогда , но . Если — компонента графа , то, записав ребро графа в виде и определив подстановку точно так же, как выше, получим , но .
Чтобы доказать достаточность, предположим, что граф имеет не больше одной изолированной вершины и не является его компонентой. Если группа тривиальна, то очевидно, что группа оставляет на месте каждое ребро и, следовательно, — тривиальная группа. Поэтому предположим, что существует подстановка , для которой . Тогда степени вершин и равны. Поскольку вершины и не изолированы, их степени не равны нулю. Здесь возникает два случая. Случай 1. Вершины и смежны. Пусть . Так как не является компонентой графа , то степени обеих вершин и больше единицы. Следовательно, существует такое ребро инцидентное вершине , что ребро инцидентно вершине . Отсюда , и тогда . Случай 2. Вершины и не смежны. Пусть — произвольное ребро, инцидентное вершине . Тогда , следовательно, . |
Операции на группах подстановок
Пусть — группа подстановок порядка и степени , действующая на множестве , а — другая группа подстановок порядка и степени , действующая на множестве . Например, пусть — циклическая группа порядка , действующая на множестве . Эта группа состоит из трех подстановок и . Если взять в качестве симметрическую группу порядка , действующую на множестве , то получим две подстановки и . Проиллюстрируем на этих двух группах подстановок действие нескольких бинарных операций.
Сумма подстановок
— это группа подстановок, действующая на объединении непересекающихся множеств и элементы которой записываются в виде и представляют собой упорядоченные пары подстановок из и из . Каждый элемент , принадлежащий множеству преобразуется подстановкой по правилу
Таким образом, группа содержит подстановок, каждую из которых можно записать в виде суммы подстановок и , как, например, . (степень равна .)
Произведение групп
— это группа подстановок, действующая на множестве , элементы которой записываются в виде и представляют собой упорядоченные пары подстановок из и из . Элемент множества преобразуется подстановкой естественным образом:
Подстановкой в группе , которая соответствует подстановке будет , где для краткости символ заменен на . (Порядок и степень равны .)
Композиция групп
группы относительно группы также действует на множестве . Для любой подстановки из и любой последовательности , содержащей (не обязательно различных) подстановок из , существует единственная подстановка из , которая записывается в виде , такая, что для всякой пары из выполняется равенство
Композиция имеет степень и порядок . Любую подстановку из можно записать в таком виде, как она действует на множестве . Вводя опять обозначение для упорядоченной пары и используя формулу выше можно представить подстановку в виде . Заметим, что группа имеет порядок и поэтому не изоморфна группе .
Степенная группа
(обозначается ) действует на множестве всех функций, отображающих в . Будем всегда предполагать, что степенная группа действует на множестве, состоящем более чем из одной функции. Для каждой пары подстановок из и из существует единственная подстановка из (записывается ), которая действует на любую функцию из в соответствии со следующим соотношением, определяющим образ каждого элемента при отображении :
Степенная группа имеет порядок и степень . Применяя формулу выше, видим, что подстановка этой группы, полученная из подстановок и , имеет один цикл длины и один цикл длины .
См. также
Источники информации
- Харари Ф. Теория графов. М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)
