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