Дискретная математика: графы и алгоритмы на графах

ОмГТУ, 2010. – 120 с.Основные понятия теории графов.Граф и его разновидности.Морфизмы графов.Степени вершин.Маршруты, цепи, циклы, связность.Операции над графами.Примеры графов.Метрические характеристики графов.Представления графов.Алгоритмы и сложность.Понятие алгоритма.Сложность алгоритма.Запись алгоритма.Обходы графов.Поиск в глубину на графе.Поиск в ширину на графе.Алгоритм выделения компонент связности.Деревья.Деревья. Свойства деревьев.Остовы. Теорема Кирхгофа.Теорема Кэли.Фундаментальная система циклов. Цикломатическое число.Алгоритм отыскания фундаментального множества циклов на графе.Остов минимального веса. Алгоритм Краскала и Прима.Алгоритм Д. Краскала.Алгоритм Р. Прима.Кратчайшие пути между вершинами графа.Алгоритм Дейкстры.Алгоритм Флойда.Эйлеровы графы.Теорема Эйлера. Алгоритм Флёри.Гамильтоновы графы.Гамильтоновы маршруты. Задача коммивояжера.Существование гамильтоновых маршрутов.