|
|
(не показаны 38 промежуточные версии 1 участника) |
Строка 1: |
Строка 1: |
| [[Категория:Лекционные_курсы_кафедры_МК]] | | [[Категория:Лекционные_курсы_кафедры_МК]] |
− |
| |
| Обязательный курс для студентов 418 группы | | Обязательный курс для студентов 418 группы |
| | | |
| Лекции 3 ч в неделю, отчетность - экзамен. | | Лекции 3 ч в неделю, отчетность - экзамен. |
| | | |
− | Лекторы - [[Романов Дмитрий Сергеевич]], [[Селезнева Светлана Николаевна]]. | + | Лекторы - [[Романов Дмитрий Сергеевич]] |
− | | + | |
− | <!--- Список вопросов по курсу "Избранные вопросы теории графов". <sup>[[Media:Список вопросов к экзамену по курсу ИВТГ_.doc|Список в формате .doc]]</sup> --->
| + | |
| | | |
| ==Часть 1== | | ==Часть 1== |
Строка 20: |
Строка 17: |
| | | |
| Лектор - [[Романов Дмитрий Сергеевич]] | | Лектор - [[Романов Дмитрий Сергеевич]] |
− |
| |
− | ==Часть 3==
| |
− |
| |
− | '''Структурные свойства графов'''
| |
− |
| |
− | Лектор - [[Селезнева Светлана Николаевна]]
| |
− |
| |
− | '''Лекции'''
| |
− |
| |
− | [[Media:ivtg3-l1-selezn.pdf|'''Лекция 1''']]. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья. Остовные деревья.
| |
− |
| |
− | [[Media:ivtg3-l2-selezn.pdf|'''Лекция 2''']]. Точки сочленения и мосты. Связность, k-связность. Двусвязные графы. Компоненты двусвязности (блоки) графа. Дерево блоков и точек сочленения графа.
| |
− |
| |
− | [[Media:ivtg3-l3-selezn.pdf|'''Лекция 3''']]. Деревья. Остовные деревья. Достижимость промежуточного числа висячих вершин в остовном дереве. Оценка числа висячих вершин в остовном дереве.
| |
− |
| |
− | [[Media:ivtg3-l4-selezn.pdf|'''Лекция 4''']]. Раскраски вершин графов. Хроматическое число графа. Критерий двуцветности графа. Верхние оценки хроматического числа графа. Существование графа без треугольников с произвольно большим хроматическим числом.
| |
− |
| |
− | [[Media:ivtg3-l5-selezn.pdf|'''Лекция 5''']]. Раскраски ребер графов. Хроматический индекс графа. Хроматический индекс двудольных графов. Верхняя и нижняя оценки хроматического индекса графа.
| |
− |
| |
− | [[Media:ivtg3-l6-selezn.pdf|'''Лекция 6''']]. Наследственные свойства графов. Экстремальные графы. Наибольшее число ребер в графах с наследственным свойством. Наибольшее число ребер в планарных графах. Наибольшее число ребер в графах без полного подграфа с n вершинами.
| |
− |
| |
− | [[Media:ivtg3-l7-selezn.pdf|'''Лекция 7''']]. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея.
| |
− |
| |
− | [[Media:ivtg3-l8-selezn.pdf|'''Лекция 8''']]. Сеть. Поток в сети. Теорема о величине максимального потока в сети. Нахождение максимального потока в сети.
| |
− |
| |
− | [[Media:ivtg3-l9-selezn.pdf|'''Лекция 9''']]. Труднорешаемые графовые задачи распознавания. NP-полнота задачи k-раскраски графов при каждом заданном числе k \ge 3.
| |
− |
| |
− | '''Литература к части 3'''
| |
− |
| |
− | '''Основная''':
| |
− |
| |
− | 1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009.
| |
− |
| |
− | 2. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.
| |
− |
| |
− | '''Дополнительная''':
| |
− |
| |
− | 3. Diestel R. Graph Theory. Springer, 2010.
| |
− |
| |
− | 4. Карпов Д.В. Теория графов
| |
− |
| |
− | 5. Харари Ф. Теория графов. М.: Мир, 1973.
| |
− |
| |
− | 6. Оре О. Теория графов. М.: Наука, 1980.
| |
− |
| |
− | 7. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
| |
− |
| |
− | 8. Липский В. Комбинаторика для программистов. М.: Мир, 1988.
| |
− |
| |
− | 9. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. М.: МЦНМО, 2014.
| |
− |
| |
− | 10. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.
| |
− |
| |
− | 11. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
| |
Лекции 3 ч в неделю, отчетность - экзамен.