Графы и их применения

Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"

Курс читается в 1-м семестре магистратуры, 2 ч лекций, 1 ч семинаров

Лектор: Бухман Антон Владимирович

Программа курса

Часть 1. Теоретические основы

Лекция 1. Основные определения. Простейшие свойства графов. Деревья. Теоремы о свойствах деревьев. Остовные деревья.

Лекция 2. Число остовных деревьев. Остовные деревья с наибольшим числом висячих вершин. Коды Прюфера. Теорема Кэли.

Лекция 3. Вершинная раскраска графов. Теорема Брукса.

Лекция 4. Реберная раскраска мультиграфов. Оптимальные раскраски. Теорема Визинга.

Лекция 5. Числа Рамсея, введение в теорию Рамсея. Задача о многоугольниках.

Лекция 6. Критрий Эйлеровости. Достаточные условия Гамильтоновости.

Лекция 7. Теорема Форда-Фалкерсона и оптимальные потоки в сетях. О паросочетаниях и их связи с потоками.

Лекция 8. Теорема Менгера(формулировка). Основные элементы теории k-связности графов.

Часть 2. Алгоритмы

Лекция 9. Представления графа, оценка сложности, сложность простейших операций в разных моделях. Поиск в глубину, ширину. Обоснование сложности и корректности.

Лекция 10. Построение множества фундаментальных циклов. Построение компонент двусвязности.

Лекция 11. Построение минимальных остовов. Алгоритм Краскала, алгоритм Прима.

Лекция 12. Задача Коммивояжера. Её вариации. Сложность решения. Понятие приближённого алгоритма на примере задачи Коммивояжёра.

Лекция 13. Понятие переборного алгоритма. Как оценивать качество переборного алгоритма. Переборный алгоритм построения всех остовных деревьев данного графа. Граф остовов и его свойства.

Часть 3. Дополнительные вопросы теории графов

Лекция 14. Теорема Турана. Наследственные свойства графов.

Лекция 15. Сложность задачи раскраска графа.

Лекция 16. Введение в теорию матроидов.

Программа семинарских занятий

Семинар 1. Остовные деревья. Коды Прюфера.

Семинар 2. Раскраска графов.

Семинар 3. Теори Рамсея, эйлеровы и гамильтоновы графы.

Семинар 4. Теорема Форда-Фалкерсона.

Семинар 5. Фундаментальные циклы и компоненты двусвязности.

Семинар 6. Минимальные остовные деревья.

Семинар 7. NP-полные задачи награфах.

Семинар 8. Переборные алгоритмы на графах.

Литература

1. Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
2. Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд. отд. ф-та ВМК МГУ имени М.В. Ломоносова, 2002.
3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
5. Карпов Д.В. Теория графов.
6. Липский В. Комбинаторика для программистов. М.: Мир, 1988.
7. Оре О. Теория графов. М.: Наука, 1980.
8. Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.
9. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.
10. Харари Ф. Теория графов. М.: Мир, 1973.
11. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.