Введение 3
Глава 1. Числа Каталана 4
1.1. Числа Каталана 4
1.2. Треугольник Каталана 9
1.3. Бинарное дерево 12
1.4. Каталановские числа и разбиения многоугольника 16
Глава 2. Обходы ориентированных графов 24
2.1. Основные определения 24
2.2. Представления ориентированных графов 27
2.3. Нахождение центра ориентированного графа 30
2.4. Обход ориентированных графов 32
2.5. Центр графа 34
2.7. Десятичная кодировка 39
2.8. Кодировка Прюфера 42
2.9. Распаковка кода Прюфера 42
Глава 3. Практическая часть 47
Заключение 57
Литература 58
Цель выпускной квалификационной работы состоит в изучении свойств производящих функций и применении их в комбинаторных задачах перечисления некоторых объектов, в частности, чисел Каталана и связанных с ними обходов ориентированных графов.
Как известно, метод производящих функций является наиболее эффективным аппаратом решения многих перечислительных комбинаторных задач. В таких задачах речь идет о нахождении числа тех или иных конфигураций, которые можно составить из элементов некоторого конечного множества.
Для достижения цели поставлены следующие задачи:
1. Рассмотреть решения некоторых задач обхода графов.
2. Ознакомиться с различными объяснениями числа Каталана.
3. Разработать алгоритмы решения некоторых комбинаторно-графовых задач и проверить их решение с помощью пакета Maple.
Выпускная квалификационная работа состоит из введения, трёх глав, заключения и списка использованной литературы.
В квалификационной работе изучены свойства производящих функций. С их помощью были выведены общие формулы для вычисления чисел Каталана, а также рассмотрены различные обходы ориентированных графов и вычислительные алгоритмы подсчёта некоторых важных характеристик графов специального вида (плоские деревья Каталана).
Решены примеры на вычисление чисел Каталана и характеристических величин ориентированных графов. Вычисления проверены с помощью программного пакета Maple.
Многие задачи, рассмотренные в работе, встречались на различных олимпиадах и турнирах по математике и программированию. Эти задачи отличаются простотой и оригинальностью формулировок, их можно использовать в работе тренеров и учителей школ при подготовке учеников к математическим олимпиадам.
