[МУЗЫКА] [МУЗЫКА] В начальных лекциях этого модуля мы говорили с вами о свойствах графов. Сегодня мы поговорим об основных свойствах теории групп, и мы введем основные понятия теории групп, которые нам понадобятся в дальнейшем на протяжении всего курса. Итак, группой G называется множество элементов с бинарной операцией, таких, что на ней выполняются следующие аксиомы. Для любых двух элементов группы выполняется условие замкнутости. Для любых трех элементов выполняется условие ассоциативности. В группе существует единичный элемент, и для любого элемента существует обратный элемент в группе. Если бинарная операция является коммутативной, то есть любые два элемента коммутируют друг с другом, то в этом случае группа называется коммутативной, или абелевой. Обычно под бинарной операцией понимается сложение или умножение элементов. При умножении двух элементов, скажем, f и g, результатом бинарной операции будет являться тоже элемент fg — это мультипликативная запись. А вот аддитивная запись используется, когда результатом бинарной операции служит сумма двух элементов. При мультипликативной записи единичный элемент группы обычно называют единицей, а при аддитивной записи единичный элемент называется нулем. Простейшими примерами групп являются числовые группы, к которым относятся все числовые системы, в частности, целые, действительные, рациональные, комплексные — все они образуют аддитивные абелевы группы. А если мы с вами возьмем ненулевые рациональные, действительные и комплексные числа, то они образуют мультипликативные абелевы группы. Если множество G является конечным, то и группа в этом случае также будет являться конечной, а порядком конечной группы служит число ее элементов. Под порядком элемента группы понимается минимальное число k, которое нам необходимо для того, чтобы умножить само число на себя и получить единичный элемент группы. Теперь давайте мы с вами рассмотрим конечную группу G и некоторое ее подмножество S. Множество S называется порождающим множеством, а его элементы — порождающими элементами, если любой другой элемент группы можно представить как конечную последовательность порождающих элементов. Естественно, с учетом той бинарной операции, которая имеется на группе. У группы G, порожденной этим множеством S, имеется свое специальное обозначение, которое вы сейчас видите на слайде. Так, например, конечная аддитивная группа целых чисел по модулю n порождается каждым из взаимно простых с n элементов. Конечная группа G по определению является циклической, если она может быть порождена одним-единственным элементом, скажем, G, то есть элементы группы тогда будут являться степенями этого элемента. Так, например, элементы циклической группы порядка 3 могут быть записаны так, как вы это сейчас видите на слайде. Если у нас имеются две группы, скажем, G и H, с некоторыми бинарными операциями, то они являются изоморфными тогда и только тогда, когда существует взаимно однозначное отображение одной группы в другую, при котором сохраняется бинарная операция. Так, например, каждая конечная циклическая группа изоморфна группе целых чисел по модулю n. Различных групп существует не так уж и мало, их много. И помимо простейших числовых групп, которые мы с вами уже рассмотрели, существуют также группы преобразований, к которым относится группа симметрий правильной призмы, или правильного n-угольника. По определению, а это будет диэдральная группа, так вот, по определению диэдральная группа степени n состоит из 2n элементов. При этом n элементов являются поворотами на угол 2πk / n, а другие n элементов — это отражения относительно прямых, которые проходят через центр и вершины нашего многоугольника либо через центр и середины сторон. Порождающее множество диэдральной группы степени n состоит из двух преобразований: из поворота на угол 2π / n и любого из отражений. Таким образом, диэдральная группа степени n состоит из вращений и отражений правильного n-угольника. Важным примером групп на перестановках является симметрическая группа. Напомню вам, что перестановкой π на множестве X, состоящем из n элементов, называется взаимно однозначное отображение множества X на себя. Мы будем записывать с вами перестановку в виде одной строки, содержащей только образы наших элементов, образы элементов множества. Тогда произведением двух перестановок π и τ является также перестановка, которая получается применением сначала перестановки τ, а потом перестановки π. Эта операция также называется композицией отображений, а порядок умножения справа налево соответствует порядку записи композиции функций. Симметрическая группа степени n содержит n! перестановок на множестве из n элементов. Ее бинарной операцией является произведение перестановок, а единичным элементов будет являться тождественная перестановка. Нетрудно показать, что всякая симметрическая группа степени n ≥ 3 будет являться некоммутативной. Так, для n = 3 можно показать, что такие перестановки, как [2 3 1], а также [1 3 2] не коммутируют. Если мы умножим одну на другую, а потом наоборот, то мы получим разные перестановки, что и скажет нам о том, что группа не является коммутативной, то есть не является абелевой. На самом деле симметрическая группа степени n обладает различными системами образующих. В частности, такую систему образуют транспозиции двух соседних элементов. В целом же, если мы возьмем перестановку на n элементах, то у нас будет n − 1 транспозиция двух соседних элементов. Так вот, множество таких транспозиций известно как множество Коксетера, которое порождает симметрическую группу степени n. Оно играет важную роль в комбинаторике групп Коксетера. Кроме этого, на симметрической группе с этим порождающим множеством возникает некоторый граф, который называется Bubble sort граф, то есть пузырьковый граф. Я уверена, что вы наверняка слышали или читали о пузырьковой сортировке в книгах Кнута. Так вот, это то самое. Более того, такой граф на самом деле изоморфен графу перестановочного многогранника, который возникает в геометрии. На этом мы сегодня закончим, а в следующий раз мы продолжим говорить о том, какие неожиданные применения симметрической группы возникают не только в математических дисциплинах, но и в других. В частности, мы поговорим о том, как такие графы возникают в биоинформатике.
