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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
м (→‎Программа курса: Исправил расписание по программу "1 раз в неделю")
м
 
(не показаны 12 промежуточные версии 2 участников)
Строка 1: Строка 1:
 +
[[Категория:Спецкурсы кафедры МК]]
 +
[[Категория:Лекционные курсы кафедры МК]]
 +
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]
 +
 
Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"
 
Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"
  
−
Курс читается в 1-м семестре магистратуры, 2 ч лекций, 1 ч семинаров
+
Курс читается в 1-м семестре магистратуры, 1 ч лекций, 1 ч семинаров
  
−
Лекторы: [[Селезнева Светлана Николаевна]], [[Бухман Антон Владимирович]]
+
Лектор: [[Бухман Антон Владимирович]]
  
−
==Объявления==
 
  
−
[[Media:gip.pdf|'''Вопросы к экзамену''']]
+
== Программа курса Графы и их применения. ==
  
−
Экзамен для аспирантов состоится 8 января (в понедельник) в 9 ч в ауд. 503.
 
  
−
Экзамен для студентов 518/1 группы состоится по расписанию экзаменов.
+
'''Занятие 1.
 +
1. Введение. Обзор курса. - 20 минут
 +
2. Семинар. Задачи на повторение курса по графам.
  
−
==Программа курса==
+
'''Занятие 2.
 +
1. Семинар. Задачи на повторение -- продолжение.
 +
2. Лекция. Алгоритмы на графах. Алгоритмическая модель. Сложность. Представление графов.
  
−
'''Лекция 1'''. Числа Рамсея. Верхняя и нижняя оценки.
+
'''Занятие 3.
 +
1. Обходы графов.
 +
2. Поиск компонент вершинной двусвязности.
 +
3. Разбор задач на двусвязность.
  
−
'''Лекция 2'''. Обобщение чисел Рамсея. Примеры их использования.
+
'''Занятие 4.
 +
1. Поиск множества фундаментальных циклов
 +
2. Поиск компонент сильной связности.  
  
−
'''Лекция 3'''. Теоремы о раскрасках графа.
+
'''Занятие 5.
 +
1. Матроиды и жадные алгоритмы.
 +
2. Минимальные остовные деревья. Алгоритмы Краскала, Прима.
  
−
'''Лекция 4'''. Поиск в глубину и поиск в ширину в графе. Нахождение остовного дерева графа поиском в глубину и поиском в ширину. Отыскание фундаментального множества циклов в графе. Критерий разделяющей вершины на основе поиска в глубину. Нахождение компонент двусвязности графа.
+
'''Занятие 6.
 +
1. Переборные алгоритмы для построения всех остовных деревьев.
 +
2. Коды Прюфера. Число остовных деревьев для полного графа
  
−
'''Лекция 5'''. Алгоритмы поиска кратчайшего остовного дерева. Матроиды и жадные алгоритмы. Теорема Радо-Эдмонса.
+
'''Занятие 7.
 +
1. Числа Рамсея. Оценка чисел Рамсея.
 +
2. Обобщение чисел Рамсея. Применение чисел Рамсея.
  
−
'''Лекция 6'''. Потоки в сетях. Максимальный поток в сети. Теорема Форда-Фалкерсона о величине максимального потока в сети. Алгоритмы отыскания максимального потока в сети.
+
'''Занятие 8.
 +
1. Паросочетания теорема Холла
 +
2. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат.
  
−
'''Лекция 7'''. Паросочетания в графах. Теорема Холла. Паросочетания в двудольных графах. Алгоритм отыскания наибольшего паросочетания двудольного графа на основе построения максимального потока в сети.
+
'''Занятие 9.
 +
1. Семинар по пройденным темам.
  
−
'''Лекция 8'''. Паросочетания в графах. Теорема Куна. Теорема Эдмонса. Алгоритмы отыскания наибольших паросочетаний в двудольных графах и в произвольных графах.  
+
'''Занятие 10.
 +
1. Алгоритм Куна для поиска максимальных паросочетаний
 +
2. Вершинное покрытие двудольного графа. Взвешенные паросочетания.
 +
3. Венгерский алгоритм.
  
−
'''Лекция 9'''. Эйлеровы пути и циклы в графах. Критерий эйлеровости графа. Задача китайского почтальона. Гамильтоновы пути и циклы в графах. Достаточные условия гамильтоновости графа.
+
'''Занятие 11.
 +
1. Гамильтонов цикл. Достаточные признаки гамильтоновости графа.
 +
2. Задача коммивояжёра. ЗКНТ.
 +
2. Эйлеров цикл. Задача китайского почтальона.
  
−
'''Лекция 10'''. Гамильтоновы циклы в графах. Задача коммивояжера с неравенством треугольника и без него. Приближенные алгоритмы. Переборные алгоритмы, дерево решений. Алгоритм перебора всех остовных деревьев графа.
+
'''Занятие 12.
 +
1. Последовательности деБрёйна.
 +
2. Теорема о числе последовательностей.
  
−
'''Лекция 11'''. Изоморфизм графов. Полиномиальный алгоритм проверки изоморфизма деревьев. Построение выпуклого n-угольника на достаточно большом множестве точек.
+
'''Занятие 13.
 +
1. Некоторые NP полные задачи на графах.
 +
2. Обзор пройденного материала.
  
−
==Программа семинарских занятий==
+
'''Занятие 14.
 +
Семинар по пройденным темам.
  
−
'''Семинар 1'''. Простейшие свойства графов (повторение).
+
'''Занятие 15.
−
[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.
+
  
−
==Литература==
+
1. Точка сочленения, компонента двусвязности. Необходимое и достаточное условия для точки сочленения. Алгоритм поиска точек сочленения и компонент двусвязности.
 +
''В. Липский Комбинаторика для программистов. Раздел 2.6 Нахождение компонент двусвязности. С. 95-99''
  
−
'''Основная''':
+
2. Множество фундаментальных циклов. Теорема о построении множества фундаментальных циклов. Алгоритм построения множества фундаментальных циклов.
 +
''В. Липский. Комбинаторика для программистов. Раздел 2.5 Отысканиефундаментального множества циклов. С. 92-95''
  
−
1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009.
+
3. Компонента сильной связности. Линейный алгоритм построения компонент сильной связности.
 +
''Кормен и др. Алгоритмы построение и анализ. Раздел 23.1.5 Сильно связные компоненты. С. 473 - 477''
  
−
2. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.
+
4. Матроиды определения, свойства. Примеры матроидов (универсальный, матричный, графовый, матроид трансверсалей) с обоснование.
 +
''Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 341-343''
  
−
3. Харари Ф. Теория графов. М.: Мир, 1973.
+
5. Матроиды и жадные алгоритмы
 +
''Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 343-345''
  
−
4. Липский В. Комбинаторика для программистов. М.: Мир, 1988.
+
6. Минимальные остовные деревья. Алгоритм Краскала и Прима.
 +
''Кормен и др. Алгоритмы построение и анализ. Раздел 24 С. 482-490''
  
−
5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
+
7. Переборные алгоритмы для построения всех остовных деревьев.
 +
''Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 148-158
 +
''
  
−
'''Дополнительная''':
+
8. Числа Рамсея
 +
''Карпов. Теория графов. С. 477-479''
  
−
6. Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
+
9. Оценки чисел Рамсея
 +
''Карпов. Теория графов С. 479-481''
  
−
7. Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Издательский отдел ф-та ВМК МГУ имени М.В. Ломоносова, 2002.
+
10. Обобщение чисел Рамсея
 +
''Карпов. Теория графов С. 482-484''
  
−
8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
+
11. Паросочетания, теорема Холла.
 +
''А. Эвнин Вокруг теоремы Холла С.5-6''
  
−
9. Оре О. Теория графов. М.: Наука, 1980.
+
12. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат.
 +
''А. Эвнин Вокруг теоремы Холла С. 7,18''
  
−
10. Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.  
+
13. Лемма Бержа. Алгоритм Куна для поиска максимальных паросочетаний
 +
''Claude Berge. Two theorems in graph theory // Proceedings of the National Academy of Sciences of the United States of America. — 1957. — September 15 (т. 43, вып. 9). — С. 842–844. — doi:10.1073/pnas.43.9.842
 +
Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97.  
 +
C 83-87''
  
−
11. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.  
+
14. Венгерский алгоритм. Покрытие единиц матрицы строками и столбцами
 +
''Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97.
 +
C 887-91''
  
−
12. Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического ф-та МГУ имени М.В. Ломоносова, 2007.
+
15. Последовательность де Брёйна. Оценка числа последовательностей деБрёйна.
 +
''de Bruijn N. G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. — v. 49. — pp. 758—764''
 +
16. Задача коммивояжёра и ЗКНТ.
 +
''Гэри, Джонсон Вычислительные машины и труднорешаемые задачи
 +
С 189-190''
  
−
13. Diestel R. Graph Theory. Springer, 2010.
+
17. Достаточные признаки гамильтоновости графа.
−
 
+
  
−
[[Категория:Лекционные курсы кафедры МК]]
+
''R.Diestel Graph Theory. Springer 2000, C 213-216''
−
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]
+
 
 +
18. Эйлеровы графы и задача китайского почтальона.
 +
''Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 227-239''
 +
 
 +
== Список литературы ==
 +
 
 +
 
 +
В. Липский Комбинаторика для программистов. М.Мир, 1988
 +
 
 +
Кормен и др. Алгоритмы построение и анализ. Третье издание. Вильямс, 2013
 +
 
 +
Кристофидес Теория графов - Алгоритмический подход. М.Мир 1978
 +
 
 +
Д.В. Карпов Теория графов. https://logic.pdmi.ras.ru/~dvk/graphs_dk.pdf
 +
 
 +
А. Ю. Эвнин, Вокруг теоремы Холла, Матем. обр., 2005, выпуск 3(34), 2–23
 +
 
 +
Гери Джонсон Вычислительные машины и труднорешаемые задачи
 +
 
 +
== Темы задач ==
 +
 
 +
1. Поиск компонент двусвязности
 +
 
 +
2. Множество фундаментальных циклов
 +
 
 +
3. Компоненты сильной связности
 +
 
 +
4. Коды Прюфера
 +
 
 +
5. Алгоритм Куна.
 +
 
 +
6. Венгерский алгоритм
 +
 
 +
7. Покрытие матрицы
 +
 
 +
8. Задача китайского почтальона
 +
 
 +
9. Задача коммивояжёра, МВГ
 +
 
 +
10. Задачи на теорему Холла
 +
 
 +
11. Гамильтоновость
 +
 
 +
12. Теория Рамсея
 +
 
 +
13. Задачи теории сложности на графах
 +
 
 +
14. Матроиды, жадные алгоритмы

Текущая версия на 23:11, 7 октября 2024


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

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

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


Программа курса Графы и их применения.

Занятие 1. 1. Введение. Обзор курса. - 20 минут 2. Семинар. Задачи на повторение курса по графам.

Занятие 2. 1. Семинар. Задачи на повторение -- продолжение. 2. Лекция. Алгоритмы на графах. Алгоритмическая модель. Сложность. Представление графов.

Занятие 3. 1. Обходы графов. 2. Поиск компонент вершинной двусвязности. 3. Разбор задач на двусвязность.

Занятие 4. 1. Поиск множества фундаментальных циклов 2. Поиск компонент сильной связности.

Занятие 5. 1. Матроиды и жадные алгоритмы. 2. Минимальные остовные деревья. Алгоритмы Краскала, Прима.

Занятие 6. 1. Переборные алгоритмы для построения всех остовных деревьев. 2. Коды Прюфера. Число остовных деревьев для полного графа

Занятие 7. 1. Числа Рамсея. Оценка чисел Рамсея. 2. Обобщение чисел Рамсея. Применение чисел Рамсея.

Занятие 8. 1. Паросочетания теорема Холла 2. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат.

Занятие 9. 1. Семинар по пройденным темам.

Занятие 10. 1. Алгоритм Куна для поиска максимальных паросочетаний 2. Вершинное покрытие двудольного графа. Взвешенные паросочетания. 3. Венгерский алгоритм.

Занятие 11. 1. Гамильтонов цикл. Достаточные признаки гамильтоновости графа. 2. Задача коммивояжёра. ЗКНТ. 2. Эйлеров цикл. Задача китайского почтальона.

Занятие 12. 1. Последовательности деБрёйна. 2. Теорема о числе последовательностей.

Занятие 13. 1. Некоторые NP полные задачи на графах. 2. Обзор пройденного материала.

Занятие 14. Семинар по пройденным темам.

Занятие 15. Итоговая контрольная работа по курсу


Вопросы к экзамену

1. Точка сочленения, компонента двусвязности. Необходимое и достаточное условия для точки сочленения. Алгоритм поиска точек сочленения и компонент двусвязности. В. Липский Комбинаторика для программистов. Раздел 2.6 Нахождение компонент двусвязности. С. 95-99

2. Множество фундаментальных циклов. Теорема о построении множества фундаментальных циклов. Алгоритм построения множества фундаментальных циклов. В. Липский. Комбинаторика для программистов. Раздел 2.5 Отысканиефундаментального множества циклов. С. 92-95

3. Компонента сильной связности. Линейный алгоритм построения компонент сильной связности. Кормен и др. Алгоритмы построение и анализ. Раздел 23.1.5 Сильно связные компоненты. С. 473 - 477

4. Матроиды определения, свойства. Примеры матроидов (универсальный, матричный, графовый, матроид трансверсалей) с обоснование. Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 341-343

5. Матроиды и жадные алгоритмы Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 343-345

6. Минимальные остовные деревья. Алгоритм Краскала и Прима. Кормен и др. Алгоритмы построение и анализ. Раздел 24 С. 482-490

7. Переборные алгоритмы для построения всех остовных деревьев. Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 148-158

8. Числа Рамсея Карпов. Теория графов. С. 477-479

9. Оценки чисел Рамсея Карпов. Теория графов С. 479-481

10. Обобщение чисел Рамсея Карпов. Теория графов С. 482-484

11. Паросочетания, теорема Холла. А. Эвнин Вокруг теоремы Холла С.5-6

12. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат. А. Эвнин Вокруг теоремы Холла С. 7,18

13. Лемма Бержа. Алгоритм Куна для поиска максимальных паросочетаний Claude Berge. Two theorems in graph theory // Proceedings of the National Academy of Sciences of the United States of America. — 1957. — September 15 (т. 43, вып. 9). — С. 842–844. — doi:10.1073/pnas.43.9.842 Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97. C 83-87

14. Венгерский алгоритм. Покрытие единиц матрицы строками и столбцами Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97. C 887-91

15. Последовательность де Брёйна. Оценка числа последовательностей деБрёйна. de Bruijn N. G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. — v. 49. — pp. 758—764 16. Задача коммивояжёра и ЗКНТ. Гэри, Джонсон Вычислительные машины и труднорешаемые задачи С 189-190

17. Достаточные признаки гамильтоновости графа.

R.Diestel Graph Theory. Springer 2000, C 213-216

18. Эйлеровы графы и задача китайского почтальона. Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 227-239

Список литературы

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

Кормен и др. Алгоритмы построение и анализ. Третье издание. Вильямс, 2013

Кристофидес Теория графов - Алгоритмический подход. М.Мир 1978

Д.В. Карпов Теория графов. https://logic.pdmi.ras.ru/~dvk/graphs_dk.pdf

А. Ю. Эвнин, Вокруг теоремы Холла, Матем. обр., 2005, выпуск 3(34), 2–23

Гери Джонсон Вычислительные машины и труднорешаемые задачи

Темы задач

1. Поиск компонент двусвязности

2. Множество фундаментальных циклов

3. Компоненты сильной связности

4. Коды Прюфера

5. Алгоритм Куна.

6. Венгерский алгоритм

7. Покрытие матрицы

8. Задача китайского почтальона

9. Задача коммивояжёра, МВГ

10. Задачи на теорему Холла

11. Гамильтоновость

12. Теория Рамсея

13. Задачи теории сложности на графах

14. Матроиды, жадные алгоритмы

Источник — «https://mk.cs.msu.ru/index.php?title=Графы_и_их_применения&oldid=11400»