ОГЛАВЛЕНИЕ

Тема. Комбинаторика......................................................................

3

Лекция 1. Введение в комбинаторику.

Некоторые области применения задач комбинаторики.

Перестановки и сочетания. ............................................................

3

Лекция 2. Биномиальные коэффициенты. Бином

Ньютона. Треугольник Паскаля.....................................................

5

Лекция 3.Разбиения множества. Числа Стирлинга

второго рода. Число Белла. Числа Стирлинга

первого рода. .....................................................................................

10

Лекция 4. Формулы включений и исключений............................

14

Лекция 5. Производящие функции. Основные

операции. Примеры использования..............................................

17

Лекция 6. Генерирование комбинаторных объектов.

Перестановки. Сочетания. Разбиение чисел.

Подмножества множеств............................................................

21

Тема. Алгоритмы на графах.........................................................

26

Лекция 7. Неориентированные графы: основные

понятия; маршруты, цепи, циклы; связность;

деревья и леса. ..................................................................................

26

Лекция 8. Ориентированные графы: основные понятия;

ориентированные маршруты, пути, контуры;

сильная связность; деревья. Метрические

характеристики графа. .................................................................

30

Лекция 9. Матричное представление графов: матрица

инциденций, матрица смежности вершин.

Список инцидентности.................................................................

33

Лекция 10. Построение покрывающих деревьев.

Алгоритм Краскала ........................................................................

37

Лекция 11. Поиск на графах:

алгоритмы поиска в глубину и в ширину.....................................

39

Лекция 12. Эйлеровы графы.

Алгоритм поиска эйлерова цикла в графе. ..................................

45

Лекция 13. Нахождение пути наименьшей длины в графе

Алгоритм Дейкстра. .....................................................................

50

Лекция 14. Нахождение расстояния между всеми

парами вершин. Алгоритм Уоршалла-Флойда.

Связность орграфов. Транзитивное замыкание.. .....................

54

Литература.......................................................................................

59

59