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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
Строка 5: Строка 5:
 
Лекторы: [[Селезнева Светлана Николаевна]], [[Бухман Антон Владимирович]]
 
Лекторы: [[Селезнева Светлана Николаевна]], [[Бухман Антон Владимирович]]
  
= Программа курса =
+
==Программа курса==
  
== Часть 1. ==
+
'''Часть 1'''.
  
 
[[gip-l1-selezn.pdf|'''Лекция 1''']]. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья. Остовные деревья.
 
[[gip-l1-selezn.pdf|'''Лекция 1''']]. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья. Остовные деревья.
Строка 23: Строка 23:
 
[[gip-l7-selezn.pdf|'''Лекция 7''']]. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея.
 
[[gip-l7-selezn.pdf|'''Лекция 7''']]. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея.
  
== Часть 2. ==
+
'''Часть 2'''.
  
= Программа семинарских занятий =
+
==Программа семинарских занятий==
  
'''Семинар 1. Простейшие свойства графов (повторение)'''.
+
'''Семинар 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.
 
[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. Связность, двусвязность графов. Остовные деревья'''.
+
'''Семинар 2'''. Связность, двусвязность графов. Остовные деревья.
 
[5] Гл. 6: 1.24, 1.17, 3.15, задачи лекций 2 и 3.
 
[5] Гл. 6: 1.24, 1.17, 3.15, задачи лекций 2 и 3.
  
'''Семинар 3. Раскраски графов. Хроматическое число и хроматический индекс графа'''.
+
'''Семинар 3'''. Раскраски графов. Хроматическое число и хроматический индекс графа.
 
[5] Гл. 6: 2.18, 2.19, 2.20, 2.21, задачи лекций 4 и 5.   
 
[5] Гл. 6: 2.18, 2.19, 2.20, 2.21, задачи лекций 4 и 5.   
  
'''Семинар 4. Наследственные свойства графов. Числа Рамсея'''.
+
'''Семинар 4'''. Наследственные свойства графов. Числа Рамсея.
 
[5] Гл. 6: 2.7, 2.8, 2.9, 2.10, 2.13, 2.17, задачи лекций 6 и 7.  
 
[5] Гл. 6: 2.7, 2.8, 2.9, 2.10, 2.13, 2.17, задачи лекций 6 и 7.  
  
= Литература =
+
==Литература==
  
 
'''Основная''':
 
'''Основная''':
#Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009.
+
 
#Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.
+
1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009.
#Харари Ф. Теория графов. М.: Мир, 1973.
+
 
#Липский В. Комбинаторика для программистов. М.: Мир, 1988.
+
2. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.
#Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
+
 
 +
3. Харари Ф. Теория графов. М.: Мир, 1973.
 +
 
 +
4. Липский В. Комбинаторика для программистов. М.: Мир, 1988.
 +
 
 +
5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
  
 
'''Дополнительная''':
 
'''Дополнительная''':
#Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
+
 
#Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд. отд. ф-та ВМК МГУ имени М.В. Ломоносова, 2002.
+
6. Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
#Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
+
 
#Оре О. Теория графов. М.: Наука, 1980.
+
7. Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд. отд. ф-та ВМК МГУ имени М.В. Ломоносова, 2002.
#Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.  
+
 
#Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.  
+
8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
 +
 
 +
9. Оре О. Теория графов. М.: Наука, 1980.
 +
 
 +
10. Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.  
 +
 
 +
11. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.  
 
    
 
    
  
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]
 
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]

Версия 11:42, 14 августа 2017

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

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

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

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

Часть 1.

Лекция 1. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья. Остовные деревья.

Лекция 2. Точки сочленения и мосты. Связность, k-связность. Двусвязные графы. Компоненты двусвязности (блоки) графа. Дерево блоков и точек сочленения графа.

Лекция 3. Деревья. Остовные деревья. Число остовных деревьев помеченного полного графа. Достижимость промежуточного числа висячих вершин в остовном дереве. Оценка числа висячих вершин в остовном дереве.

Лекция 4. Раскраски вершин графов. Хроматическое число графа. Критерий двуцветности графа. Верхние оценки хроматического числа графа. Существование графов без треугольников с произвольно большим хроматическим числом.

Лекция 5. Раскраски ребер графов. Хроматический индекс графа. Хроматический индекс двудольных графов. Верхняя и нижняя оценки хроматического индекса графа.

Лекция 6. Наследственные свойства графов. Наибольшее число ребер в графах с наследственным свойством. Наибольшее число ребер в планарных графах. Наибольшее число ребер в графах без полного подграфа с n вершинами.

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

Часть 2.

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

Семинар 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.

Литература

Основная:

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.