Избранные вопросы теории графов — различия между версиями
(→Часть 3) |
|||
(не показаны 24 промежуточных версий 1 участника) | |||
Строка 1: | Строка 1: | ||
[[Категория:Лекционные_курсы_кафедры_МК]] | [[Категория:Лекционные_курсы_кафедры_МК]] | ||
− | |||
Обязательный курс для студентов 418 группы | Обязательный курс для студентов 418 группы | ||
+ | |||
+ | Лекции 3 ч в неделю, отчетность - экзамен. | ||
Лекторы - [[Романов Дмитрий Сергеевич]], [[Селезнева Светлана Николаевна]]. | Лекторы - [[Романов Дмитрий Сергеевич]], [[Селезнева Светлана Николаевна]]. | ||
− | Список вопросов по курсу "Избранные вопросы теории графов". <sup>[[Media:Список вопросов к экзамену по курсу ИВТГ_.doc|Список в формате .doc]]</sup> | + | <!--- Список вопросов по курсу "Избранные вопросы теории графов". <sup>[[Media:Список вопросов к экзамену по курсу ИВТГ_.doc|Список в формате .doc]]</sup> ---> |
+ | ==Часть 1== | ||
+ | |||
+ | '''Алгебраические свойства графов''' | ||
+ | |||
+ | Лектор - [[Романов Дмитрий Сергеевич]] | ||
+ | |||
+ | ==Часть 2== | ||
+ | |||
+ | '''Перечисления графов''' | ||
+ | |||
+ | Лектор - [[Романов Дмитрий Сергеевич]] | ||
+ | |||
+ | ==Часть 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''']]. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея. | ||
+ | |||
+ | <!---'''Лекция 8'''. Сеть. Поток в сети. Теорема о величине максимального потока в сети. Нахождение максимального потока в сети. | ||
+ | |||
+ | '''Лекция 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. | |
− | + | <!---В течение семестра по части 3 проводятся три проверочные работы: | |
− | + | 1-я по темам "Простейшие свойства графов. Двусвязность. Остовные деревья"; | |
− | + | 2-я по темам "Раскраски вершин. Раскраски ребер. Экстремальные графы"; | |
− | + | 3-я по темам "Теория Рамсея. Потоки в сетях. Труднорешаемые задачи".---> | |
− | + | По итогам проверочных работ для каждого студента выводится предварительная оценка по части 3. Для подтверждения предварительной оценки по части 3 на экзамене проводится опрос студента по темам этой части (определения, формулировки теорем, основные идеи доказательств). Для повышения предварительной оценки по части 3 (не более, чем на один балл), студент тянет билет по этой части, готовится (30 мин) и отвечает на вопрос билета, после чего проводится опрос по темам этой части (определения, формулировки теорем, основные идеи доказательств). |
Версия 23:12, 8 декабря 2021
Обязательный курс для студентов 418 группы
Лекции 3 ч в неделю, отчетность - экзамен.
Лекторы - Романов Дмитрий Сергеевич, Селезнева Светлана Николаевна.
Часть 1
Алгебраические свойства графов
Лектор - Романов Дмитрий Сергеевич
Часть 2
Перечисления графов
Лектор - Романов Дмитрий Сергеевич
Часть 3
Структурные свойства графов
Лектор - Селезнева Светлана Николаевна
Лекции
Лекция 1. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья.
Лекция 2. Точки сочленения и мосты. Связность, k-связность. Двусвязные графы. Компоненты двусвязности (блоки) графа. Дерево блоков и точек сочленения графа.
Лекция 3. Деревья. Остовные деревья. Достижимость промежуточного числа висячих вершин в остовном дереве. Оценка числа висячих вершин в остовном дереве.
Лекция 4. Раскраски вершин графов. Хроматическое число графа. Критерий двуцветности графа. Верхние оценки хроматического числа графа. Существование графа без треугольников с произвольно большим хроматическим числом.
Лекция 5. Раскраски ребер графов. Хроматический индекс графа. Хроматический индекс двудольных графов. Верхняя и нижняя оценки хроматического индекса графа.
Лекция 6. Наследственные свойства графов. Экстремальные графы. Наибольшее число ребер в графах с наследственным свойством. Наибольшее число ребер в планарных графах. Наибольшее число ребер в графах без полного подграфа с n вершинами.
Лекция 7. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея.
Литература к части 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.
По итогам проверочных работ для каждого студента выводится предварительная оценка по части 3. Для подтверждения предварительной оценки по части 3 на экзамене проводится опрос студента по темам этой части (определения, формулировки теорем, основные идеи доказательств). Для повышения предварительной оценки по части 3 (не более, чем на один балл), студент тянет билет по этой части, готовится (30 мин) и отвечает на вопрос билета, после чего проводится опрос по темам этой части (определения, формулировки теорем, основные идеи доказательств).