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