|
|
(не показаны 11 промежуточные версии 2 участников) |
Строка 1: |
Строка 1: |
| Обязательный курс магистерской программы "Дискретные структуры и алгоритмы" | | Обязательный курс магистерской программы "Дискретные структуры и алгоритмы" |
| | | |
− | Курс читается в 1-м семестре магистратуры, 2 ч лекций, 1 ч семинаров | + | Курс читается в 1-м семестре магистратуры, 1 ч лекций, 1 ч семинаров |
| | | |
− | Лекторы: [[Селезнева Светлана Николаевна]], [[Бухман Антон Владимирович]]
| + | Лектор: [[Бухман Антон Владимирович]] |
| | | |
− | ==Объявления==
| |
| | | |
− | [[Media:gip.docx|'''Вопросы к экзамену''']]
| |
− |
| |
− | Досрочный экзамен состоится 16 декабря (в субботу) в 11 ч в ауд. 503.
| |
− |
| |
− | Консультация по курсу состоится в среду, 13 декабря, с 8-45 до 10-20 в ауд. по расписанию лекций.
| |
− |
| |
− | ==Программа курса==
| |
− |
| |
− | '''Часть 1'''.
| |
− |
| |
− | [[Media:gip-l1-selezn.pdf|'''Лекция 1''']]. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья. Остовные деревья.
| |
− |
| |
− | [[Media:gip-l2-selezn.pdf|'''Лекция 2''']]. Точки сочленения и мосты. Связность, k-связность. Двусвязные графы. Компоненты двусвязности (блоки) графа. Дерево блоков и точек сочленения графа.
| |
− |
| |
− | [[Media:gip-l3-selezn.pdf|'''Лекция 3''']]. Деревья. Остовные деревья. Число остовных деревьев помеченного полного графа. Достижимость промежуточного числа висячих вершин в остовном дереве. Оценка числа висячих вершин в остовном дереве.
| |
− |
| |
− | [[Media:gip-l4-selezn.pdf|'''Лекция 4''']]. Раскраски вершин графов. Хроматическое число графа. Критерий двуцветности графа. Верхние оценки хроматического числа графа. Существование графов без треугольников с произвольно большим хроматическим числом.
| |
− |
| |
− | [[Media:gip-l5-selezn.pdf|'''Лекция 5''']]. Раскраски ребер графов. Хроматический индекс графа. Хроматический индекс двудольных графов. Верхняя и нижняя оценки хроматического индекса графа.
| |
− |
| |
− | [[Media:gip-l6-selezn.pdf|'''Лекция 6''']]. Наследственные свойства графов. Наибольшее число ребер в графах с наследственным свойством. Наибольшее число ребер в планарных графах. Наибольшее число ребер в графах без полного подграфа с n вершинами.
| |
− |
| |
− | [[Media:gip-l7-selezn.pdf|'''Лекция 7''']]. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея.
| |
− |
| |
− | '''Часть 2'''.
| |
− |
| |
− | '''Лекция 8'''. Поиск в глубину и поиск в ширину в графе. Нахождение остовного дерева графа поиском в глубину и поиском в ширину. Отыскание фундаментального множества циклов в графе. Критерий разделяющей вершины на основе поиска в глубину. Нахождение компонент двусвязности графа.
| |
− |
| |
− | '''Лекция 9'''. Алгоритмы поиска кратчайшего остовного дерева. Матроиды и жадные алгоритмы. Теорема Радо-Эдмонса.
| |
− |
| |
− | '''Лекция 10'''. Потоки в сетях. Максимальный поток в сети. Теорема Форда-Фалкерсона о величине максимального потока в сети. Алгоритмы отыскания максимального потока в сети.
| |
− |
| |
− | '''Лекция 11'''. Паросочетания в графах. Теорема Холла. Паросочетания в двудольных графах. Алгоритм отыскания наибольшего паросочетания двудольного графа на основе построения максимального потока в сети.
| |
− |
| |
− | '''Лекция 12'''. Паросочетания в графах. Теорема Куна. Теорема Эдмонса. Алгоритмы отыскания наибольших паросочетаний в двудольных графах и в произвольных графах.
| |
− |
| |
− | '''Лекция 13'''. Эйлеровы пути и циклы в графах. Критерий эйлеровости графа. Задача китайского почтальона. Гамильтоновы пути и циклы в графах. Достаточные условия гамильтоновости графа.
| |
− |
| |
− | '''Лекция 14'''. Гамильтоновы циклы в графах. Задача коммивояжера с неравенством треугольника и без него. Приближенные алгоритмы. Переборные алгоритмы, дерево решений. Алгоритм перебора всех остовных деревьев графа.
| |
− |
| |
− | '''Лекция 15'''. Изоморфизм графов. Полиномиальный алгоритм проверки изоморфизма деревьев. Построение выпуклого n-угольника на достаточно большом множестве точек.
| |
− |
| |
− | ==Программа семинарских занятий==
| |
− |
| |
− | '''Семинар 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.
| |
− |
| |
− | 12. Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического ф-та МГУ имени М.В. Ломоносова, 2007.
| |
− |
| |
− | 13. Diestel R. Graph Theory. Springer, 2010.
| |
− |
| |
| | | |
| [[Категория:Лекционные курсы кафедры МК]] | | [[Категория:Лекционные курсы кафедры МК]] |
| [[Категория:Магистерская программа Дискретные структуры и алгоритмы]] | | [[Категория:Магистерская программа Дискретные структуры и алгоритмы]] |