Читать курсовая по математике: "Решения комбинаторных задач теории графов с помощью теоремы Пойа" Страница 4

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

Рассмотрим теперь множество X = {1, 2, …, n}. Подстановкой называется взаимно однозначное отображение a: X → X. Умножением подстановок будем называть их композицию. Пусть A - некоторая совокупность подстановок множества X, замкнутая относительно операции умножения. Тогда A является группой подстановок на множестве объектов X. Порядок группы A, обозначаемый |A|, есть число подстановок A, а степень группы - это число n элементов в множестве объектов X. [3]

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

Транспозицией называется подстановка, меняющая два элемента местами друг с другом и оставляющая остальные элементы на своих местах. Можно показать, что любая подстановка раскладывается в произведение транспозиций. Подстановка называется четной, если число транспозиций, в которые раскладывается подстановка, четно. Пусть A - группа подстановок с множеством объектов X = {1, 2, …, n}. Циклом длины k называется подстановка, обозначаемая (i1, i2, …, ik), которая переводит i1 в i2, i2 в i3, …, ik в i1. Известно, что каждая подстановка a может быть представлена в виде произведения непересекающихся циклов. Например,

3 = {(1)(2)(3), (12)(3), (13)(2), (23)(1), (123), (132)} или A3 = {(1)(2)(3), (123), (132)}.

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

Рис. 2

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

включает все подстановки множества X, сохраняющие отношение смежности в графе G. К примеру, вершины 1 и 4 смежны в G. Подстановка (13)(2)(4) преобразует вершины 1 и 4 в вершины 3 и 4, и эти образы 3 и 4, также являются смежными. Таким образом, подстановка (13)(2)(4) сохраняет смежность вершин 1 и 4.

Так как совокупность подстановок в этом списке замкнута относительно операции умножения, то она образует группу. [2]

.3 Цикловые индексы группы подстановок

Пусть A - группа подстановок с множеством объектов X = {1, 2, …, n} и a - некоторая подстановка из этой группы. Для каждого k = 1, 2, …, n через jk(a) обозначим число циклов длины k в разложении подстановки a в произведение непересекающихся циклов.

Тогда цикловой индекс группы A, обозначаемый Z(A) или Z(A, s1, s2, …, sn), представляет собой многочлен от переменных s1, s2, …, sn, определяемый формулой

Рассмотрим для примера симметрическую группу S3. Заметим, что тождественная подстановка (1)(2)(3) имеет три единичных цикла дающих слагаемое s13. Три подстановки (1)(23), (2)(13) и (3)(12) имеют каждая по единичному циклу и по одному циклу длины 2, так что получается одно слагаемое

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