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

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

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

20
Решение задач о перечислении графов с помощью теоремы Пойа………………………………………………………………

20
Заключение…………………………………………………………...........
26
Список используемых источников……………………………………….
28