Графы и их применения — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Объявления)
Строка 1: Строка 1:
 
Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"
 
Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"
  
Курс читается в 1-м семестре магистратуры, 2 ч лекций, 1 ч семинаров
+
Курс читается в 1-м семестре магистратуры, 1 ч лекций, 1 ч семинаров
  
Лекторы: [[Селезнева Светлана Николаевна]], [[Бухман Антон Владимирович]]
+
Лектор: [[Бухман Антон Владимирович]]
 
+
==Объявления==
+
 
+
[[Media:gip.pdf|'''Вопросы к экзамену''']]
+
 
+
Занятия проходят по средам в 9 ч, ауд. 503.
+
 
+
2 октября занятие переносится на 3 октября.
+
  
 
==Программа курса==
 
==Программа курса==
Строка 36: Строка 28:
  
 
'''Лекция 11'''. Изоморфизм графов. Полиномиальный алгоритм проверки изоморфизма деревьев. Построение выпуклого n-угольника на достаточно большом множестве точек.
 
'''Лекция 11'''. Изоморфизм графов. Полиномиальный алгоритм проверки изоморфизма деревьев. Построение выпуклого n-угольника на достаточно большом множестве точек.
 
==Программа семинарских занятий==
 
 
'''Семинар 1'''. Простейшие свойства графов (повторение).
 
[5] Гл. 6: 1.3, 1.4, 1.5, 1.13, 1.16, 1.21, 1.22, 1.27, 1.28, 1.29, 1.31, 3.10, 3.14, задачи лекции 1.
 
 
'''Семинар 2'''. Связность, двусвязность графов. Остовные деревья.
 
[5] Гл. 6: 1.24, 1.17, 3.15, задачи лекций 2 и 3.
 
 
'''Семинар 3'''. Раскраски графов. Хроматическое число и хроматический индекс графа.
 
[5] Гл. 6: 2.18, 2.19, 2.20, 2.21, задачи лекций 4 и 5. 
 
 
'''Семинар 4'''. Наследственные свойства графов. Числа Рамсея.
 
[5] Гл. 6: 2.7, 2.8, 2.9, 2.10, 2.13, 2.17, задачи лекций 6 и 7.
 
  
 
==Литература==
 
==Литература==

Версия 00:32, 3 апреля 2022

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

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

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

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

Лекция 1. Числа Рамсея. Верхняя и нижняя оценки.

Лекция 2. Обобщение чисел Рамсея. Примеры их использования.

Лекция 3. Теоремы о раскрасках графа.

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

Лекция 5. Алгоритмы поиска кратчайшего остовного дерева. Матроиды и жадные алгоритмы. Теорема Радо-Эдмонса.

Лекция 6. Потоки в сетях. Максимальный поток в сети. Теорема Форда-Фалкерсона о величине максимального потока в сети. Алгоритмы отыскания максимального потока в сети.

Лекция 7. Паросочетания в графах. Теорема Холла. Паросочетания в двудольных графах. Алгоритм отыскания наибольшего паросочетания двудольного графа на основе построения максимального потока в сети.

Лекция 8. Паросочетания в графах. Теорема Куна. Теорема Эдмонса. Алгоритмы отыскания наибольших паросочетаний в двудольных графах и в произвольных графах.

Лекция 9. Эйлеровы пути и циклы в графах. Критерий эйлеровости графа. Задача китайского почтальона. Гамильтоновы пути и циклы в графах. Достаточные условия гамильтоновости графа.

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

Лекция 11. Изоморфизм графов. Полиномиальный алгоритм проверки изоморфизма деревьев. Построение выпуклого n-угольника на достаточно большом множестве точек.

Литература

Основная:

1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009.

2. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.

3. Харари Ф. Теория графов. М.: Мир, 1973.

4. Липский В. Комбинаторика для программистов. М.: Мир, 1988.

5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.

Дополнительная:

6. Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.

7. Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел ф-та ВМК МГУ имени М.В. Ломоносова, 2002.

8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

9. Оре О. Теория графов. М.: Наука, 1980.

10. Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.

11. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.

12. Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического ф-та МГУ имени М.В. Ломоносова, 2007.

13. Diestel R. Graph Theory. Springer, 2010.