Теорема Пойа и перечисление графов

Содержание
Введение……………………………………………………………………..	3
1 ТЕОРЕМА ПОЙА И ПЕРЕЧИСЛЕНИЕ ГРАФОВ……………………	5
Понятия теории графов и теории групп……………………	5
Эквивалентность, порождаемая группой подстановок…….	14
Теорема Пойа………………………………………………….	17
ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ ТЕОРЕМЫ ПОЙА И ПЕРЕЧИСЛЕНИЯ ГРАФОВ………………………………………..	20
Решение задач о перечислении графов с помощью теоремы Пойа………………………………………………………………	20
Заключение…………………………………………………………...........	26
Список используемых источников……………………………………….	28

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

Графы – это замечательные  математические объекты, с помощью, которых можно решать математические, экономические и логические задачи. Также можно решать различные  головоломки и упрощать условия  задач по физике, химии, электронике, автоматике. Сама теория графов является частью как топологии, так и комбинаторики.

Решение многих задач перечисления графов сводится к подсчету числа  классов эквивалентностей. Эффективный  метод решения таких задач  базируется на известной теореме  Пойа.

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

Задачи исследования:

1. Изучить такие основополагающие понятия теории графов и теории групп, как граф, группа подстановок и её цикловой индекс.
2. Рассмотреть определение эквивалентности, порождаемое группой подстановок, и доказать лемму Бернсайда о числе классов такой эквивалентности.
3. Разобрать определение перечня конфигурации и доказать теорему Пойа.
4. Рассмотреть задачу о перечислении графов и метод её решения с помощью теоремы Пойа.

Объектом исследования: теория графов.

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

 Работа состоит из двух разделов -  теоретической и практической части.

В ходe работы нами использовались слeдующиe мeтоды исслeдования: изучeниe научной, учeбной и мeтодичeской литeратуры, Интeрнeт-источников, анализ, обобщeниe и систематизация.

 

1. Теорема Пойа и перечисление графов.

 

1.1 Понятия теории графов и теории групп.

 

В математической теории графов и информатике граф — это совокупность непустого множества вершин и  множества пар вершин (связей между  вершинами). Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах [2].

Граф, или неориентированный  граф   — это упорядоченная пара , для которой выполнены следующие условия:

 —  это непустое множество вершин или узлов,

 —  это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

  (а значит и, , иначе оно было бы мультимножеством) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становится ложным в случае бесконечных множеств.

Вершины и рёбра графа  называются также элементами графа, число вершин в графе  —  порядком, число рёбер   — размером графа.

Вершины  и  называются концевыми вершинами (или просто концами) ребра . Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними. Два ребра называются смежными, если они имеют общую концевую вершину. Два ребра называются кратными, если множества их концевых вершин совпадают. Ребро называется петлёй, если его концы совпадают, то есть . Степенью   вершины называют количество инцидентных ей рёбер (при этом петли считают дважды). Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Ориентированный граф.

Ориентированный граф (сокращённо орграф)   — это упорядоченная пара , для которой выполнены следующие условия:

 — это непустое множество вершин или узлов,

 — это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Рисунок 1.1 – Ориентированный  граф

  Дуга — это упорядоченная пара вершин , где вершину называют началом, а — концом дуги. Можно сказать, что дуга   ведёт от вершины к вершине .

Смешанный граф

Смешанный граф — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой , где ,   и определены так же, как выше.

Ориентированный и неориентированный  графы являются частными случаями смешанного.

Изоморфные графы

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

Прочие связанные  определения

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

Ориентированным путём в  орграфе называют конечную последовательность вершин , для которой все пары   являются (ориентированными) рёбрами.

Циклом называют путь, в  котором первая и последняя вершины  совпадают. При этом длиной пути (или  цикла) называют число составляющих его рёбер. Заметим, что если вершины  и  являются концами некоторого ребра, то согласно данному определению, последовательность является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

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

• всякий путь, соединяющий две вершины, содержит элементарный путь, соединяющий те же две вершины.
• всякий простой неэлементарный путь содержит элементарный цикл.
• всякий простой цикл, проходящий через некоторую вершину (или ребро), содержит элементарный (под-)цикл, проходящий через ту же вершину (или ребро).
• петля — элементарный цикл.

Бинарное отношение на множестве вершин графа, заданное как  «существует путь из в », является отношением эквивалентности и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.

Всякий максимальный связный  подграф графа G называется связной  компонентой (или просто компонентой) графа . Слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов

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

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

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

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

1. Для любых x, y и z из Γ справедливо (x·y)·z = x·(y·z);
2. В Γ существует единичный элемент e, такой что для любого x из Γ e·x = x·e = x;
3. Для любого элемента x из Γ существует обратный элемент также из множества Γ, такой что .

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

1. Бинарная операция не выводит за пределы подмножества 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. Подстановка (13)(2)(4) преобразует вершины 1 и 4 в вершины 3 и 4, и эти образы 3 и 4, также являются смежными. Таким образом, подстановка (13)(2)(4) сохраняет смежность вершин 1 и 4. Так как совокупность подстановок в этом списке замкнута относительно операции умножения, то она образует группу.

Теперь можем переходить к определению такого понятия, как  цикловой индекс группы подстановок.

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

Тогда цикловой индекс группы , обозначаемый  или , представляет собой многочлен от переменных , определяемый формулой: