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

Решение многих задач перечисления графов сводится к подсчету числа

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

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

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).

Литература, рекомендуемая для изучения темы