Тема 61. Теорема Пойа и перечисление графов
Решение многих задач перечисления графов сводится к подсчету числа классов эквивалентностей. Эффективный метод решения таких задач базируется на известной теореме Пойа. Цель курсовой работы – изучить основные свойства групп подстановок и метод решения комбинаторных задач теории графов с помощью теоремы Пойа. Рекомендуется следующий план работы.
1 Изучить такие основополагающие понятия теории графов и теории групп, как граф, группа подстановок и ее цикловой индекс (/2/, с. 9-18; 239-243; /3/, с. 21-26, 194; /4/, с. 50-63).
2 Рассмотреть определение эквивалентности, порождаемой группой подстановок, и доказать лемму Бернсайда о числе классов такой эквивалентности (/2/, с. 245-248; /4/, с. 81-85).
3 Разобрать определение перечня конфигурации и доказать теорему Пойа (/2/, с. 248-259; /3/, с. 211-216).
4 Рассмотреть задачу о перечислении графов и метод ее решения с помощью теоремы Пойа (/2/, с. 262-270; /3/, с. 216-224).
Разобрать все примеры из указанных выше литературных источников и решить задачи 10a, 10c из /1/, 15.1, 15.2 из /3/ и 2.100-2.102, 2.120 из /5/.
Литература, рекомендуемая для изучения темы
1Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.
2Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: ВШ,
1976.
3Харари Ф. Теория графов. – М.: Мир, 1973.
4Калужнин Л.А., Сущанский В.И. Преобразования и перестановки. –
М.: Наука, 1985.
5Комбинаторный анализ. Задачи и упражнения. – М.: Наука, 1982.
- 1 АЛГЕБРА И ТЕОРИЯ ЧИСЕЛ
- Тема 1. Алгебра бинарных отношений и отображений
- Тема 2. Отображения и фактор-множества
- Тема 10. Основная теорема алгебры
- Тема 18. Замыкания и соответствия Галуа
- Тема 19. Функция Мёбиуса и её свойства
- Тема 28. Греко-китайская теорема об остатках
- Тема 33. Силовские подгруппы
- 2 МАТЕМАТИЧЕСКАЯ ЛОГИКА
- Тема 34. Логическая игра
- Тема 35. Неразрешимость логики первого порядка
- 3 ДИСКРЕТНАЯ МАТЕМАТИКА
- Тема 47. Эйлеровы графы
- Тема 48. Гамильтоновы графы
- Тема 55. Раскраски графов
- Тема 61. Теорема Пойа и перечисление графов
- Тема 62. Графы на двумерных поверхностях
- Тема 68. Логика на словах
- Тема 75. Элементы теории конечных автоматов
- Тема 82. Модулярные и дистрибутивные решетки
- Тема 83. Булевы алгебры
- 4 РАЗЛИЧНЫЕ РАЗДЕЛЫ МАТЕМАТИКИ
- Тема 86. Элементы линейного программирования
- Тема 95. Барицентрическое исчисление
- Приложение А