Лекции по дискретной математике. Ч.II. Комбинаторика, разостные уравнения, алгоритмы на графах. Гайдамака Ю.В - 59 стр.

UptoLike

59
ОГЛАВЛЕНИЕ
Тема. Комбинаторика ......................................................................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