Календарный план учебных занятий по дисциплине «Теория графов», привязанной к первому семестру второго курса. Лектор – старший преп. Р

КАЛЕНДАРНЫЙ ПЛАН

учебных занятий по дисциплине «Теория графов», привязанной к первому семестру второго курса. Лектор – старший преп.

Виды и содержание учебных занятий
Неделя	Лекции	Число часов	Лабораторные занятия	Число часов
1	Неориентированные графы. Основные понятия. Маршруты, цепи, циклы.	2	Нахождение матриц смежности и инцидентности, матрицы весов для неорграфов.	2
2	Ориентированные графы. Ормаршруты, цепи.	2	Нахождение матриц смежности и инцидентности, матрицы весов для орграфов.	2
3	Теорема о связности графа. Деревья, леса.	2	Построение покрывающего дерева для графа.	2
4	Изоморфизм графов.	2	Построение неизоморфных графов. Частные случаи.	2
5	Метрические характеристики графа. Эксцентриситет, радиус, диаметр графа.	2	Решение задач на нахождение метрических характеристик графа.	2
6	Алгоритм поиска с возвращением.	2	Решение задач на обход вершин графа в ширину и в глубину.	2
7	Промежуточный контроль знаний (Контрольная работа № 1)	2
8	Алгоритм Краскала.	2	Построение минимального и максимального покрывающего дерева для графа по алгоритму Краскала.	2
9	Алгоритм Прима.	2	Построение минимального и максимального покрывающего дерева для графа по алгоритму Прима.	2
10	Алгоритм Дейкстры.	2	Поиск кратчайшего пути по алгоритму Дейкстры.	2
11, 12	Эйлеровы графы. Алгоритм поиска Эйлерова цикла в графе.	4	Нахождение эйлерова цикла в графе.	4
13	Алгоритм Уоршалла-Флойда.	2	Решение задач на алгоритм Уоршалла-Флойда.	2
14	Промежуточный контроль знаний (Контрольная работа № 2)	2
15	Задача о максимальном потоке.	2	Решение задачи о максимальном потоке.	2
16	Алгоритм поиска увеличивающейся цепи.	2	Разбор задач на алгоритм поиска увеличивающейся цепи.	2
17	Гамильтоновы циклы.	2	Решение задач на гамильтоновы циклы.	2
18,19	Заключительный обзор курса. Консультации по подготовке к итоговому контролю знаний.	4	Заключительный обзор курса. Консультации.	4
20	Итоговый контроль знаний - экзамен (Контрольная работа № 3)

Зав. кафедрой систем телекоммуникаций, д. т.н., проф.