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

Таким образом, . Пусть переменная x отвечает белому цвету, а y — черному.

(2.1)

Это означает, что у нас  есть четыре графа с тремя вершинами: один граф без ребер, один с одним  ребром, один с двумя ребрами и один с тремя ребрами.

Пример. n = 4. Рассмотрим действие группы на . одночлен — .

• 2-цикл, например (1, 2)(3)(4), действует так: (1, 2) и (3, 4) неподвижны; (1, 3) → (2, 3) → (1, 3); (1, 4) →(2, 4)  → (1, 4). Соответствующий одночлен  —. Так как в шесть  2-циклов,  то  они  дают  в цикловый индекс вклад
• 3-цикл, например (1, 2, 3)(4), действует так: (1, 2) → (2, 3) → (1, 3) → (1, 2); (1, 4) → (2, 4) → (3, 4) →(1, 4). Соответствующий одночлен — . Так как в восемь 2-циклов, то они дают в цикловый индекс вклад 8.
• 4-цикл, например (1, 2, 3, 4), действует так: (1, 2) → (2, 3) → (3, 4) → (1, 4) → (1, 2); (1, 3) → (2, 4) →(1, 3). Соответствующий одночлен —. Так как в шесть 4-циклов, то они дают в цикловый индекс вклад.
• 2,2-цикл, например (1, 2)(3, 4), действует так: (1, 2) и (3, 4) неподвижны; (1, 3) → (2, 4) → (1, 3); (1, 4) →2, 3) → (1, 4). Соответствующий одночлен — . Так как в S4 три 2,2-цикла, то они дают в цикловый индекс вклад .

 

 

Пример. Пусть n = 4. Мы знаем, что . Имеется 5 разбиений числа 4: 4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1.

• Первое разбиение отвечает случаю связного графа — таких графов 6.
• Второе разбиение отвечает случаю двух компонент связности — с тремя вершинами и с одной вершиной. Таких графов 2.
• Третье разбиение отвечает случаю двух компонент связности — с двумя вершинами каждая. Такой граф один.
• Четвертое разбиение отвечает случаю трех компонент связности — одна с двумя вершинами и две с одной вершиной. Такой графов один.
• Пятое разбиение отвечает случаю четырех компонент связности — с одной вершиной каждая. Такой граф один.

Следовательно, = 11.

На языке производящих рядов эту конструкцию можно  описать так. Количество графов с n вершинами  равно коэффициенту при tn в произведении рядов

(1+ t + + +. . .) × (1+ + +. . .)×(1+++. . .)×. . .

Здесь коэффициент равен числу графов, состоящих из j связных компонент, причем каждая компонента имеет i вершин. Тоесть — это количество способов выбрать j связных графов из , причем в выборке могут быть и одинаковые графы.

Таким образом,

 

и i-й сомножитель в  произведении есть

 

Следовательно

 

Перейдем к логарифмам

 

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

 

Где

 

Здесь сумма берется по всем делителям числа n. Таким образом,

 

Правило перехода от достаточно простое. Действительно, продифференцируем это равенство. Имеем (2.10)

 

 

Теперь  сравниваем коэффициенты при :

 

Так как _, то мы получили рекуррентную формулу для вычисления чисел

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

Пусть множество   соответствует номерам бусинок в ожерелье, а   — множество возможных цветов. Весовую функцию положим равной  для всех  . Во множестве   имеется один элемент веса 0 и один — веса 1, то есть   и  . Откуда  .

Пусть   — множество всех функций из   в  . Любая функция   задает некоторое ожерелье и, наоборот, каждое ожерелье задаётся некоторой функцией из  . При этом вес функции равен количеству бусинок цвета 1 в соответствующем ожерелье.

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

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

,

где   — функция Эйлера,   — наибольший общий делитель чисел   и  .

По  теореме Редфилда-Пойа

Число орбит веса   (то есть различных ожерельев с   бусинками цвета 1) равно  , коэффициенту при   в  :

.

Общее число различных орбит (или ожерелий) равно

 

Заключение

 

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

Графами являются блок-схемы  программ для ЭВМ, сетевые графики  строительства. С помощью графов решается задача о назначении на должности.

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

В данной курсовая работе я изучила описание этого инструмента. Для осознания проблемы я рассмотрела перечисление помеченных графов, это наиболее простая задача из теории перечисления. Затем рассмотрела основные виды графов, понятие теории графов и теории групп, понятие эквивалентности, лемму Бернсайда (William Burnside) и, наконец, доказала теорему Пойа.

Итак, практический смысл теории перечисления графов состоит в том, чтобы подсчитать число графов определённого класса и оценить трудоёмкость задач, связанных  с перечислением выявленного  множества объектов. Теорема Пойа даёт нам механизм для проведения подобной оценки.

 

 

 

 

Список используемых источников

1. Burnside, William Theory of groups of finite order. — Cambridge University Press, 1897.
2. Diestel R. Graph Theory, Electronic Edition. — NY: Springer-Verlag, 2005.
3. Балашова Н.А., Кукин Г.П. Комбинаторика. Омск, 1992.
4. Басакер Р., Саати Т. Конечные графы и сети М., Наука, 1974
5. Белов В. В., Воробьев Е.М., Шаталов В.Е. Теория графов. М.: ВШ, 1976.
6. Березина Л.Ю. Графы и их применения: Пособие для учителей. – М., 1979
7. Берж К. Теория графов и ее приложения. М.: ИЛ, 1962.
8. Емеличев В.А. Лекции по теории графов. – М.: Наука, 1990.
9. Зелянин Р.В. Некоторые задачи перечисления графов — Сыктывкарский ГУ (сайт).
10. Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004.
11. Калужнин Л.А., СущанскийВ.И. Преобразования и перестановки – М.: Наука,1985
12. Камерон П., ван Линт Дж. Теория графов. Теория кодирования и блок-схемы. М.: Наука, 1980. 
13. Комбинаторная прикладная математика / Под ред. Э.Беккенбаха. — М.: Мир, 1968.
14. Комбинаторный анализ. Задачи и упражнения. – М.: Наука 1982
15. Кофман А.,  Фор Р. Займемся исследованием операций. М.: Мир, 1966
16. Кристофидес Н.Теория графов. Алгоритмический подход. М.: Мир, 1978.
17. Липский В. Комбинаторика для программистов: Пер. с польск. — М.: Мир, 1988.
18. Оре О. Графы и их применение. М., Мир, 1965.
19. Оре О. Теория графов. – М.: Наука, 1968.
20. Перечислительные задачи комбинаторного анализа / Сборник переводов под редакцией Г. П. Гаврилова. — М.: Мир, 1979.
21. Салий В. Н. Богомолов А. М. Алгебраические основы теории дискретных систем. — М.: Физико-математическая литература, 1997.
22. Татт У. Теория графов. Пер. с англ. М.: Мир, 1988.
23. Уилсон Р. Введение в теорию графов М.: Мир, 1977.
24. Харари Ф. Теория графов. – М.: Мир, 1973.
25. Харари Ф., Палмер Э. Перечисление графов: Пер. с. англ. — М.: Мир, 1977.
26. Яковенко Д. И. Задача об ожерельях // Вестник Омского университета. — 1998. — В. 2. — С. 21-24.