Читать курсовая по математике: "Практическое применение теоремы Пойа и перечисления графов" Страница 3

(Назад) (Cкачать работу)

Группы подстановок и их цикловой индекс.

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

Множество Г называется группой, если на нем задана бинарная операция (·), не выводящая за пределы множества и удовлетворяющая следующим трем условиям:

. Для любых x, y и z из Г справедливо (x·y)·z = x·(y·z);

. В Г существует единичный элемент e, такой что для любого x из Г e·x = x·e = x;

3. Для любого элемента x из Г существует обратный элемент также из множества Г, такой что .

Непустое подмножество A множества Г называют подгруппой группы Г, если оно удовлетворяет следующим двум условиям:

. Бинарная операция не выводит за пределы подмножества A;

2. Для любого элемента x из A обратный к нему элементтакже лежит в A.

Пусть A - некоторая подгруппа группы Г. Правым классом смежности группы Г по подгруппе A называется множество вида Ax , где x - произвольный элемент из Г (аналогично определяются левые классы смежности). Известно также утверждение о том, что если A - подгруппа группы Г, то группу Г можно разложить в объединение правых (левых) классов смежности по подгруппе A.

Рассмотрим теперь множество . Подстановкой называется взаимно однозначное отображение . Умножением подстановок будем называть их композицию. Пусть A - некоторая совокупность подстановок множества X, замкнутая относительно операции умножения. Тогда A является группой подстановок на множестве объектов X. Порядок группы A, обозначаемый |A|, есть число подстановок A, а степень группы - это число n элементов в множестве объектов X.

Наиболее важными для нас примерами группы подстановок являются симметрическая группа Sn - группа всех подстановок на множестве из n объектов, изнакопеременная группа An - группа всех четных подстановок. Чтобы определить понятие четной подстановки введем понятие транспозиции.

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

Пусть A - группа подстановок с множеством объектов . Циклом длины k называется подстановка, обозначаемая , которая переводитИзвестно, что каждая подстановка a может быть представлена в виде произведения непересекающихся циклов.

Например,

или

.

Существует естественная связь между группами подстановок и графами.

Рассмотрим два графа . Взаимно однозначное отбражение a множества вершин графа на множество вершин графа , сохраняющее смежность, называютизоморфизмом. Если , то a называется автоморфизмом графа. Совокупность всех автоморфизмов графа G, обозначаемая Г(G), образует группу, называемуюгруппой графа G, или группой автоморфизмов графа G. Таким образом, элементы группы Г(G) являются подстановками, действующими на множестве вершин графа.

Рассмотрим граф G, изображенный на рисунке.

Рисунок 1.2 - граф G

Его четыре вершины составляют множество X целых чисел 1, 2, 3, 4. Заметим, что следующий список подстановок

·

·

·

·

включает все подстановки множества X, сохраняющие отношение смежности в графе G. К примеру, вершины 1 и 4 смежны в G.

Похожие работы