Группы и их графы

 

Министерство  образования Республики Беларусь

 

Кафедра алгебры и геометрии

Курсовая  работа на тему:

Группы  и их

графы

Выполнила:

студентка 4 курса

физико-математического

факультета  группы Б

Лужко Анна Сергеевна

 

 

 

 

 

Могилев 2012

 

Оглавление

Введение 3

Теоретическая часть 4

1. Группы 4

1.1 Понятие алгебраической операции 4

1.2 Свойства алгебраических операций. 4

1.3 Изоморфизм групп. 6я

1.4 Понятие подгруппы. 7

1.5 Смежные классы; классы сопряженных элементов 8

1.6 Нормальные подгруппы. Фактор - группы. 10

1.7 Гомоморфизм. 11

1.8 Циклические группы. 13

2. Теория графов 17

2.1. Основные определения 17

2.1.1. Графы специального вида 18

2.1.2. Изоморфизм графов 19

2.1.3. Способы задания графа 20

2.2. Маршруты, цепи и циклы 21

2.3. Деревья 23

2.4. Эйлеровы и гамильтоновы циклы 25

2.5. Планарность.Двойственные графы 26

2.5.1. Планарные графы 26

2.5.2. Двойственные графы 27

3. Группы и их графы 29

3.1. Группы подстановок 29

3.2. Группа тетраэдра. 34

Практическая часть 38

Заключение 41

Список использованных источников 42

 

 

Введение

Теория  групп начала оформляться в качестве самостоятельного раздела математики в конце восемнадцатого века. В  течение первых десятилетий девятнадцатого века она развивалась медленно и практически не привлекала к себе внимания. Но затем, около 1830 года, благодаря работам Галуа и Абеля о разрешимости алгебраических уравнений всего за несколько лет она совершила гигантский скачок, который оказал глубокое влияние на развитие всей математики.

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

Данная  курсовая работа посвящена группам  и их графическому представлению. Наша первая задача - выяснить, что же такое «группа».

Основная  идея дальнейших рассмотрений, проникающая  в самую сущность понятия группы, связана с концепцией структуры. Перед нами развернется ряд примеров и пояснений, определений и теорем, варьирующих одну основную тему - как группы и их графы представляют и иллюстрируют одну из разновидностей математической структуры.

 

Теоретическая часть

1. Группы

1. Понятие алгебраической операции

  Говорят, что на множестве X определена алгебраическая операция(*), если каждой упорядоченной паре элементов поставлен в соответствие некоторый элемент называемый их произведением.

Примеры.

1. Композиция перемещений на множествах является алгебраической операцией.
2. Композиция подстановок является алгебраической операцией на множестве всех подстановок степени n.
3. Алгебраическими операциями будут и обычные операции сложения, вычитания и умножения на множествах соответственно целых, вещественных и комплексных чисел. Операция деления не будет алгебраической операцией на этих множествах, поскольку частное не определено при . Однако на множествах , это будет алгебраическая операция.
4. Сложение векторов является алгебраической операцией на множестве .
5. Векторное произведение будет алгебраической операцией на множестве .
6. Умножение матриц будет алгебраической операцией на множестве всех квадратных матриц данного порядка.

2. Свойства алгебраических операций.

1. Операция (*) называется ассоциативной, если

.

Это свойство выполняется во всех приведенных  выше примерах, за исключением операций вычитания (и деления) и операции векторного умножения векторов. Наличие свойства ассоциативности позволяет определить произведение любого конечного множества элементов. Например, если , . В частности можно определить степени с натуральным показателем: . При этом имеют место обычные законы: , .

2. Операция (*) называется коммутативной, если

.

В приведенных выше примерах операция коммутативна в примерах 3 и 4 и не коммутативна в остальных случаях. Отметим, что для коммутативной  операции .

3. Элемент называется нейтральным для алгебраической операции (*) на множестве X, если . В примерах 1-6 нейтральными элементами будут соответственно тождественное перемещение, тождественная перестановка, числа 0 и 1 для сложения и умножения, нулевой вектор, единичная матрица. Для векторного произведения нейтральный элемент отсутствует. Отметим, что нейтральный элемент (если он существует) определен однозначно. В самом деле, если - нейтральные элементы, то . Наличие нейтрального элемента позволяет определить степень с нулевым показателем: .
4. Допустим, что для операции (*) на X существует нейтральный элемент. Элемент называется обратным для элемента , если . Отметим, что по определению . Все перемещения обратимы также как и все подстановки. Относительно операции сложения все числа обратимы, а относительно умножения обратимы все числа, кроме нуля. Обратимые матрицы - это в точности все матрицы с ненулевым определителем. Если элемент x обратим, то определены степени с отрицательным показателем: . Наконец, отметим, что если x и y обратимы, то элемент также обратим и . (Сначала мы одеваем рубашку, а потом куртку; раздеваемся же в обратном порядке!).

Определение (абстрактной) группы.

Пусть на множестве G определена алгебраическая операция (*). (G,*) называется группой, если

1. Операция (*) ассоциативна на G.
2. Для этой операции существует нейтральный элемент e (единица группы).
3. Каждый элемент из G обратим.

Примеры групп.

1. Любая группа преобразований.
2. (Z, +), (R, +), (C, +).

Простейшие  свойства групп. В любой группе выполняется закон сокращения: (левый закон сокращения; аналогично, имеет место и правый закон).

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

Домножим  равенство слева на и воспользуемся свойством ассоциативности:

.

1. Признак нейтрального элемента:

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

Применим  к равенству  закон сокращения.

2. Признак обратного элемента:

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

Применим  закон сокращения к равенству  .

3. Единственность обратного элемента. Обратный элемент определен однозначно. Следует из п.3.
4. Существование обратной операции. Для любых двух элементов произвольной группы G уравнение имеет и притом единственное решение.

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

Непосредственно проверяется, что  (левое частное элементов ) является решением указанного уравнения. Единственность вытекает из закона сокращения, примененного к равенству .

Аналогично  устанавливается существование  и единственность правого частного.

3. Изоморфизм групп.

Отображение двух групп G и K называется изоморфизмом, если

1.Отображение j взаимно однозначно.

2.Отображение j сохраняет операцию:

.

Поскольку отображение обратное к j также является изоморфизмом, введенное понятие симметрично относительно групп G и K , которые называются изоморфными.

Примеры.

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

2.Группа  диэдра  и соответствующая пространственная группа изоморфны.

Группа  тетраэдра T изоморфна группе состоящей из четных подстановок четвертой степени. Для построения изоморфизма достаточно занумеровать вершины тетраэдра цифрами 1,2,3,4 и заметить, что каждый поворот, совмещающий тетраэдр с собой некоторым образом переставляет его вершины и, следовательно, задает некоторую подстановку множества{1,2, 3, 4} Повороты вокруг оси, проходящей через некоторую вершину (например 1), оставляет символ 1 на месте и циклически переставляет символы 1, 2, 3. Все такие перестановки - четные. Поворот вокруг оси, соединяющей середины ребер (например, 12 и 34 ) переставляет символы 1 и 2 , а также 3 и 4. Такие перестановки также являются четными.

Формула определяет взаимно однозначное соответствие между множеством R вещественных чисел и множеством положительных чисел. При этом . Это означает, что является изоморфизмом.

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

4. Понятие подгруппы.

Непустое  подмножество называется подгруппой, если само является группой. Более подробно это означает, что , и .

Признак подгруппы.

Непустое  подмножество будет подгруппой тогда и только тогда, когда .

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

В одну сторону это утверждение  очевидно. Пусть теперь - любой элемент. Возьмем в признаке подгруппы. Тогда получим . Теперь возьмем . Тогда получим .

Примеры подгрупп.

Для групп преобразований новое и  старое понятие подгруппы равносильны между собой.

- подгруппа четных подстановок.

 и т.д.

Пусть G - любая группа и - любой фиксированный элемент. Рассмотрим множество всевозможных степеней этого элемента. Поскольку , рассматриваемое множество является подгруппой. Она называется циклической подгруппой с образующим элементом g .

Пусть любая подгруппа. Рассмотрим множество - централизатор подгруппы H в группе G. Из определения вытекает, что если , то , то есть . Теперь ясно, что если , то и и значит централизатор является подгруппой. Если группа G коммутативна, то . Если G=H, то централизатор состоит из тех элементов, которые перестановочны со всеми элементами группы; в этом случае он называется центром группы G и обозначается Z(G).

Замечание об аддитивной форме записи группы.

Иногда, особенно когда операция в группе коммутативна, она обозначается (+) и называется сложением. В этом случае нейтральный элемент называется нулем и удовлетворяет условию: g+0=g. Обратный элемент в этом случае называется противоположным и обозначается (-g). Степени элемента g имеют вид g+g+...+g , называются кратными элемента g и обозначаются ng.

1.5 Смежные классы; классы сопряженных элементов.

Пусть, как и выше, некоторая подгруппа. Реализуем H как группу L(H,G) левых сдвигов на группе G. Орбита называется левым смежным классом группы G по подгруппе H. Аналогично, рассматривая правые сдвиги, приходим к правым смежным классам .Заметим, что стабилизатор St(g, L(H,G)) (как и St(g, R(H,G))) тривиален поскольку состоит из таких элементов , что hg=g . Поэтому, если группа H конечна, то все левые и все правые смежные классы состоят из одинакового числа элементов, равного .

Орбиты  группы называются классами сопряженных элементов группы G относительно подгруппы H и обозначаются Если G=H, говорят просто о классах сопряженных элементов группы G. Классы сопряженных элементов могут состоять из разного числа элементов . Это число равно , где Z(H,g) подгруппа H , состоящая из всех элементов h перестановочных с g.

Пример.

Пусть - группа подстановок степени 3. Занумеруем ее элементы: =(1,2,3); =(1,3,2); =(2,1,3); =(2,3,1); =(3,1,2); =(3,2,1). Пусть . Легко проверить, что левые смежные классы суть:

, , .

Правые  смежные классы:

, , .

Все эти классы состоят из 2 элементов.

Классы  сопряженных элементов G относительно подгруппы H:

, , , .

В то же время, , , .

Теорема 1. (Лагранжа).

Пусть H подгруппа конечной группы G. Тогда порядок H является делителем порядка G.

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

По  свойству орбит G представляется в виде объединения непересекающихся смежных классов: . Поскольку все смежные классы состоят из одинакового числа элементов, , откуда и вытекает теорема.

Замечание.

Число s левых (или правых) смежных классов называется индексом подгруппы .

Следствие.

Две конечные подгруппы группы G порядки которых взаимно просты пересекаются только по нейтральному элементу.

В самом деле, если эти подгруппы, то их общая подгруппа и по теореме Лагранжа - общий делитель порядков H и K то есть 1.

6. Нормальные подгруппы. Фактор - группы.

Пусть любая подгруппа и - любой элемент. Тогда также является подгруппой G притом изоморфной H, поскольку отображение сопряжения является изоморфизмом. Подгруппа называется сопряженной по отношению к подгруппе H.

Определение.

Подгруппа H называется инвариантной или нормальной в группе G, если все сопряженные подгруппы совпадают с ней самой: .

Равенство можно записать в виде Hg = gH и таким образом, подгруппа инвариантна в том и только в том случае, когда левые и правые смежные классы по этой подгруппе совпадают.

Примеры.

В коммутативной группе все подгруппы  нормальны, так как отображение сопряжения в такой группе тождественно.

В любой группе G нормальными будут , во первых, тривиальная подгруппа и, во вторых, вся группа G. Если других нормальных подгрупп нет, то G называется простой.

В рассмотренной выше группе подгруппа не является нормальной так как левые и правые смежные классы не совпадают. Сопряженными с H будут подгруппы и