Лекция 9. Информационная лекция

Теоремы о маршрутах и циклах (продолжение). Алгоритмы Дейкстры и Беллмана-Мура, алгоритм вычисления максимального по весу пути. Маршруты и пути (продолжение). Дерево (ордерево). Корневые, бинарные деревья. Теоремы о деревьях. Обходы графов. Эйлеровы и гамильтоновы циклы. Алгоритм Флери.

Лекция 10. Проблемная лекция.

Фундаментальные циклы. Матрица фундаментальных циклов. Решение экстремальных задач теории графов (экстремальные остовы). Алгоритм ближайшего соседа построения остова дерева.

Аудиторный практикум - 8 часов, 4 практических занятия.

Практические занятия №8-9.

Решение задач на способы задания графов по матрицам смежности вершин, смежности рёбер и инциденций. Нахождение маршрутов, состоящих из фиксированного количества ребер. Упорядочение дуг и вершин орграфа, алгоритм Фалкерсона. Алгоритм Дейкстры.

Практические занятия № 10-11.

Задачи на вычисление максимального пути, алгоритм Беллмана-Мура, построение минимального остова графа. Эйлеровы и гамильтоновы циклы. Алгоритм Флери. Алгоритм Прима построения остова дерева. Вычисление клик ордерава, построение матрицы клик. Вычисление числовых характеристик деревьев.

Управление самостоятельной работой студента - 12 часов.

Отношения между элементами графа (орграфа). Способы задания. Степень вершины. Изоморфизм. Связность. Теоремы о маршрутах и циклах. Определение экстремальных путей на графах. Выявление маршрутов с заданным количеством ребер. Метод Шимбелла. Алгоритмы Дейкстры и Беллмана - Мура построения кратчайшего пути. Задача о нахождении максимального пути на ациклических графах. Обходы графов. Фундаментальные циклы. Остовный граф. Задача об остове минимального веса. Алгоритм Прима расчета кратчайшего остова.

Раздел 4.Планарные и хроматические графы.

Теоретические занятия (лекции) - 6 часов.

Лекция 11. Информационная лекция.

Планарные и хроматические графы. Число планарности и хроматическое число и их оценки. Алгоритм укладки графа на плоскости. Раскраски графов.

Лекция 12. Проблемная лекция.

Теорема о четырех красках и история её доказательства. Рассмотрение и доказательство теоремы о пяти красках.

Аудиторный практикум - 6 часов, 3 практических занятия.