Тема 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.