Группы автоморфизмов подстановок и графы

Рябова Марина Анатольевна

Группы автоморфизмов подстановок и графы

Выпускная квалификационная работа бакалавра на тему: «Автоморфизмы подстановок и графы» содержит 35 страниц текста, 15 использованных источников литературы, 3 таблицы, 1 рисунок. Ключевые слова: подстановки, симметрическая группа, цикл, классы сопряженных элементов, автоморфизмы, совершенные группы, графы, матрица подстановки. Объектом исследования являются группы подстановок. Предмет исследования – автоморфизмы групп подстановок и их связь с графами. Целью работы является нахождение группы автоморфизмов подстановок и ее применение в теории графов. В результате теоретических исследований, которые сопровождались анализом доступных литературных источников, были получены необходимые математические выкладки для достижения поставленной цели работы. Как итог работы, были установлены правила нахождения автоморфизмов группы подстановок и их взаимосвязь с автоморфизмами графов через матрицы подстановок и смежности.

Общественные науки в целом

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36405f1be77c40d58a9c

UUID: c1a60fed-374a-4f40-8276-d5faa0f58c4d

Язык: Русский

Опубликовано: больше 7 лет назад

Просмотры: 474

Рябова Марина Анатольевна

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 4952449 bytes

Поделиться работой

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КАФЕДРА ВЫСШЕЙ МАТЕМАТИКИ Рябова Марина Анатольевна Выпускная квалификационная работа бакалавра Автоморфизмы подстановок и графы Направление 010400 Прикладная математика, фундаментальная информатика и основы программирования Научный руководитель, кандидат физ.-мат. наук, доцент Калинина Е. А. Санкт-Петербург 2016 

Содержание Введение .....................................................................................................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 Список литературы ........................................................................................34 Введение Понятие подстановки, которое является одним из центральных в данной работе, возникло еще в M XVIII веке. Тогда выдающиеся математики Вандермонд и Лагранж, занимаясь изучением полиномиальных уравнений, рассмотрели композицию подстановок и установили, что они обладают 2

свойствами групповых объектов[1, с. 349]. Поэтому можно считать, что именно с подстановок зародилась теория конечных групп. При исследовании теории групп подстановок естественным образом может возникнуть вопрос о существовании таких отображений группы подстановок, или симметрической группы, на себя, при которых сохраняются соотношения между элементами группы. Как будет показано в настоящей работе, все такие отображения образуют группу относительно операции умножения и несут название автоморфизмов группы подстановок. Одним из примечательных свойств автоморфизмов является то, что они определяют внутреннюю структуру объектов, разбивая их на множества элементов со схожими особенностями и характеристиками. Выделив основные принципы теории подстановок, применим их к теории графов. Если говорить точнее, то мы можем установить связь между свойствами группы автоморфизмов подстановок на множестве вершин некоторого графа и автоморфизмами этого графа. Постановка задачи Наша задача заключается в исследовании различных групп подстановок и нахождении их групп автоморфизмов. Целью работы является распространение полученных результатов для теории подстановок на автоморфизмы графов. 3

В первой главе мы введем основные понятия и утверждения, связанные с подстановками. Особое внимание уделим разложению подстановок в произведение циклов. Во второй главе определим разделение группы на классы сопряженных элементов и перейдем к поиску автоморфизмов симметрической группы. Третья глава является результатом исследований свойств автоморфизмов подстановок и их применений к теории автоморфизмов графов. Обзор литературы Всю литературу, используемую при написании данной работы, можно разделить на четыре части. В первой из них содержатся литературные источники, раскрывающие такие понятия как подстановка, умножение подстановок, симметрическая группа, циклы. Это книги Постникова М. М., 4

Головиной Л. И. и работа под редакцией Александрова А. Д., Колмогорова А. Н., Лаврентьева М. А. К ним можно добавить книги Гроссмана И. и Магнуса В. «Группы и их графы», Винберга Э. Б. «Курс алгебры», в которых рассматриваются понятия группы и циклической группы. Вторая часть включает литературу по автоморфизмам групп. Авторами литературных источников являются Ван дер Варден , Курош А. Г., Каргаполов М. И. и Мерзляков Ю. И. При подсчете количества всех автоморфизмов симметрической группы использовалась литература по теории вероятностей: «Введение в прикладную комбинаторику» Кофмана А., «Теория вероятностей и математическая статистика» Буре В. М. и Парилиной Е. М. Последняя часть литературы связана с основными понятиями теории графов. К ней относятся книги «Теория графов» Харари Ф., «Перечисление графов» Харари Ф. и Палмера Э., «Лекции по теории графов» Емеличева В. А., Мельникова О. И., Сарванова В. И. и Тышкевича Р. И. Глава 1. Общие сведения о подстановках 1.1. Понятие подстановки Подстановкой называется взаимно однозначное отображение конечного множества на себя [2, с. 87]. Далее под конечным множеством мы будем 5

подразумевать множество с натуральными числами E M = {1, 2, ..., n} и записывать подстановки в следующем виде: ⎛1 s=⎜ ⎝ a1 M 2 a2 ... n ⎞ ... an ⎟⎠ , где вторая строка является перестановкой множества E M (1) и состоит из различных чисел. При этом из (1) следует, что 1 → a1 , 2 → a2 и так далее1. Переставляя некоторые столбцы в подстановке, мы не меняем ее смысла. Под степенью подстановки будем понимать мощность множества, на котором она задана. В нашем случае степень подстановки будет равняться M n . Если наше множествоимеет nM элементов, то количество различных подстановок на данном множестве, очевидно, равняется M n ! Действительно, M1 может перейти в M n различных чисел, тогда M 2 – в M n − 1 число, 3 – в M n − 2 числа и так далее. Имеем M n ! различных перестановок второй строки. 1.2. Произведение подстановок Произведением двух подстановок назовем последовательное выполнение двух подстановок одинаковой степени M n , результатом которого является некая подстановка тоже M n − й степени [3, с. 281]. Стоит отметить, что умножение подстановок не всегда является коммутативным2. Пример. Перемножим подстановки ⎛1 2 3 4 5 ⎞ ⎛1 2 3 4 5 ⎞ s1 = ⎜ s = 2 ⎟ ⎜1 3 4 2 5 ⎟ 5 3 1 4 2 ⎝ ⎠ ⎝ ⎠. M иM 1 Здесь и далее значит, что число переходит в число . 2 Для двух подстановок и не всегда выполняется . 6

Получаем ⎛1 2 3 4 5 ⎞ ⎛1 2 3 4 5 ⎞ s1s2 = ⎜ s s = ⎟ 2 1 ⎜5 1 4 3 2⎟ ⎝5 4 1 2 3⎠, M ⎝ ⎠. M Из (2) можно заметить, что подстановки sM 1 и s2 (2) в данном случае не коммутируют. Произведение подстановок ассоциативно. Действительно, пусть нам даны три подстановки M s1 , s2 , s3 , каждая из них имеет степень M n , и пусть для чисел a1 , a2 , a3 , a4 ∈ {1, 2, ..., n} 3 определено следующее: a1 → a2 при s1 , M a2 → a3 при M s2 , a M 3 → a4 при Ms3 . Тогда нетрудно убедиться, что как при M s1 (s2 s3 ), так и при M (s1s2 ) s3 M a1 → a4 . Следовательно, M s1 (s2 s3 ) = (s1s2 ) s3 . 1.3. Симметрическая группа степени На протяжении всей работы мы будем не раз прибегать к понятию группы. Для того чтобы его ввести, нам необходимо знать, что собой представляет бинарная операция на множестве. Бинарная операция 4 на множестве – это соответствие, при котором каждой упорядоченной паре элементов данного множества отвечает однозначно определенный элемент этого же множества [4, с. 11]. Тогда множество M M будет являться группой, если на нем определена бинарная операция и его элементы удовлетворяют следующим трем аксиомам: 1) Ассоциативности. Пусть p, q, r ∈ M ⇒ ( p ⊗ q ) ⊗ r = p ⊗ (q ⊗ r )5. 3 Здесь и далее – символ принадлежности. 4 Обозначим ее как . 5 Здесь и далее – следовательно, – любой, – существует. 7

2) Существование единичного элемента. Существует единственный элемент M i ∈ M такой, что M ∀m ∈ M , i ⊗ m = m ⊗ i . −1 3) Существование обратного элемента. Для M∀m ∈ M ∃ m ∈ M такой, −1 −1 что M m ⊗ m = m ⊗ m = i . Если бинарная операция задается умножением6, то такую группу назовем мультипликативной. Пусть нам заданы подстановки на множестве M E . Обозначим множество всех таких подстановок через M S n и назовем симметрической группой степени M n [3, с. 280]. Покажем, что M S n – мультипликативная группа. Действительно, имеем: 1) Как было показано в параграфе 1.2, мы можем определить операцию умножения на множестве S M n , которая является ассоциативной и ставит в соответствие двум подстановкам M s1, s2 ∈ Sn их произведение M s1s2 ∈ Sn ; 2) Среди всех подстановок множества SM n подстановку ⎛1 2 ... n ⎞ e=⎜ ⎟ ⎝1 2 ... n ⎠ и произвольную подстановку ⎛1 2 ... n ⎞ s=⎜ a1 a2 ... an ⎟⎠ ⎝ M , тогда очевидно, что M es = se = s ; 6 Будем обозначать как или опускать данный символ. 8 выделим единичную

−1 назовем подстановку sM , которая 3) Обратной к подстановке sM удовлетворяет равенству ⎛a s −1 = ⎜ 1 ⎝1 и очевидно, что M ss −1 a2 2 ... an ⎞ ... n ⎟⎠ , = s −1s = e . 1.4. Циклы и циклическая группа Подстановку вида M {a1 → a2 , a2 → a3 , ..., am−1 → am , am → a1} будем называть циклом длины , при этом все элементы M ai , i = 1,m, различны [5, с. 263]. Очевидно, что существует M m различных записей одного и того же цикла длины M m . Например, ⎛ a1 ⎜a ⎝ 2 M a2 a3 ... am−1 ... am и т. д. am ⎞ = (a1 , a2 ,..., am−1 , am ) = (a2 , a3 ,..., am , a1 ) = a1 ⎟⎠ = (a3 , a4 ,..., am , a1 , a2 ) . Циклы, не содержащие общих элементов, являются независимыми. Не имеет разницы, в каком порядке перемножаются независимые циклы. Действительно, пусть подстановки sM 1 = (a1 , a2 ,..., ak ) и sM 2 = (b1 , b2 ,..., bl ) независимые между собой циклы. Тогда M ⎛ a a2 s1s2 = (a1 , a2 ,..., ak )(b1 , b2 ,..., bl ) = ⎜ 1 ⎝ a2 a3 ⎛ b b2 s2 s1 = (b1 , b2 ,..., bl )(a1 , a2 ,..., ak ) = ⎜ 1 ⎝ b2 b3 ... ak ... a1 ... bl a1 ... b1 a2 s = s. Цикл длины один переводит число само в себя. 9 b1 b2 b2 ... bl ⎞ = s, b3 ... b1 ⎟⎠ a2 ... ak ⎞ = s, a3 ... a1 ⎟⎠ –

Пример. В некоторой подстановке ⎛1 2 3 4 ⎞ s=⎜ ⎟ ⎝1 3 2 4 ⎠ M и 4 есть два единичных цикла M (1) ( ). Назовем транспозицией цикл длины два. Цикл, длина которого Mm , мы можем разложить в произведение M m − 1 транспозиции: ⎛ a1 ⎝ a2 (a1 , a2 , ..., am ) = ⎜ a2 ⎞ ⎛ a1 a1 ⎟⎠ ⎜⎝ a3 a3 ⎞ ⎛ a1 a1 ⎟⎠ ⎜⎝ a4 a4 ⎞ ⎛ a1 ... a1 ⎟⎠ ⎜⎝ am am ⎞ = a1 ⎟⎠ ⎛ a a2 a3 ⎞ ⎛ a1 a4 ⎞ ⎛ a1 am ⎞ =⎜ 1 ⎟⎜ ⎟= ⎟ ... ⎜ ⎝ a2 a3 a1 ⎠ ⎝ a4 a1 ⎠ ⎝ am a1 ⎠ ⎛ a a2 a3 a4 ⎞⎛ a1 a5 ⎞ ⎛ a1 am ⎞ =⎜ 1 ⎟⎜ ⎟ ... ⎜ ⎟= ⎝ a2 a3 a4 a1 ⎠⎝ a5 a1 ⎠ ⎝ am a1 ⎠ M = (a1 , a2 )(a1 , a3 )... (a1 , am ). Далее, введем понятие циклической группы. Циклическая группа – группа, порожденная степенями одного элемента [6, с. 160]: −n − n +1 ,..., g −1 , g 0 = 1, g 1 ,..., g n−1 , g n ,... M ..., g , g (3) В таком случае будем говорить, что gM порождает циклическую группу. Очевидно, что на ней задана бинарная ассоциативная операция умножения, 0 i существует единственный единичный элемент M g , а каждому элементу M g −i ставится в соответствие обратный ему M g . Элементы такой группы могут i j повторяться (имеются равные). Пусть M g = g , i > j , тогда Mg Порядок элемента gM i− j =1 = g0 . (4) – наименьшая натуральная степень, удовлетворяющая (4) [4, с. 60]. Пусть порядок равен nM . При этом все элементы 10

1 n-1 M 1, g ,..., g (5) различны. Если найдутся одинаковые, то разность их показателей меньше, чем M n , а это противоречит определению порядка группы. Любой элемент M g m из (3) совпадает с каким-либо элементом из совокупности элементов (5), в m m mod n частности M g = g , M m mod n − остаток от деления M m на n . Получаем, что порядок группы равен порядку порождающего элемента. Перейдем к подстановкам. Допустим, что некоторая подстановка sM вида (1) из симметрической группы SM n порождает циклическую группу порядка M m , то есть элементы группы есть различные подстановки 0 1 m-1 M s = e, s , ..., s . Пусть подстановка sM k0 ≠ ak0 = k1 M перемещает некоторое число kM 0 ∈ {1, n} , то есть . Обозначим через kM i число, которое получается из kM 0 в i результате подстановки M s . При этом M ki ≠ ki +1 , так как, применяя подстановку Ms −i i i +1 k и k1 = ak0 k ≠ ak0 к kM и k , получаем числа M 0 , а M0 . Следовательно, получаем перемещаемые подстановкой M s числа M k0 , k1 , k2 ... . m 0 Очевидно, этих чисел не может быть больше M m , так как M s = s ⇒ km = k0 . Если M s исчерпывается набором чисел M k0 , k1 , ..., km−1 , то можем определить эту подстановку как цикл длины m M , иначе можем выделить в данной подстановке цикл M (k0 , k1 , ..., km−1 ) длины M m . M Пример. Пусть произвольная подстановка M s ∈ S5 задана на множестве E = {1, 2, 3, 4, 5} : 11

M ⎛1 2 3 4 5 ⎞ ⎟ ⎝5 4 2 3 1 ⎠ . s=⎜ Порождаемая ею циклическая группа ⎛1 s0 = ⎜ ⎝1 ⎛1 s3 = ⎜ ⎝5 2 3 4 5 ⎞ 1 ⎛1 ,s =⎜ 2 3 4 5 ⎟⎠ ⎝5 2 3 4 5 ⎞ 4 ⎛1 ,s =⎜ 2 3 4 1 ⎟⎠ ⎝1 2 3 4 5 ⎞ 2 ⎛1 ,s = ⎜ 4 2 3 1 ⎟⎠ ⎝1 2 3 4 5 ⎞ 5 ⎛1 ,s =⎜ 4 2 3 5 ⎟⎠ ⎝5 2 3 4 5⎞ , 3 4 2 5 ⎟⎠ 2 3 4 5⎞ , 3 4 2 1 ⎟⎠ ⎛1 2 3 4 5 ⎞ 0 s6 = ⎜ ⎟ = s , ... ⎝1 2 3 4 5 ⎠ M Как видим, порядок группы равен шести. Возьмем, к примеру, число 3. Оно является перемещаемым и M k0 = 3, k1 = 2, k2 = 4, k3 = 3, k4 = 2, k5 = 4, ... . Можем выделить цикл M (3, 2, 4 ) , длина которого равняется трем. Однако, M s не исчерпывается данным набором чисел, в подстановке также имеет место цикл M (1, 5 ) длины 2. У т в е рж д е н и е 1 . Л ю б а я н е ед и н и ч н а я п од с т а н о в ка sM ∈ S n раскладывается единственным способом в произведение независимых циклов [2, с. 96]. Доказательство. Будем проводить доказательство утверждения методом математической индукции по числу M m перемещаемых подстановкой M s чисел. Число M m не может равняться 1, так как два числа при подстановке не могут переходить в одно. Поэтому за базу индукции возьмем M m = 2 , тогда, очевидно, sM раскладывается в произведение транспозиции и циклов единичной длины из неперемещаемых элементов. Пусть утверждение доказано для подстановок, перемещающих меньше M m чисел. Докажем его для подстановки sM , перемещающей m M 12 чисел.

Предположим, что Ms перемещает какое-то число M k0 , и применим к этому i s числу подстановки M (i = 1, 2,...) таким же способом, как было показано выше. В итоге мы получим перемещаемые подстановкой M s числа M kj Допустим, что среди удовлетворяет уравнению M k0 , k1 , k2 , ..., k j ,... (6) M k j = k0 (6) является первым числом, которое , при этом все числа M Тогда мы можем выделить в подстановке sM k0 ,k1 ,...,k j-1 различны. (k ,k ,...,k ) . цикл M 0 1 j-1 Следовательно, M s = (k0 , k1 , ..., k j −1 )⋅ s , где ⎛ k0 −1 s = s ⋅ (k0 , k1 , ..., k j −1 ) = ⎜ ⎝ k0 M В свою очередь, sM k1 ... k j −1 k1 ... k j −1 a1 a '1 a2 a '2 ... am ⎞ ... a 'm ⎟⎠ . перемещает не более m M − j < m , а для такой подстановки выше было предположено, что она раскладывается единственным образом в произведение независимых циклов. Следовательно, подстановка M s тоже имеет единственное разложение по циклам. При этом циклы в разложении M s независимы, так как ⎛ k0 s = (k0 , k1 , ..., k j −1 )⋅ ⎜ ⎝ k0 k1 ... k j −1 k1 ... k j −1 a1 a '1 a2 ... am ⎞ = a '2 ... a 'm ⎟⎠ a2 ... am ⎞ = a '2 ... a 'm ⎟⎠ ⎛a = (k0 , k1 , ..., k j −1 )⋅ (k0 )⋅ (k1 )⋅ ... ⋅ (k j −1 )⋅ ⎜ 1 ⎝ a '1 a2 ... am ⎞ ⎛a = (k0 , k1 , ..., k j −1 )⋅ ⎜ 1 ⎟. a ' a ' ... a ' ⎝ 1 2 m⎠ M Утверждение доказано. 13

Глава 2. Автоморфизмы подстановок 2.1. Классы сопряженных элементов Рассмотрим некоторую мультипликативную группу MΓ и какой-либо ее −1 элемент aM . Пусть gM ∈ Γ , тогда назовем всякий элемент bM = g ag сопряженным с элементом M a [3, с. 297]. Будем обозначать сопряженность двух элементов как M b ≈ a . Свойства отношения сопряженности: 1) Рефлексивность. M a ≈ a, так как ∀a ∈Γ −1 M a = e ae. 14

2) Симметричность. b = g −1ag ⇒ gbg −1 = g g −1ag g −1 = a ⇒ a = g −1 ) ( −1 ( ) bg −1, поэтому a ≈ b и b ≈ a. M 3) Транзитивность. −1 M Пусть a = g −1bg , b = h −1ch ⇒ a = (hg ) c (hg ). Из вышеизложенных свойств видим, что отношение сопряженности является отношением эквивалентности, поэтому определяет разбиение группы M Γ на непересекающиеся классы сопряженных между собой элементов [3, с. 289]. 2.2. Автоморфизмы группы Для того чтобы задать определение автоморфизмов группы, нам необходимо рассмотреть понятие изоморфизма двух множеств. Установим между элементами двух произвольных множеств M M и M M взаимно однозначное соответствие, то есть элементу a M ∈ M соответствует элемент M a ∈ M и так далее. При этом заметим, что соотношения между элементами одного множества сохраняются и для другого множества. Такое соответствие двух множеств назовем изоморфизмом [7, с. 42]. Положим, что элементу aM группы ΓM соответствует элемент a группы Γ , a Mb a 7, взаимно однозначно а элементу b∈Γ – b ∈ Γ , b . При изоморфизме двух групп произведение элементов одной группы сопоставим произведению элементов другой группы, поэтому ab M Аналогично, если Mϕ − изоморфизм, можно записать так: 7 Здесь и далее – элементу взаимно однозначно соответствует элемент . 15 ab .

ϕ (a ) = a, ϕ (b ) = b, ϕ (c ) = c, ab = c, ab = c ⇒ ⇒ ϕ (a )ϕ (b ) = ϕ (ab ). M В частности, если Γ M = Γ , то такое соответствие элементов назовем автоморфизмом группы [7, с. 43]. Если рассматривать примеры на практике, то мы можем сравнить понятие автоморфизма с симметрией. Действительно, при симметрии некое тело в результате преобразований переходит само в себя, сохраняя соотношения между элементами тела. Покажем, что множество всех автоморфизмов группы Γ M является группой8 с определенной на ней бинарной операцией умножения. Будем рассматривать умножение двух автоморфизмов как их последовательное выполнение. Тогда: 1) Пусть Mϕ и M φ – два автоморфизма, заданных на M Γ , некоторые элементы a, b, c принадлежат Γ . Если ϕ :a b φ :b c или или ϕ (a ) = b φ (b ) = c ⇒ ϕ ⋅ φ : a c, из чего следует, что произведение двух автоморфизмов взаимно однозначно отображает группу ΓM на себя и является бинарной операцией на M Γ . 2) Пусть ϕ , φ , γ – три автоморфизма, заданных на Γ , некоторые элементы a, b, c, d принадлежат Γ . Если ϕ :a φ :b γ :c то 8 Обозначим ее как . 16 b c d ,

M φγ : b ϕφ : a d ⇒ ϕ (φγ ): a c ⇒ (ϕφ )γ : a d ⇒ ϕ (φγ )= (ϕφ )γ . d Доказали ассоциативность автоморфизмов. 3) Допустим, что автоморфизм ϕ M ставит в соответствие некоторому элементу из Γ M этот же элемент, то есть является тождественной подстановкой. ϕ (a1 )= a1 , ϕ (a2 )= a2 , ..., ϕ (an ) = an , a1 , a2 , ..., an ∈Γ. Если некоторый автоморфизм M φ такой, что φ (a1 ) = a '1 , φ (a2 ) = a '2 , ..., φ (an ) = a 'n , a1 , a2 , ..., an ∈ Γ, M то Mϕφ = φϕ , M ϕ – тождественный автоморфизм. 4) Пусть некоторый автоморфизм M γ может быть представлен как γ (a1 ) = a '1, γ (a2 ) = a '2 , ..., γ (an ) = a 'n , a1, a2 , ..., an ∈Γ. Так как автомор фи змы являют ся в заи мн о одн озн ачн ыми отображениями, то мы можем однозначно сопоставить каждому элементу aM 1, a2 , ..., an ∈Γ другой элемент из этой же группы M a '1, a '2 , ..., a 'n , и наоборот, элементам M a '1, a '2 , ..., a 'n можем однозначно сопоставить M γ −1 (a '1 ) = a1, γ −1 (a '2 ) = a2 , ..., γ −1 (a 'n ) = an . Следовательно, для каждого автоморфизма M γ найдется единственный −1 γ обратный ему автоморфизм M . 17

Рассмотрим теперь такое отображение, которое ставит в соответствие −1 некоторому элементу M a ∈ Γ сопряженный ему элемент M g ag , g ∈Γ . К тому же, (g M −1 a1 g )(g −1a2 g )= g −1a1a2 g . Делаем вывод, что данное отображение является изоморфизмом группы M Γ на себя, то есть является автоморфизмом. Назовем его внутренним автоморфизмом, а все другие автоморфизмы, если они существуют, назовем внешними [7, с. 43]. Как и было доказано выше, что множество автоморфизмов является группой, так и можно аналогично удостовериться, что множество внутренних автоморфизмов группы Γ тоже составляет группу9 относительно операции умножения (последовательного выполнения). Так как объектом наших исследований является симметрическая группа M Sn и все подстановки степени n M , которые она включает, то следует применить понятие группы автоморфизмов именно к ней. Как будет показано далее в этом параграфе, в большинстве случаев, имея дело с симметрическими группами, нам не придется сталкиваться с ее множеством внешних автоморфизмов. А внутренние автоморфизмы будут играть важную роль в установлении связи между симметриче ской группой и автоморфизмами графов. Итак, установим утверждение, которое поможет нам в дальнейшем не акцентировать внимание на выделении в каждой симметрической группе ее внешних автоморфизмов. Для начала введем следующие необходимые понятия: 9 Обозначим ее как . 18

1) Если под инвариантными элементами группы понимать такие, которые коммутируют со всеми ее элементами, то центр группы – это множество M Z всех ее инвариантных элементов [8 ,с. 68]. 2) Группа совершенна, если она без центра10 и все ее автоморфизмы внутренние [9, с. 67]. и Утверждение 1 (Теорема Гёльдера). При M n ≠ 2 n ≠ 6 симметрическая группа M Sn совершенна [9, с. 67]. Из теоремы Гельдера вытекает, что группы SM 2 и SM 6 не являются совершенными, потому что первая из них представляет собой группу двух коммутативных подстановок s1 = (12 ), s2 = (1)(2 ), s1s2 = s2 s1, M а вторая обладает внешним автоморфизмом [9, с. 69]. Во всех остальных симметрических группах M Sn группа автоморфизмов будет ограничиваться группой внутренних автоморфизмов. Таким образом, Aut (Sn ), n ≥ 3, n ≠ 6, M включает в себя все отображения вида ϕ (s ) = α −1sα , M α , s ∈ Sn , откуда делаем важный вывод, что группы автоморфизмов таких симметрических групп совпадают с самими симметрическими группами. 10 Другими словами, центр состоит из одного элемента. 19

2.3. Разложение симметрической группы на классы сопряженности Условимся, что будем рассматривать далее симметрические группы степени nM ≥ 3, n ≠ 6 . Из прошлого параграфа мы выяснили, что для Aut (Sn ), n ≥ 3, n ≠ 6, нахождения группы автоморфизмов M достаточно обозначить все подстановки, которые входят в M Sn . Как будет показано далее, удобнее структурировать симметрическую группу и начать с выделения классов сопряженности в M Sn , а затем вести подсчет различных подстановок в каждом классе. Утверждение 1. Чтобы получить из некоторой подстановки sM ∈ Sn , разложенной в произведение циклов, сопряженную ей ) Sn , нужно сделать подстановку αM каждом цикле в разложении подстановки M s [10, с. 263]. −1 M α sα (α − любая подстановка из в Доказательство. Положим s = (a1, a2 , ..., al )(b1, b2 , ..., bm )...(c1, c2 , ..., cq ), ⎛ a1 ⎜ a1 ⎝ ⎛a α −1 = ⎜ 1 ⎜ a1 ⎝ M α =⎜ a2 ... al b1 b2 ... bm ... c1 c2 ... cq ⎞ ⎟, a2 ... al b1 b2 ... bm ... c1 c2 ... cq ⎟⎠ a2 ... al b1 b2 ... bm ... c1 c2 ... cq ⎞ ⎟. a2 ... al b1 b2 ... bm ... c1 c2 ... cq ⎟⎠ Последовательно выполним подстановки (1). Получим: a1 → a2 b1 → b2 c1 → c2 M c → c3 a2 → a3 b2 → b3 ... 2 . ... ... ... al → a1 bm → b1 20 cq → c1 (1)

В итоге M ( )( )( α −1sα = a1, a2 , ..., al b1, b2 , ..., bm ... c1, c2 , ..., cq ), что и требовалось доказать. С помощью следующего утверждения мы, наконец, сможем выдвинуть правило, по которому будет происходить разложение симметрической группы M Sn на классы сопряженных элементов, а впоследствии определить количество ее автоморфизмов. Утверждение 2. Для того чтобы две подстановки были сопряжены в симметрической группе M Sn , необходимо и достаточно, чтобы существовало их разложение в произведение независимых циклов одинаковых порядков [10, с. 264]. Доказательство. Как было показано в утверждении 1, мы имеем −1 разложение двух сопряженных подстановок Ms и α M sα на соответственно одинаковые по порядку циклы. Необходимость доказана. Докажем теперь достаточность. Как мы знаем, в симметрической группе всегда найдутся такие подстановки, переводящие произвольное количество чисел в любое другое. Тогда, если две подстановки sM 1 и sM 2 из SM n раскладываются в произведение независимых циклов одинаковых порядков, то существует такая подстановка Mα ∈ Sn , которая переводит подстановку M s2 в M s1 , при этом −1 M s1 = α s2α , то есть M s1 и M s2 будут сопряжены в M Sn . Определим правило, по которому будем разбивать симметрическую группу на классы сопряженности. Пусть множество, на котором заданы подстановки, состоит из M n чисел. Тогда учтем все разбиения M n на слагаемые, обозначающие порядки циклов. Пример. Предположим M n = 7 , тогда 21

7 = 1 + 1 + 1 + 1 + 1 + 1 + 1; 7 = 1 + 1 + 1 + 1 + 1 + 2; 7 = 1 + 1 + 1 + 1 + 3; 7 = 1 + 1 + 1 + 2 + 2; 7 = 1 + 1 + 1 + 4; 7 = 1 + 1 + 2 + 3; M 7 = 1 + 1 + 5; 7 = 1 + 2 + 4; 7 = 1 + 3 + 3; 7 = 1 + 6; 7 = 2 + 5; 7 = 3 + 4; M 7 = 7. Заметим, что не имеет значения, в каком порядке стоят слагаемые в разложении nM . Действительно, подстановка не меняет смысла при перестановке циклов в ее разложении. В итоге получилось 13 классов. Произведем подсчет количества классов M m в M Sn , n ≤ 10 : Mn 1 2 3 4 5 Mm 1 2 3 5 7 Mn 6 7 8 9 10 Mm 10 13 17 21 26 2.4. Нахождение группы автоморфизмов симметрической группы Решим задачу нахождения в симметрической группе SM n , n ≥ 3, n ≠ 6, группы автоморфизмов. Вначале вычислим количество различных подстановок в каждом классе сопряженных элементов. Допустим, что в некотором классе M P разложение подстановок порядка n M по m M циклам принимает следующий вид: M n = k1 + k2 + ... + km , 22

где M k1 − длина первого цикла, M k2 − второго цикла и так далее. Воспользуемся основами комбинаторики и посчитаем, сколько различных циклов можно получить из kM 1, k2 , ..., kn чисел, а затем с помощью основного правила комбинаторики (правила умножения) вычислим количество различных подстановок в M P . Согласно урновой схеме, мы производим упорядоченный выбор чисел без возвращения, то есть будем находить число размещений для каждого цикла [11, с. 125]. Для первого цикла разместим Mn чисел по kM 1 элементам, для второго цикла – уже M n − k1 по M k2 элементам и так далее до m n − ∑ ki M m − го цикла, где разместим M i =1 по kM m элементам. Перемножим размещения по правилу умножения [12, с. 16]: Ank1 ⋅ Ank−2 k1 −k2 ⋅ ... ⋅ Akmm n − ∑ km i =1 M M (2) Однако мы данный ответ не является верным. Как было указано выше, один и тот же цикл может быть записан несколькими способами. Например, 235 ) = (352 ) = (523). M M( Поэтому число размещений включает в себя повторяющиеся циклы. Очевидно, что цикл длины M k может быть записан M k способами. Кроме того, мы не учли, что для некоторых номеров 1, M m может выполняться M ki = k j , i ≠ j. Подразумевается, что если переставить циклы в разложении подстановки, то ее смысл не изменится. Поэтому разобьем циклы по группам 23

в зависимости от их длины, и пусть у нас есть Ml таких групп. Количество циклов в M l − й группе – M ql . Сократим формулу (2) и получим количество различных подстановок M p в данном классе сопряженных элементов: p= k Ank−mk1 −...−km Ank1 An−2 k1 −k2 ⋅ ⋅ ... ⋅ k1 k2 km r Aqq ∏ i =1 = i i = M Ank1 ⋅ Ank−2 k1 −k2 ⋅ ... ⋅ Ank−mk1 −...−km m r km ∏ qi ! ∏ i =1 j =1 (3) Остается просуммировать количество подстановок для различных классов и получить конечный ответ. Пример. Пусть дана симметрическая группа SM 4 , ее степень nM = 4 . Найдем все автоморфизмы этой группы. Всего имеем пять классов сопряженности P M 1, P2 , P3 , P4 , P5 . Используя формулу (3), посчитаем количество элементов в каждом из них: 24

A41 ⋅ A31 ⋅ A21 ⋅ A11 = 1; 4! A42 1 1 ⋅ A2 ⋅ A1 2 p2 = = 6; 2! A43 1 p3 = ⋅ A = 8; 3 1 A42 A22 ⋅ 2 2 = 3; p4 = 2! A44 p5 = = 6. 4 M p1 = Составим итоговую таблицу с подстановками. Класс Разложение по циклам Сопряженные элементы в классе M p1 M4 =1+1+1+1 M (1)(2 )(3)(4 ) M p2 M4 =1+1+ 2 (1)(2 )(34 ), (1)(3)(24 ), (1)(4 )(23), 2 3 14 , 2 4 13 , 3 4 12 M ( )( )( ) ( )( )( ) ( )( )( ) M p3 M4 =1+ 3 (1)(234 ), (1)(324 ), (2 )(134 ), (2 )(314 ), 3 124 , (3) (214 ), (4 )(123), (4 )(213) M ( )( ) M p4 M4 = 2 + 2 M (12 )(34 ), (13)(24 ), (23)(14 ) M p5 M4 = 4 (1234 ), (2134 ), (2314 ), 1243), (4132 ), (3214 ) M( Порядок группы, очевидно, равен M Aut (S4 ) = 1 + 6 + 8 + 3 + 6 = 24. 25

Глава 3. Применение автоморфизмов подстановок к теории графов 3.1. Основные понятия о графах Будем рассматривать простые помеченные графы без петель с неориентированными, невзвешенными, некратными ребрами и конечным множеством вершин. Обозначим через G M (V , E ) граф G M с множеством вершин VM и множеством ребер M E . e= v ,v Если M v1 и M v2 – две вершины в графе G M , а M ( 1 2 ) – ребро, которое соединяет эти две вершины, то будем говорить, что ребро eM инцидентно вершинам vM 1 и vM 2 [13, с. 9]. При этом две вершины (или два ребра) инцидентными быть не могут. Степень вершины vM в графе G M – количество ребер, инцидентных данной вершине [13, с. 26]. 26

Назовем две вершины vM 1 и vM 2 смежными, если существует ребро e = (v1, v2 ) M , которое их соединяет. В противном случае вершины не являются смежными [13, с. 9]. V = {1, 2, ..., n} Пусть граф MG имеет M n вершин, M . Определим матрицу M A размера M n × n следующим образом: если в противном вершиныслучае , смежны i j ⎧1, Aij = ⎨ , 0, ⎩ M тогда M A – матрица смежности графа M G [13, с. 27]. 3.2. Автоморфизмы графов H V ,E Два графа G M (VG , EG ) и M ( H H ) изоморфны, если между их множе ствами вершин VM G и VH суще ствует взаимно однозначное соответствие, сохраняющее смежность [14, с.24]. Автоморфизмом графа M G (V , E ) назовем изоморфизм графа M себя. Множество всех автоморфизмов графа G G (V , E ) на образует группу 11, называемую группой графа M G [15, с. 14]. Обозначим ее как M Γ(G) . Если мы сопоставляем некоторую вершину и ее образ, в который она переходит при автоморфизме графа, то можно рассматривать такое отображение как подстановку на множестве вершин графа VM , а Γ M (G) как подгруппу симметрической группы подстановок на MV . Пример. Найдем группу автоморфизмов графа G M , изображенного на рисунке 1: 11 Относительно операции композиции автоморфизмов. 27

1 2 3 5 4 1 подстановками на множестве его Его группа может быть представленаРис. двумя вершин: ⎧⎪ a1 = (1)(2 )(3)(4 )(5 ) − ⎪⎩a2 = (12 )(4 )(35 ). тождественный автоморфизм, Γ (G ) = ⎨ M Стоит заметить, что при автоморфизме степени вершин сохраняются. У первой и второй вершин степень равняется трем, у третьей и пятой – двум, у четвертой – четырем. 3.3. Связь симметрической группы и автоморфизмов графов Обозначим через M E единичную матрицу размера M n × n , то есть матрицу, e = e = ... = enn = 1) у которой на главной диагонали стоят единицы M ( 11 22 , а все остальные элементы равны нулю. Будем говорить, что матрица M P размера n × n ортогональна, если обратная12 к ней матрица совпадает с T транспонированной13 к P . Другими словами, PP = E . Пусть ⎛ p11 p12 ⎜ p p22 P = ⎜ 21 ⎜ ... ... ⎜ ⎝ pn1 pn 2 M ... ... ... ... p1n ⎞ ⎛ p11 p21 ⎟ p2 n ⎟ T ⎜⎜ p12 p22 ,P = ⎜ ... ... ... ⎟ ⎟ ⎜ pnn ⎠ ⎝ p1n p2 n ... ... ... ... pn1 ⎞ pn 2 ⎟⎟ , ... ⎟ ⎟ pnn ⎠ 12 Такая матрица , что . 13 Транспонированная матрица получается из , если поменять местами соответствующие столбцы и строки 28

n ⎛ n 2 p1 j p2 j ∑ ⎜∑ p 1j j =1 ⎜ j =1 n ⎜ n ⎜ ∑ p2 j p1 j ∑ p 2 2 j T PP = ⎜ j =1 j =1 ⎜ ... ... ⎜ n ⎜ n ⎜ ∑ pnj p1 j ∑ pnj p2 j j =1 ⎝ j =1 M ... n ⎞ ∑ p1 j pnj ⎟ j =1 ⎟ ⎟ ... ∑ p2 j pnj ⎟ j =1 ⎟ = E. ⎟ ... ... ⎟ n ⎟ ... ∑ p 2 nj ⎟ j =1 ⎠ n (1) Тогда из уравнения (1) следует, что n 2 ij ∑p = 1, i = 1,n, j =1 n ∑p ij M pkj = 0, i, k = 1, n, i ≠ k , j =1 (2) или, другими словами, сумма квадратов элементов каждой строки матрицы M P равна одному, а сумма произведений соответствующих элементов двух строк в матрице P M равна нулю. Выполнение формул (2) и являются критерием ортогональности произвольной матрицы. Представим теперь некоторую подстановку ⎛1 M s=⎜ ⎝ a1 в матричном виде. Пусть матрица M 2 ... n ⎞ a2 ... an ⎟⎠ P (s ) такая, что если в противном элемент случае подстановки переходит в i s j ⎧1, Pij (s ) = ⎨ ⎩0, M . P s Назовем матрицу M ( ) (далее будем писать просто PM ) матрицей подстановки. 29

Пример. Дана следующая подстановка ⎛1 2 3 4 5 ⎞ s=⎜ ⎟ ⎝ 2 3 1 4 5⎠ . M Тогда ⎛0 ⎜ ⎜0 P = ⎜1 ⎜ ⎜0 ⎜0 ⎝ M 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0⎞ 0 ⎟⎟ 0 ⎟. ⎟ 0⎟ 1 ⎟⎠ Так как один элемент подстановки не может переходить сразу в два других, то в каждой строке матрицы M P будет ровно одна единица. Кроме того, два элемента подстановки не могут переходить в один и тот же, поэтому в каждом столбце содержится тоже по одной единице. Нетрудно заметить, что P M является ортогональной матрицей, проверив выполнение для нее −1 формул (2). Обратная матрица M P к M P всегда будет существовать, так как каждая подстановка имеет обратную себе. Очевидно, что множество всех матриц подстановки P M n×n будет представлять группу с операцией умножения матриц, так как является эквивалентным симметрической группе M Sn . Непосредственно умножая слева матрицу подстановки M Pn×n на матрицу смежности M An×n графа M G , имеющего M n вершин, можно удостовериться, что в результате произведения строки матрицы M A переставляются. Если умножать матрицу P M на матрицу MA справа, то переставляются столбцы. Причем правило перестановки строк и столбцов зависит от подстановки, по которой строилась матрица M P . Пример. Посмотрим, как влияет подстановка 30

M s = (1324 ) , на матрицу смежности графа M G ⎛0 ⎜ 1 A=⎜ ⎜1 ⎜ ⎝1 M 1 0 1 0 1 1 0 1 1⎞ 0 ⎟⎟ 1⎟ ⎟ 0⎠ . Представим M s в матричном виде: ⎛0 ⎜ 0 P (s ) = ⎜ ⎜0 ⎜ ⎝1 M 0 0 1 0 1 0 0 0 0⎞ 1 ⎟⎟ 0⎟ ⎟ 0 ⎠. Умножим M P слева и справа на M A : ⎛0 ⎜ 0 P⋅ A=⎜ ⎜0 ⎜ ⎝1 0 0 1 0 1 0 0 0 0⎞ ⎛0 1 ⎟⎟ ⎜⎜1 ⋅ 0 ⎟ ⎜1 ⎟ ⎜ 0 ⎠ ⎝1 1 0 1 0 1 1 0 1 1 ⎞ ⎛1 0 ⎟⎟ ⎜⎜1 = 1 ⎟ ⎜1 ⎟ ⎜ 0⎠ ⎝0 1 0 0 1 0 1 1 1 1⎞ 0 ⎟⎟ , 0⎟ ⎟ 1⎠ ⎛0 ⎜ 1 A⋅ P = ⎜ ⎜1 ⎜ ⎝1 M 1 0 1 0 1 1 0 1 1 ⎞ ⎛0 0 ⎟⎟ ⎜⎜ 0 ⋅ 1 ⎟ ⎜0 ⎟ ⎜ 0 ⎠ ⎝1 0 0 1 0 1 0 0 0 0 ⎞ ⎛1 1 ⎟⎟ ⎜⎜ 0 = 0 ⎟ ⎜1 ⎟ ⎜ 0⎠ ⎝0 1 1 0 1 0 1 1 1 1⎞ 0 ⎟⎟ . 1⎟ ⎟ 0⎠ Сравнивая результаты, мы убедились, что умножая M P слева, на место первой строки перешла третья, на место третьей – вторая, на место второй – четвертая, на место четвертой – первая. Умножая MP справа, аналогично поменялись строки в установленном подстановкой M s порядке. 31

Вернемся к автоморфизмам графов. Пусть граф M предположим, что n ≥ 3, n ≠ 6 ) вершинах (M G (V , E ) построен на M n , и ему удовлетворяет некая матрица смежности A M n×n . Установим, как связаны автоморфизмы подстановок и графы. Так же, как мы поступали с подстановками в параграфе 4.2, зададим отображение ϕ M матрицы A M в сопряженную ей матрицу −1 M B = P AP , где M P - матрица некоторой подстановки M s ∈ Sn : Mϕ : A B = P −1 AP . Как и в случае подстановок, данное отображение является внутренним T автоморфизмом. Кроме того, из ортогональности M P следует, что M B = P AP . Для того, чтобы отображение ϕ M было автоморфизмом графа, необходимо равенство матриц M A = B , поэтому получаем M A = ϕ ( A) = PT AP . Как мы знаем из параграфа 4.2, группа автоморфизмов симметрической группы степени nM ≥ 3, n ≠ 6 совпадает с ее группой внутренних автоморфизмов, а группа различных матриц P M является матричным представлением M Sn . Логично предположить из этого, что все матрицы M P , при T которых M A = P AP , будут составлять группу графа M G . 32

Заключение В ходе работы подробно рассмотрены симметрические группы и их свойства, установлена взаимосвязь между автоморфизмами подстановок и автоморфизмами графов через матрицы подстановок и смежности. Были получены следующие результаты: 1) Симметрическая группа SM n может быть разложена на классы сопряженных между собой элементов, при этом подстановки из одного класса имеют разложение на циклы одинаковых порядков. 2) Если степень симметрической группы M Sn M n ≥ 3 и отлична от шести, то группа автоморфизмов M Aut (Sn ) совпадает с самой группой M Sn . 3) Установлено, что используя матрицу смежности графа M A , подстановки на множестве вершин графа и представляя эти подстановки в виде матрицы M P , можно вывести уравнение для нахождения автоморфизмов графа A = PT AP . 33

Список литературы 1. Стиллвелл Д. Математика и ее история. М.-Иж.: Институт компьютерных исследований, 2004. 580 с. 2. Постников М. М. Теория Галуа. М.: Изд. Физ-мат. литературы, 1963. 220 с. 3. Головина Л. И. Линейная алгебра и некоторые ее приложения: Учебное пособие для вузов. Изд. 4-е., испр. М.: Наука, 1985. 392 с. 4. Гроссман И., Магнус В. Группы и их графы / Под ред. В. Е. Тараканова. М.: Мир, 1971. 231 с. 5. Математика, ее содержание, методы и значение. Том 3 / Под ред. А. Д. Александрова, А. Н. Колмогорова, М. А. Лаврентьева. М.: Изд. Академии наук СССР, 1956. 336 с. 6. Винберг Э. Б. Курс алгебры. Изд. 2-е, испр. и доп. М.: Факториал Пресс, 2001. 544 с. 34

7. Ван дер Варден Б.Л. Алгебра / Под ред. Ю. И. Мерзлякова. М.: Наука, 1979. 623 с. 8. Курош А. Г. Теория групп. Изд. 3-е, доп. М.: Наука, 1967. 648 с. 9. Каргаполов М. И., Мерзляков Ю. И. Основы теории групп. Изд. 3-е, перераб. и доп. М.: Наука, 1982. 288 с. 10. Фаддеев с: Учебное пособие для вузов. М.: Наука, 1984. 416 с. 11. Кофман А. Введение в прикладную комбинаторику / Под ред. Б.А. Севастьянова. М.: Наука, 1975. 480 с. 12. Буре В. М., Парилина Е. М. Теория вероятностей и математическая статистика: Учебник. СПб.: Лань, 2013. 416 с. 13. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384 с. 14. Харари Ф. Теория графов. Изд. 2-е / Под ред. Г. П. Гаврилова. М.: Едиториал УРСС, 2003. 296 с. 15. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977. 324 с. 35

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв