Степанов В.Н. Дискретная математика: графы и алгоритмы на графах

ОмГТУ, 2010. – 120 с.

Основные понятия теории графов.
Граф и его разновидности.
Морфизмы графов.
Степени вершин.
Маршруты, цепи, циклы, связность.
Операции над графами.
Примеры графов.
Метрические характеристики графов.
Представления графов.

Алгоритмы и сложность.
Понятие алгоритма.
Сложность алгоритма.
Запись алгоритма.

Обходы графов.
Поиск в глубину на графе.
Поиск в ширину на графе.
Алгоритм выделения компонент связности.

Деревья.
Деревья. Свойства деревьев.
Остовы. Теорема Кирхгофа.
Теорема Кэли.
Фундаментальная система циклов. Цикломатическое число.
Алгоритм отыскания фундаментального множества циклов на графе.

Остов минимального веса. Алгоритм Краскала и Прима.
Алгоритм Д. Краскала.
Алгоритм Р. Прима.

Кратчайшие пути между вершинами графа.
Алгоритм Дейкстры.
Алгоритм Флойда.

Эйлеровы графы.
Теорема Эйлера.
Алгоритм Флёри.

Гамильтоновы графы.
Гамильтоновы маршруты. Задача коммивояжера.
Существование гамильтоновых маршрутов.