Избранные вопросы теории графов — различия между версиями
(→Часть 3) |
(→Часть 3) |
||
(не показаны 14 промежуточные версии 1 участника) | |||
Строка 25: | Строка 25: | ||
Лектор - [[Селезнева Светлана Николаевна]] | Лектор - [[Селезнева Светлана Николаевна]] | ||
− | ''' | + | '''Программа''' части 3 |
− | + | * Графы. Изоморфизм графов. Пути и циклы. Связность. Простейший свойства графов. Обходы графов. Деревья. Свойства деревьев. Остовные деревья. Число остовных деревьев в полном графе. Достижимость промежуточного числа висячих вершин в остовных деревьях. Число висячих вершин в остовных деревьях. Непересекающиеся остовные деревья. | |
+ | * Разделяющие вершины в графе. Свойства разделяющих вершин. Двусвязные графы. Свойства двусвязных графов. Мосты в графе. Свойства мостов. Реберно двусвязные графы их свойства. Компоненты двусвязности графа. Свойства компонент двусвязности. Разложение графа на компоненты двусвязности. Дерево компонент двусвязности и разделяющих вершин графа. Цепные разложения графа. Независимые деревья в графе. Реберно независимые деревья в графе. | ||
− | + | '''Лекции''' | |
− | [[Media:ivtg3- | + | [[Media:ivtg3-l1-selezn.pdf|'''Лекция 1''']]. Графы. Простейшие свойства графов. Цепи и циклы в графах. Связность. Обходы графов. |
− | [[Media:ivtg3- | + | [[Media:ivtg3-l2-selezn.pdf|'''Лекция 2''']]. Деревья. Свойства деревьев. Остовные деревья в графе. Реберно непересекающиеся остовные деревья в графе. |
− | + | '''Литература''' к части 3 | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009. | 1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009. | ||
2. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008. | 2. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008. | ||
− | |||
− | |||
3. Diestel R. Graph Theory. Springer, 2010. | 3. Diestel R. Graph Theory. Springer, 2010. | ||
− | 4. | + | 4. Липский В. Комбинаторика для программистов. М.: Мир, 1988. |
− | 5. | + | 5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. |
− | + | <!---'''Дополнительная''': | |
− | + | 6. Харари Ф. Теория графов. М.: Мир, 1973. | |
− | 8. | + | 7. Оре О. Теория графов. М.: Наука, 1980. |
+ | |||
+ | 8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. | ||
9. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. М.: МЦНМО, 2014. | 9. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. М.: МЦНМО, 2014. | ||
− | 10. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966. | + | 10. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.---> |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
'''Проверочные работы''' по части 3. | '''Проверочные работы''' по части 3. | ||
− | В течение семестра по части 3 проводятся три проверочные работы: | + | <!---В течение семестра по части 3 проводятся три проверочные работы: |
1-я по темам "Простейшие свойства графов. Двусвязность. Остовные деревья"; | 1-я по темам "Простейшие свойства графов. Двусвязность. Остовные деревья"; | ||
Строка 82: | Строка 67: | ||
2-я по темам "Раскраски вершин. Раскраски ребер. Экстремальные графы"; | 2-я по темам "Раскраски вершин. Раскраски ребер. Экстремальные графы"; | ||
− | 3-я по темам "Теория Рамсея. Потоки в сетях. Труднорешаемые задачи". | + | 3-я по темам "Теория Рамсея. Потоки в сетях. Труднорешаемые задачи".---> |
− | + | По итогам проверочных работ для каждого студента выводится предварительная оценка по части 3. Для подтверждения предварительной оценки по части 3 на экзамене проводится опрос студента по темам этой части (определения, формулировки теорем, основные идеи доказательств). Для повышения предварительной оценки по части 3 (не более, чем на один балл), студент тянет билет по этой части, готовится (30 мин) и отвечает на вопрос билета, после чего проводится опрос по темам этой части (определения, формулировки теорем, основные идеи доказательств). | |
− | По итогам | + |
Версия 19:27, 14 сентября 2022
Обязательный курс для студентов 418 группы
Лекции 3 ч в неделю, отчетность - экзамен.
Лекторы - Романов Дмитрий Сергеевич, Селезнева Светлана Николаевна.
Часть 1
Алгебраические свойства графов
Лектор - Романов Дмитрий Сергеевич
Часть 2
Перечисления графов
Лектор - Романов Дмитрий Сергеевич
Часть 3
Структурные свойства графов
Лектор - Селезнева Светлана Николаевна
Программа части 3
- Графы. Изоморфизм графов. Пути и циклы. Связность. Простейший свойства графов. Обходы графов. Деревья. Свойства деревьев. Остовные деревья. Число остовных деревьев в полном графе. Достижимость промежуточного числа висячих вершин в остовных деревьях. Число висячих вершин в остовных деревьях. Непересекающиеся остовные деревья.
- Разделяющие вершины в графе. Свойства разделяющих вершин. Двусвязные графы. Свойства двусвязных графов. Мосты в графе. Свойства мостов. Реберно двусвязные графы их свойства. Компоненты двусвязности графа. Свойства компонент двусвязности. Разложение графа на компоненты двусвязности. Дерево компонент двусвязности и разделяющих вершин графа. Цепные разложения графа. Независимые деревья в графе. Реберно независимые деревья в графе.
Лекции
Лекция 1. Графы. Простейшие свойства графов. Цепи и циклы в графах. Связность. Обходы графов.
Лекция 2. Деревья. Свойства деревьев. Остовные деревья в графе. Реберно непересекающиеся остовные деревья в графе.
Литература к части 3
1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009.
2. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.
3. Diestel R. Graph Theory. Springer, 2010.
4. Липский В. Комбинаторика для программистов. М.: Мир, 1988.
5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
Проверочные работы по части 3.
По итогам проверочных работ для каждого студента выводится предварительная оценка по части 3. Для подтверждения предварительной оценки по части 3 на экзамене проводится опрос студента по темам этой части (определения, формулировки теорем, основные идеи доказательств). Для повышения предварительной оценки по части 3 (не более, чем на один балл), студент тянет билет по этой части, готовится (30 мин) и отвечает на вопрос билета, после чего проводится опрос по темам этой части (определения, формулировки теорем, основные идеи доказательств).