Автоморфизм

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 19:13, 20 мая 2016.
TemplateDifinitionIcon.svg Определение «Определение 1»

Пусть - произвольное множество.Тогда:

а) -арным отношением на называется любое подмножество в множестве
б) -арной операцией на со значением в называется:
(отображает декартову степень во множество ).
в) Пусть -арная функция , определенная на множестве принимает 2 значения {И,Л} (И - Истина, Л - Ложь). Такая функция называется -арным предикатом, отображающим декартову степень во множество {И,Л}:
[1].
TemplateDifinitionIcon.svg Определение «Определение 2»

Пусть множество задано следующим образом[2]:

при т.е. элементы упорядочены по возрастанию.

Тогда алгебраической системой типа называется объект, состоящий из 3-х множеств:

обладающих следующими свойствами:
1.
2. - множество операций, определенных на множестве , причем "арность" -ой операции равна
3. - множество предикатов на , причем "арность" равна

Множество называется носителем (основным множеством).

Если то алгебраическая система - алгебра (универсальная алгебра).

Если , то алгебраическая система - модель.

TemplateExampleIcon.svg Пример Пример 1 (алгебраические системы)
1. Пусть - алгебра, - коммутативная группа на ; множество с заданной на нем бинарной операцией т.е. арность операции равна
2. - алгебра, кольцо.
3. - алгебраическая система,
4. - модель,


Группа автоморфизмов алгебраической системы

TemplateDifinitionIcon.svg Определение «Определение 3»

Группа действующая на множестве сохраняет алгебраическую систему если выполняются соотношения:

а) (сохраняется функция; результат левой части выражения равен результату правой части выражения);
б) (полученный предикат не выходит за пределы данного множества, т.е. предикат сохраняется).
TemplateDifinitionIcon.svg Определение « Определение 4»
Группа всех подстановок на сохраняющая алгебраическую систему называется группой автоморфизмов в
(т.е. переводит алгебраическую систему саму в себя).


TemplateExampleIcon.svg Пример Пример 2 (автоморфизмы алгебраической системы)
1. - группа. Рассмотрим множество подстановок сохраняющих групповую (в данном случае, бинарную) операцию:

Иными словами, получается множество изоморфизмов группы саму в себя (автоморфизмов).

2. - векторное пространство над полем.

Автоморфизмом над являются все подстановки , действующие на которые его сохраняют.

Определим на операции: + (сложение) и * (умножение на скаляр):

(множество всех линейных обратимых матриц, т.е. линейных преобразований) - полная линейная группа.

3. Кольцо с .

- множество всех подстановок, сохраняющих бинарные операции (т.е. сохраняющих операции + и *) и

Кольцо

а)

б)

в)

4. Группа автоморфизмов частично упорядоченного множества (ЧУМ).

Пусть на множестве задано отношение частичного порядка Тогда:

множество подстановок, сохраняющих частичный порядок.


TemplateExampleIcon.svg Пример Упражнение 1

1. Пусть - конечная циклическая группа порядка Доказать, что ее группа автоморфизмов состоит из всех подстановок вида:

(возвели в k-ую степень) для

2. Найти явно описать кольца вычетов по т.е.

Рассматриваем

3. Доказать: т.е. их группы автоморфизмов тривиальны.


Группа автоморфизмов графов

TemplateDifinitionIcon.svg Определение «Определение 5»

Граф, или неориентированный граф  — это упорядоченная пара , где  — это непустое множество вершин или узлов, а  — множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

TemplateDifinitionIcon.svg Определение «Определение 6»

Автоморфизмом графа (орграфа) с множеством вершин и множеством ребер называется биекция, сохраняющая этот граф:

(т.е. подстановка вершин из сохраняющая смежность: переводит вершину графа в вершину той же степени).

Для выполняется следующее:

Т.е. сохраняется множество ребер и множество вершин.

Множество всех автоморфизмов графа относительно операции композиции образуют группу, называемую группой автоморфизмов графа (группа подстановок).

В зависимости от свойств группы подстановок (группы автоморфизмов графа) возникают разные характеристики графов.

TemplateDifinitionIcon.svg Определение «Определение 7»

Если группа автоморфизмов , где граф, действует на множестве вершин, и вершинная группа автоморфизмов транзитивна, то граф называется вершинно-транзитивным.

Если реберная группа автоморфизмов транзитивна, то граф называется реберно-транзитивным.

TemplateExampleIcon.svg Пример Пример 3

Дано:

Dgdm6 3 2.png

Найти: группу автоморфизмов.

Определить: является ли граф вершинно-транзитивным или реберно-транзитивным.

Т.к. можем перевести вершины

Группа действует транзитивно граф - вершинно-транзитивный.

Но: группа действует на интранзитивно граф не является реберно-транзитивным.


TemplateExampleIcon.svg Пример Упражнение 2
К задаче 1

1. Дано:

а) Показать, что - вершинно-транзитивный.

б) Выяснить, является ли группа примитивной доказывать по критерию примитивности: 1) найти стабилизатор какой-либо точки ; 2) доказать по лемме Бернсайда, что порядок стабилизатора равен [3]







2.
К задаче 2

Дано: граф Петерсона.

Определить:

а) Показать, что - вершинно-транзитивный.

б)

в) примитивна (найти мощность стабилизатора вершины).

г) Показать, что имеет 3 орбиты длины 1, 3 и 6 произвольная вершина графа

д) Выяснить, является ли группа автоморфизмов примитивной.







3.
К задаче 3

Дано:

Определить:

а) Является ли вершинно-транитивным.

б) Является ли реберно-транзитивным.

в) Является ли примитивной.


4. Дано: орграф

- транзитивна.

бесконечная числовая прямая:

Определить:

Является ли группа примитивной.


TemplateTheoremIcon.svg Теорема Теорема 1

Если - реберно-транзитивный, то - вершинно-транзитивный или - двудольный граф, причем имеет 2 орбиты, соответствующие долям.

Доказательство

Пусть

Граф - реберно-транзитивный - транзитивный по крайней мере автоморфизмов

Двудольный граф: каждая вершина из первой доли соединяется с вершиной из другой доли, причем вершины в одной доле между собой не соединяются

Обозначим:

По условию, граф реберно транзитивен, без изолированных вершин имеет место равенство:

т.е. некоторое объединение.

Возможны 2 случая:

1) (имеем разбиение). Тогда - двудольный[4].

2) Возьмем произвольную пару вершин графа

Надо показать, что существует автоморфизм следовательно - вершинно-транзитивный.

Рассмотрим 2 ситуации:

а) т.е. целиком вкладывается в Рассмотрим случай с все аналогично). Рассмотрим 2 автоморфизма, действующих следующим образом:

Такие автоморфизмы заведомо существуют:

построили требуемый автоморфизм - вершинно-транзитивный.

б)

т.к. - лежат на одной орбите также принадлежат одной орбите автоморфизм:


  • Пусть имеется группа . Существует ли граф, для которого она является

Да, существует: это утверждается в теореме Фрухта.

TemplateTheoremIcon.svg Теорема Теорема Фрухта

Для конечной произвольной группы всегда существует граф, для которого она является т.е. изоморфна группе автоморфизмов некоторого графа.

Доказательство
Граф, который использовал Фрухт для доказательства

Первый шаг состоит в построении такого семейства связных графов , что группа каждого является единичной. Это можно сделать многими способами. Фрухт использовал графы, изображённые на рисунке.

Затем для строится цветной граф Кэли . Искомый граф получается из такой заменой каждого ориентированного ребра из класса цвета на граф , что отождествляется с вершиной 1, а - с вершиной 2.

Очевидно, что граф является неориентированным и связным. Остается показать, что его группа изоморфна. Рассмотрим сначала автоморфизм , оставляющий неподвижной некоторую вершину . В ребра, отходящие от , имеют вид (1,3) или (2,4) в зависимости от направления соответствующего ребра в . Но если вершина инварианта при , то соседние вершины 3 и 4 также должны оставаться неизменными, так как все соответствующие им цепи имеют различные длины. По той же причине каждый из графов в остается неподвижным. Следовательно, такой будет и вершина 2, соответствующая вершине .

При автоморфизме графа любая вершина может переходить только в некоторую вершину , т.к. все остальные вершины графа имеют другие локальные степени. Кроме того, из предыдущего следует, что для каждой пары может быть не более одного автоморфизма, переводящего одну вершину в другую. Но такой автоморфизм в индуцируется автоморфизмами графа , определяемыми умножениями слева на элементы из . Ч.т.д.


Примечания

  1. {T, F} {И, Л}
  2. Считаем, что все множества конечны и счетны.
  3. Величина орбиты равна числу вершин, если примитивна.
  4. Доказать самостоятельно.