Введение 2
Постановка задачи 3
Обзор литературы 4
Глава 1. Общие сведения о подстановках 5
1.1. Понятие подстановки 5
1.2. Произведение подстановок 6
1.3. Симметрическая группа степени 7
1.4. Циклы и циклическая группа 9
Глава 2. Автоморфизмы подстановок 14
2.1. Классы сопряженных элементов 14
2.2. Автоморфизмы группы 15
2.3. Разложение симметрической группы на классы сопряженности 20
2.4. Нахождение группы автоморфизмов симметрической группы 22
Глава 3. Применение автоморфизмов подстановок к теории графов 26
3.1. Основные понятия о графах 26
3.2. Автоморфизмы графов 27
3.3. Связь симметрической группы и автоморфизмов графов 28
Заключение 33
Список литературы
Понятие подстановки, которое является одним из центральных в данной работе, возникло еще в XVIII веке. Тогда выдающиеся математики Вандермонд и Лагранж, занимаясь изучением полиномиальных уравнений, рассмотрели композицию подстановок и установили, что они обладают свойствами групповых объектов[1, с. 349]. Поэтому можно считать, что именно с подстановок зародилась теория конечных групп.
При исследовании теории групп подстановок естественным образом может возникнуть вопрос о существовании таких отображений группы подстановок, или симметрической группы, на себя, при которых сохраняются соотношения между элементами группы. Как будет показано в настоящей работе, все такие отображения образуют группу относительно операции умножения и несут название автоморфизмов группы подстановок. Одним из примечательных свойств автоморфизмов является то, что они определяют внутреннюю структуру объектов, разбивая их на множества элементов со схожими особенностями и характеристиками.
Выделив основные принципы теории подстановок, применим их к теории графов. Если говорить точнее, то мы можем установить связь между свойствами группы автоморфизмов подстановок на множестве вершин некоторого графа и автоморфизмами этого графа.
В ходе работы подробно рассмотрены симметрические группы и их свойства, установлена взаимосвязь между автоморфизмами подстановок и автоморфизмами графов через матрицы подстановок и смежности. Были получены следующие результаты:
1) Симметрическая группа nможет быть разложена на классы сопряженных между собой элементов, при этом подстановки из одного класса имеют разложение на циклы одинаковых порядков.
2) Если степень симметрической группы Sn n-3 и отлична от шести, то группа автоморфизмов ^U(n) совпадает с самой группой Sfi.
3) Установлено, что используя матрицу смежности графа A, подстановки на множестве вершин графа и представляя эти подстановки в виде матрицы Р, можно вывести уравнение для нахождения автоморфизмов графа
A = PTAP
