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

I

а

g₃

g₃

g₄

g₁

g₂

а³

а³

I

а

а²

g₄

g₄

g₁

g₂

g₃

,

,

,

.

Каждая строка таблицы - это перестановка верхней строки, например, последовательность g₂, g₃, g₄, g₁ (или просто 2, 3, 4, 1) во второй строке есть перестановка последовательности 1, 2, 3, 4 из первой строки. Четыре подстановки (или взаимно однозначных отображения), соответствующие перестановкам в строках, записаны справа от таблицы. Их можно представить с помощью циклов:

т₁ = (1)(2)(3)(4) = I,

т₃ = ( 1 3) (2 4),

т₂ = (1 2 3 4),

т₄=(1 4 3 2).

(Чтобы записать т₁ = I в виде циклов, нам пришлось ввести циклы, содержащие один символ.)

Пример 3.

Проверьте непосредственно, что

(а) ,

(b) ,

(с),

(d) т₂т₄ = I

и что отображения m₁, m₂, m₃, m₄ образуют группу М.

Чтобы убедиться в том, что группа М, состоящая из подстановок m₁, m₂, m₃, m₄, изоморфна группе С₄, рассмотрим такие движения квадрата, вершины которого перенумерованы цифрами 1, 2, 3, 4, в результате которых вершины перемещаются в соответствии с подстановками m₁, т₂, т₃, т₄ (рис. 16). Ясно, что т₁ - единица группы подстановок М. Сопоставим ей единичный элемент I группы С₄. Подстановка т₂ эквивалентна повороту против часовой стрелки на 90°. Сопоставим ей образующую а группы С₄.

Рис. 16

m₁ т₂ т₃ т₄

(1)(2)(3)(4) (1 2 3 4) (1 3)(2 4) (1 4 3 2)

Пример 4. Отобразите оставшиеся элементы т₃ и т₄ группы М на элементы группы С₄ таким образом, чтобы группа М отображалась на группу С₄ изоморфно.

Возникает естественный вопрос: почему отображения, выписанные в таблице, образуют группу, изоморфную исходной? Вот вкратце основные соображения по этому поводу. Четыре отображения т_j (j = 1, 2, 3, 4) можно описать так:

т. е. m_j - это отображение

g_i > g_j g_i (i = 1, 2, 3, 4 ).

Отображение m_jm_k есть последовательное выполнение отображений m_j и m_k, т.е. при m_jm_k

g_i > g_j g_i,

а затем

g_i > g_k g_i.

Таким образом, при отображении m_jm_k

g_i > g_j (g_k g_i)=( g_j g_k) g_i.

Следовательно, существует взаимно однозначное соответствие между произведениями m_jm_k в группе подстановок и произведениями g_j g_k в группе С_4.

Рис. 17

Теперь найдем представление четвертой группы D₂ в виде группы подстановок.

	I	a	b	ab
	g1	g2	g3	g4
I	I	a	b	ab
g1	g1	g2	g3	g4
a	a	I	ab	b
g2	g2	g1	g4	g3
b	b	ab	I	a
g3	g3	g4	g1	g2
ab	ab	b	a	I
g4	g4	g3	g2	g1

,

,

,

.

Элементы группы подстановок М записаны в виде двух строк, заключенных в скобки. Их можно следующим образом выразить как произведения циклов:

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

Значительный интерес представляют группы, связанные с самосовмещениями пяти правильных многогранников: тетраэдра, куба (гексаэдра), октаэдра, додекаэдра и икосаэдра. Мы подробно остановимся на группе тетраэдра.

Следует помнить, что в качестве групповой бинарной операции здесь, как и во всех группах движений, рассматривается суперпозиция, или «последовательное выполнение». (Для наглядности будем использовать какую-нибудь модель тетраэдра.)

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

Выберем за ось вращения перпендикуляр, опущенный из вершины 4 на плоскость треугольника с вершинами 1, 2 и 3, и зададим на ней направление, как показано на рис. 18. Мы рассматриваем стрелку на оси как конец ввинчивания винта. При вращении вокруг этой оси верхняя вершина 4 отмеченные на рис. буквами I, r, r². Заметим, что изображенные на рис. 18 вращения исчерпывают все движения тетраэдра, при которых он совмещается сам с собой, а вершина 4 остается на месте. Аналогичная ситуация возникает и при рассмотрении других вершин, и потому мы имеем всего 4Ч2 = 8 нетождественных самосовмещений тетраэдра, при которых какая-либо одна вершина остается неподвижной.



Рис. 18

Легко видеть также, что единственными самосовмещениями тетраэдра, при которых ни одна из вершин не остается на месте, являются вращения на 180? вокруг трех его медиан. Таким образом. Существует всего двенадцать самосовмещений правильного тэтраэдра. Группа тэтраэдра имеет порядок 12.

Рис. 19

А также следует проверить, что все двенадцать самосовмещений тетраэдра являются комбинациями движений r и f, т. е. r и f порождают группу тетраэдра. Отметим, в частности, что опрокидывание относительно каждой из трех медиан можно представить в виде слова от r и f. Но эти движения дают конкретное представление четверной группы. Следовательно, четверная группа является подгруппой группы тетраэдра.

Образующие элементы r и f можно представлять себе как отображения множества, состоящего из четырех вершин, на себя:

Отметим, что как r, так и f являются произведениями двух циклов, содержащих по два символа каждый.

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

Рис. 20

Рассмотрим усеченный тетраэдр, изображенный на рис. 20,а). Треугольник при каждой вершине соответствует вращению порядка 3. На рис. 20, б) мы снабдили стороны треугольников стрелками, чтобы напомнить о вращении вокруг фиксированной вершины тетраэдра. Когда мы увидим, как из этого представления самосовмещений получается граф, станет ясно, почему мы выбрали именно такие направления, которые показаны на рисунке. Отрезок, соединяющий два треугольника, можно рассматривать как представление опрокидывания относительно медианы (порядок этого движения равен 2). Напоминаем, что образующие порядка 2 изображались на графе группы как один отрезок без стрелки; поэтому мы не ставим стрелок и на соответствующих ребрах тетраэдра, изображенного на рис. 20, б).

Заметим, что грани усеченного тетраэдра - это треугольники и шестиугольники. Чтобы перейти к двумерному представлению, сплющим наш тетраэдр так, чтобы в середине оказался треугольник или шестиугольник (рис. 21). В этих плоских представлениях каждый направленный отрезок, соответствующий вращению r на 120°, изображается непрерывной линией, а каждый отрезок, соответствующий опрокидыванию f порядка 2, - пунктирной линией. Две сети, изображенные на рис. 21, топологически эквивалентны.

Рис. 21

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

Определяющие соотношения для группы тетраэдра A₄. Группа A₄ полностью определяется следующими данными:

A₄ порождается двумя образующими, обозначаемыми через r и f;

эти образующие удовлетворяют определяющим соотношениям

r3 = I, f2 = I, rfrfrf = I [или (rf)3 = I ]. [2]



4. Практическая часть

Задание 1

Докажите, что множество подстановок

e = ;

f = ;

g = ;

h = .

с операцией - композицией преобразований - является группой. [5]

Решение.

Для проверки замкнутости нашей операции нам нужно вычислить 4Ч4=16 произведений, которые удобно разместить в таблице Кели.

	e	f	g	h
e	e	f	g	h
f	f	g	h	e
g	g	h	e	f
h	h	e	f	g

Наша операция определена, так как таблица заполнена и новых подстановок не возникло. Первый столбец произведений совпадает с левым входным столбцом, т.е. элемент e является правым нейтральным. Аналогично из совпадения первой строки произведений с верхней строкой следует, что e является левым нейтральным элементом, т. е. e - единственная и двусторонняя единица.

Так как в каждой строке и в каждом столбце содержится единица e, то каждый элемент имеет как левый, так и правый обратный, и поэтому в силу ассоциативности умножения подстановок каждый элемент обладает единственным обратным. Пусть - левый обратный, - правый обратный к элементу e. Тогда

.

С другой стороны,

, т. е. = .

Так как наша таблица симметрична относительно главной диагонали, то группа коммутативна.

Задание 2

В группе

M = {a₁, a₂, a₃, a₄, a₅, a₆}

a) найти все подгруппы;

b) найдите правые смежные классы по каждой подгруппе;

c) найдите левые смежные классы по каждой подгруппе;

d) определите, какие из подгрупп нашей группы являются нормальными. [5]

Решение.

Составим таблицу Кели:

	a1	a2	a3	a4	a5	а6
a1	a1	a2	a3	a4	a5	а6
a2	a2	a1	а6	a5	a4	a3
a3	a3	a5	a1	а6	a2	a4
a4	a4	а6	a5	a1	a3	a2
a5	a5	a3	a4	a2	а6	a1
а6	а6	a4	a2	a3	a1	a5

a) Наша группа конечна и ее порядок равен 6. По теореме Лагранжа она может иметь подгруппы только следующих порядков: первого, второго, третьего, шестого. Первый порядок имеет единичная подгруппа, шестой - сама группа. Найдем циклические подгруппы, порожденные отдельными элементами. Из таблицы видно, что

,

т. е. a₂, a₃, a₄ являются элементами второго порядка, среди их степеней содержатся только по два различных элемента. Поэтому {a₁,a₂},{a_1,a₃},{a_1,a₄} есть подгруппы второго порядка. Далее в таблице Кели находим

,

.,

т. е. являются взаимно обратными элементами третьего порядка. Они порождают одну и ту же циклическую подгруппу {a_1,a₅,а₆}. Других подгрупп третьего порядка нет. Итак, наша группа содержит четыре собственные подгруппы (три второго порядка и одну третьего порядка).

b) Подгруппа {a_1,a₅,а₆} - первый смежный класс по подгруппе третьего порядка.

Подгруппа {a₁,a₂} - первый смежный класс по подгруппе второго порядка. Возьмем любой элемент вне этой подгруппы, например, a₃, умножаем все элементы подгруппы на него, используя таблицу Кели. Получаем

, ,

т. е. {a₃,a₆}- второй правый смежный класс. Очевидно, что оставшиеся два элемента группы составляют третий правый смежный класс: {a_4,a₅}. Итак, мы получили разложение:

М = {a₁,a₂}{a₃,a₆}{a_4,a₅}.

Подгруппа {a_1,a₃} - второй смежный класс по подгруппе второго порядка. Возьмем любой элемент вне этой подгруппы, например, a₂, умножаем все элементы подгруппы на него, используя таблицу Кели. Получаем

, ,

т. е. {a₂,a₅}- второй правый смежный класс. Очевидно, что оставшиеся два элемента группы составляют третий правый смежный класс: {a_4,a₆}. Итак, мы получили разложение:

М = {a₁,a₃}{a₂,a₅}{a_4,a₆}.

Подгруппа {a_1,a₄} - третий смежный класс по подгруппе второго порядка. Возьмем любой элемент вне этой подгруппы, например, a₂, , умножаем все элементы подгруппы на него, используя таблицу Кели. Получаем

, ,

т. е. {a₂,a₆}- второй правый смежный класс. Очевидно, что оставшиеся два элемента группы составляют третий правый смежный класс: {a_3,a₅}. Итак, мы получили разложение:

М = {a₁,a₄}{a₂,a₆}{a_3,a₅}.

c) Подгруппа {a_2,a₃,а₄} - первый смежный класс по подгруппе третьего порядка.

Подгруппа {a₁,a₂} - первый смежный класс по подгруппе второго порядка. Умножив слева на a₃, получим

, ,

т. е. {a₃,a₅}- второй левый смежный класс. Тогда {a_4,a₆} третий смежный класс. Итак, мы получили разложение:

М = {a₁,a₂}{a₃,a₅}{a_4,a₆}.

Подгруппа {a_1,a₃} - второй смежный класс по подгруппе второго порядка. Возьмем любой элемент вне этой подгруппы, например, a₂, умножаем слева все элементы подгруппы на него, используя таблицу. Получаем

, ,

т. е. {a₂,a₆}- второй правый смежный класс. Очевидно, что оставшиеся два элемента группы составляют третий правый смежный класс: {a_4,a₅}. Итак мы получили разложение:

М = {a₁,a₃}{a₂,a₆}{a_4,a₅}.

Подгруппа {a_1,a₄} - третий смежный класс по подгруппе второго порядка. Умножив слева на a₂, получим

, ,

т. е. {a₂,a₅}- второй правый смежный класс. Очевидно, что оставшиеся два элемента группы составляют третий правый смежный класс: {a_3,a₆}. Итак мы получили разложение:

М = {a₁,a₄}{a₂,a₅}{a_3,a₆}.

d) Так как разложения в правые и левые смежные классы по подгруппе совпадают, то такая подгруппа называется нормальной (инвариантной). В нашем случае, нормальная подгруппа - подгруппа третьего порядка. Из приведенных рассуждений видно, что подгруппа индекса 2 всегда инвариантна.



Заключение

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

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

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



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

[1] Алексеев В.Б., Ложкин С.А. Элементы теории графов, схем и автоматов: Учебное пособие для студентов.- Москва.: Издательский отдел ф-та ВМиК МГУ (лицензия ЛР N 040777 от 23.07.1996), 2000 г. - 58 с.

[2] Гросман И., Магнус В. Группы и их графы.- Москва: Издательство «Мир», 1971 г. - 247 с.

[3] Кравец Е.В., Ситкевич И.И., Столярова Т.В. Дискретная математика (теория графов) - Могилев: УО «МГУ им. А.А. Кулешова», 2009.-68 с.

[4] Ленг С. Алгебра.- Москва: Издательство «Мир», 1971 г. - 553 с.

[5] Шнеперман Л. Б. Сборник задач по алгебре и теории чисел: Учебное пособие дли физ.- мат. Факультетов пед. Институтов.- Минск: Выш. Школа,1982. - 223 с.

Размещено на Allbest.ru