|
|
| (не показана 1 промежуточная версия 1 участника) |
| Строка 5: |
Строка 5: |
| | Лектор: [[Бухман Антон Владимирович]] | | Лектор: [[Бухман Антон Владимирович]] |
| | | | |
| − | ==Программа курса==
| |
| | | | |
| − | '''Лекция 1'''. Числа Рамсея. Верхняя и нижняя оценки.
| |
| − |
| |
| − | '''Лекция 2'''. Обобщение чисел Рамсея. Примеры их использования.
| |
| − |
| |
| − | '''Лекция 3'''. Теоремы о раскрасках графа.
| |
| − |
| |
| − | '''Лекция 4'''. Поиск в глубину и поиск в ширину в графе. Нахождение остовного дерева графа поиском в глубину и поиском в ширину. Отыскание фундаментального множества циклов в графе. Критерий разделяющей вершины на основе поиска в глубину. Нахождение компонент двусвязности графа.
| |
| − |
| |
| − | '''Лекция 5'''. Алгоритмы поиска кратчайшего остовного дерева. Матроиды и жадные алгоритмы. Теорема Радо-Эдмонса.
| |
| − |
| |
| − | '''Лекция 6'''. Потоки в сетях. Максимальный поток в сети. Теорема Форда-Фалкерсона о величине максимального потока в сети. Алгоритмы отыскания максимального потока в сети.
| |
| − |
| |
| − | '''Лекция 7'''. Паросочетания в графах. Теорема Холла. Паросочетания в двудольных графах. Алгоритм отыскания наибольшего паросочетания двудольного графа на основе построения максимального потока в сети.
| |
| − |
| |
| − | '''Лекция 8'''. Паросочетания в графах. Теорема Куна. Теорема Эдмонса. Алгоритмы отыскания наибольших паросочетаний в двудольных графах и в произвольных графах.
| |
| − |
| |
| − | '''Лекция 9'''. Эйлеровы пути и циклы в графах. Критерий эйлеровости графа. Задача китайского почтальона. Гамильтоновы пути и циклы в графах. Достаточные условия гамильтоновости графа.
| |
| − |
| |
| − | '''Лекция 10'''. Гамильтоновы циклы в графах. Задача коммивояжера с неравенством треугольника и без него. Приближенные алгоритмы. Переборные алгоритмы, дерево решений. Алгоритм перебора всех остовных деревьев графа.
| |
| − |
| |
| − | '''Лекция 11'''. Изоморфизм графов. Полиномиальный алгоритм проверки изоморфизма деревьев. Построение выпуклого n-угольника на достаточно большом множестве точек.
| |
| − |
| |
| − | ==Литература==
| |
| − |
| |
| − | '''Основная''':
| |
| − |
| |
| − | 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.
| |
| − |
| |
| | | | |
| | [[Категория:Лекционные курсы кафедры МК]] | | [[Категория:Лекционные курсы кафедры МК]] |
| | [[Категория:Магистерская программа Дискретные структуры и алгоритмы]] | | [[Категория:Магистерская программа Дискретные структуры и алгоритмы]] |
