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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Литература)
Строка 3: Строка 3:
 
Курс читается в 1-м семестре магистратуры, 2 ч лекций, 1 ч семинаров
 
Курс читается в 1-м семестре магистратуры, 2 ч лекций, 1 ч семинаров
  
−
Лектор — доцент [[Селезнева Светлана Николаевна]]
+
Лектор: [[Бухман Антон Владимирович]]
  
−
==Программа курса==
+
= Программа курса =
  
−
'''Лекция 1'''. Основные определения. Простейшие свойства графов. Граф, изоморфизм графов. Степень вершины, изолированная и висячая вершины. Теорема о сумме степеней вершин графа. Маршрут, путь, цикл в графе. Теорема о свойствах путей и циклов в графе. Связность, компонента связности. Теорема о числе ребер в связном графе. Дерево. Теоремы о свойствах деревьев.
+
== Часть 1. Теоретические основы ==
  
−
'''Лекция 2'''. Остовное дерево. Алгоритмы построения остовного дерева связного графа. Теорема о числе остовных деревьев полного графа. Теорема о двух остовных деревьях связного графа. Теоремы об оценке числа висячих вершин остовного дерева связного графа. Труднорешаемые задачи, труднорешаемость задачи построения остовного дерева с наибольшим числом висячих вершин.
+
'''Лекция 1.''' Основные определения. Простейшие свойства графов. Деревья. Теоремы о свойствах деревьев. Остовные деревья.
  
−
==Программа семинарских занятий==
+
'''Лекция 2.''' Число остовных деревьев. Остовные деревья с наибольшим числом висячих вершин. Коды Прюфера. Теорема Кэли.
  
−
'''Семинар 1'''. Простейшие свойства графов.
+
'''Лекция 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.''' Переборные алгоритмы на графах.
 +
 
 +
= Литература =
 
#Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
 
#Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
 
#Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд. отд. ф-та ВМК МГУ имени М.В. Ломоносова, 2002.
 
#Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд. отд. ф-та ВМК МГУ имени М.В. Ломоносова, 2002.

Версия 12:30, 11 апреля 2017

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

Курс читается в 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.
Источник — «https://mk.cs.msu.ru/index.php?title=Графы_и_их_применения&oldid=3729»