13. Производящие функции в теории графов.

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

1) Изучить такие основополагающие понятия теории графов, как граф, маршрут, цикл и дерево (/1/, с. 9-43; /2/, с. 5-22).

2) Рассмотреть определение производящей функции и доказать основные свойства таких функций (/2/, с. 226-231; /3/, с. 64-72; /4/, с. 24-30).

3) Разобрать решение задачи перечисления корневых деревьев с помощью производящих функций (/1/, с. 236-238).

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

1 Уилсон Р. Введение в теорию графов. – М.: Мир, 1977. 2 Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. – М.: ВШ,

1976.

3 Липский В. Комбинаторика для программистов. – М.: Мир, 1988.

4 Комбинаторный анализ. Задачи и упражнения. – М.: Наука, 1982.