Графы и их применения — различия между версиями
PodymovVV (обсуждение | вклад) м |
|||
| (не показаны 5 промежуточные версии 1 участника) | |||
| Строка 1: | Строка 1: | ||
| + | [[Категория:Спецкурсы кафедры МК]] | ||
| + | [[Категория:Лекционные курсы кафедры МК]] | ||
| + | [[Категория:Магистерская программа Дискретные структуры и алгоритмы]] | ||
| + | |||
Обязательный курс магистерской программы "Дискретные структуры и алгоритмы" | Обязательный курс магистерской программы "Дискретные структуры и алгоритмы" | ||
| Строка 70: | Строка 74: | ||
| − | Вопросы к экзамену | + | |
| + | == Вопросы к экзамену == | ||
| + | |||
1. Точка сочленения, компонента двусвязности. Необходимое и достаточное условия для точки сочленения. Алгоритм поиска точек сочленения и компонент двусвязности. | 1. Точка сочленения, компонента двусвязности. Необходимое и достаточное условия для точки сочленения. Алгоритм поиска точек сочленения и компонент двусвязности. | ||
| − | В. Липский Комбинаторика для программистов. Раздел 2.6 Нахождение компонент двусвязности. С. 95-99 | + | ''В. Липский Комбинаторика для программистов. Раздел 2.6 Нахождение компонент двусвязности. С. 95-99'' |
| + | |||
2. Множество фундаментальных циклов. Теорема о построении множества фундаментальных циклов. Алгоритм построения множества фундаментальных циклов. | 2. Множество фундаментальных циклов. Теорема о построении множества фундаментальных циклов. Алгоритм построения множества фундаментальных циклов. | ||
| − | В. Липский. Комбинаторика для программистов. Раздел 2.5 Отысканиефундаментального множества циклов. С. 92-95 | + | ''В. Липский. Комбинаторика для программистов. Раздел 2.5 Отысканиефундаментального множества циклов. С. 92-95'' |
| + | |||
3. Компонента сильной связности. Линейный алгоритм построения компонент сильной связности. | 3. Компонента сильной связности. Линейный алгоритм построения компонент сильной связности. | ||
| − | Кормен и др. Алгоритмы построение и анализ. Раздел 23.1.5 Сильно связные компоненты. С. 473 - 477 | + | ''Кормен и др. Алгоритмы построение и анализ. Раздел 23.1.5 Сильно связные компоненты. С. 473 - 477'' |
| + | |||
4. Матроиды определения, свойства. Примеры матроидов (универсальный, матричный, графовый, матроид трансверсалей) с обоснование. | 4. Матроиды определения, свойства. Примеры матроидов (универсальный, матричный, графовый, матроид трансверсалей) с обоснование. | ||
| − | Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 341-343 | + | ''Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 341-343'' |
| + | |||
5. Матроиды и жадные алгоритмы | 5. Матроиды и жадные алгоритмы | ||
| − | Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 343-345 | + | ''Кормен и др. Алгоритмы построение и анализ. Раздел 17.4 С. 343-345'' |
| + | |||
6. Минимальные остовные деревья. Алгоритм Краскала и Прима. | 6. Минимальные остовные деревья. Алгоритм Краскала и Прима. | ||
| − | Кормен и др. Алгоритмы построение и анализ. Раздел 24 С. 482-490 | + | ''Кормен и др. Алгоритмы построение и анализ. Раздел 24 С. 482-490'' |
| + | |||
7. Переборные алгоритмы для построения всех остовных деревьев. | 7. Переборные алгоритмы для построения всех остовных деревьев. | ||
| − | Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 148-158 | + | ''Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 148-158 |
| + | '' | ||
| + | |||
8. Числа Рамсея | 8. Числа Рамсея | ||
| − | Карпов. Теория графов. С. 477-479 | + | ''Карпов. Теория графов. С. 477-479'' |
| + | |||
9. Оценки чисел Рамсея | 9. Оценки чисел Рамсея | ||
| − | Карпов. Теория графов С. 479-481 | + | ''Карпов. Теория графов С. 479-481'' |
| + | |||
10. Обобщение чисел Рамсея | 10. Обобщение чисел Рамсея | ||
| − | Карпов. Теория графов С. 482-484 | + | ''Карпов. Теория графов С. 482-484'' |
| + | |||
11. Паросочетания, теорема Холла. | 11. Паросочетания, теорема Холла. | ||
| − | А. Эвнин Вокруг теоремы Холла С.5-6 | + | ''А. Эвнин Вокруг теоремы Холла С.5-6'' |
| + | |||
12. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат. | 12. Совершенные п.с., Теорема Пуанкаре для них, латинский квадрат. | ||
| − | А. Эвнин Вокруг теоремы Холла С. 7,18 | + | ''А. Эвнин Вокруг теоремы Холла С. 7,18'' |
| + | |||
13. Лемма Бержа. Алгоритм Куна для поиска максимальных паросочетаний | 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 | + | ''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. | Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97. | ||
| − | C 83-87 | + | C 83-87'' |
| + | |||
14. Венгерский алгоритм. Покрытие единиц матрицы строками и столбцами | 14. Венгерский алгоритм. Покрытие единиц матрицы строками и столбцами | ||
| − | Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97. | + | ''Kuhn, H.W. (1955) The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97. |
| − | C 887-91 | + | C 887-91'' |
| − | + | ||
| − | + | ||
| + | 15. Последовательность де Брёйна. Оценка числа последовательностей деБрёйна. | ||
| + | ''de Bruijn N. G. A combinatorial problem // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. — v. 49. — pp. 758—764'' | ||
16. Задача коммивояжёра и ЗКНТ. | 16. Задача коммивояжёра и ЗКНТ. | ||
| − | Гэри, Джонсон Вычислительные машины и труднорешаемые задачи | + | ''Гэри, Джонсон Вычислительные машины и труднорешаемые задачи |
| − | С 189-190 | + | С 189-190'' |
17. Достаточные признаки гамильтоновости графа. | 17. Достаточные признаки гамильтоновости графа. | ||
| − | |||
| − | + | ''R.Diestel Graph Theory. Springer 2000, C 213-216'' | |
| − | + | ||
| + | 18. Эйлеровы графы и задача китайского почтальона. | ||
| + | ''Кристофидес Теория графов - Алгоритмический подход. раздел 7.2 Построение всех остовных деревьев графа. С. 227-239'' | ||
| − | == Список литературы | + | == Список литературы == |
| Строка 131: | Строка 151: | ||
Гери Джонсон Вычислительные машины и труднорешаемые задачи | Гери Джонсон Вычислительные машины и труднорешаемые задачи | ||
| − | == | + | == Темы задач == |
| − | 1. | + | 1. Поиск компонент двусвязности |
2. Множество фундаментальных циклов | 2. Множество фундаментальных циклов | ||
| − | 3. | + | 3. Компоненты сильной связности |
| − | 4. | + | 4. Коды Прюфера |
| − | 5. Куна | + | 5. Алгоритм Куна. |
6. Венгерский алгоритм | 6. Венгерский алгоритм | ||
| Строка 157: | Строка 177: | ||
12. Теория Рамсея | 12. Теория Рамсея | ||
| − | 13. Задачи теории | + | 13. Задачи теории сложности на графах |
14. Матроиды, жадные алгоритмы | 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. Матроиды, жадные алгоритмы
