Графы и алгоритмы

: Информация
Опубликована: 05.04.2011 | Уровень: для всех | Стоимость: 3000.00 руб. | Длительность: 14 дней
Курс посвящен алгоритмам на графах. Приводятся базовые понятия и факты из теории графов и излагаются некоторые алгоритмы для решения задач на графах.
Основной принцип отбора и организации материала состоял в том, что каждый рассматриваемый пример должен нести определенную идейную нагрузку, знакомить слушателя с одним из важных изобретений или открытий в алгоритмической области. При этом предпочтение отдавалось не самым последним или рекордным алгоритмам, а более простым для понимания и убедительно демонстрирующим ту или иную идею. Для большинства рассматриваемых алгоритмов даются доказательства их правильности (т.е. того, что алгоритм действительно решает поставленную задачу) и оценок трудоемкости. Умение достаточно строго обосновывать алгоритмы и оценивать их трудоемкость является существенной частью квалификации алгоритмиста. Материал первой части может быть использован и в общем курсе дискретной математики.

План занятий

ЗанятиеЗаголовок <<Дата изучения
-
Лекция 1
1 час 17 минут
Начальные понятия теории графов
Начальные понятия теории графов. Определение графа. Графы и бинарные отношения. Откуда берутся графы. Число графов. Смежность, инцидентность, степени. Некоторые специальные графы. Графы и матрицы. Взвешенные графы. Изоморфизм. Инварианты. Операции над графами. Локальные операции. Подграфы. Алгебраические операции.
-
Тест 1
12 минут
-
Лекция 2
43 минуты
Маршруты, связность, расстояния
Маршруты, пути, циклы. Связность и компоненты. Метрические характеристики графов. Маршруты и связность в орграфах. Эйлеровы пути и циклы.
-
Тест 2
12 минут
-
Лекция 3
1 час 5 минут
Важнейшие классы графов
Деревья. Центр дерева. Корневые деревья. Каркасы. Двудольные графы. Планарные графы.
-
Тест 3
15 минут
-
Лекция 4
38 минут
Поиск в ширину
Поиск в ширину. Процедура поиска в ширину. BFS-дерево и вычисление расстояний.
-
Тест 4
9 минут
-
Лекция 5
43 минуты
Поиск в глубину
Процедура поиска в глубину. DFS-дерево. Глубинная нумерация. Построение каркаса. Шарниры.
-
Тест 5
9 минут
-
Лекция 6
45 минут
Блоки
Блоки. Двусвязность. Блоки и BC-дерево. Выявление блоков.
-
Лекция 7
44 минуты
Пространство циклов графа
Пространство подграфов. Квазициклы. Фундаментальные циклы. Построение базы циклов. Рационализация.
-
Тест 6
15 минут
-
Лекция 8
38 минут
Эйлеровы и гамильтоновы циклы
Построение эйлерова цикла. Гамильтоновы пути и циклы.
-
Лекция 9
49 минут
Независимые множества, клики, вершинные покрытия.
Независимые множества, клики, вершинные покрытия . Три задачи. Стратегия перебора для задачи о независимом множестве. Эвристики для задачи о независимом множестве. Приближенный алгоритм для задачи о вершинном покрытии. Перебор максимальных независимых множеств.
-
Тест 7
15 минут
-
Лекция 10
35 минут
Раскраски
Раскраска вершин. Переборный алгоритм для раскраски. Раскраска ребер.
-
Лекция 11
35 минут
Рационализация переборных алгоритмов
Рационализация поиска наибольшего независимого множества. Хордальные графы. Рационализация алгоритма для задачи о раскраске вершин.
-
Тест 8
12 минут
-
Лекция 12
57 минут
Паросочетания
Паросочетания и реберные покрытия. Метод увеличивающих путей. Паросочетания в двудольных графах. Паросочетания в произвольных графах (алгоритм Эдмондса).
-
Лекция 13
28 минут
Оптимальные каркасы
Задача об оптимальном каркасе. Алгоритм Прима. Алгоритм Крускала.
-
Тест 9
15 минут
-
Лекция 14
40 минут
-
Лекция 15
21 минута
Кратчайшие пути
В этой лекции рассматриваются связные графы с неотрицательными весами ребер. А также кратчайшие пути, геодезическое дерево и алгоритм Дейкстры.
-
Лекция 16
35 минут
Потоки
В этой лекции будем рассматривать ориентированные графы без петель и кратных ребер: задачу о максимальном потоке и метод увеличивающих путей.
-
Тест 10
18 минут
-
5 часов
-