|
|
| (не показаны 14 промежуточные версии 1 участника) |
| Строка 4: |
Строка 4: |
| | Лекции 3 ч в неделю, отчетность - экзамен. | | Лекции 3 ч в неделю, отчетность - экзамен. |
| | | | |
| − | Лекторы - [[Романов Дмитрий Сергеевич]], [[Селезнева Светлана Николаевна]]. | + | Лекторы - [[Романов Дмитрий Сергеевич]] |
| | | | |
| − | <!--- Список вопросов по курсу "Избранные вопросы теории графов". <sup>[[Media:Список вопросов к экзамену по курсу ИВТГ_.doc|Список в формате .doc]]</sup> --->
| |
| | ==Часть 1== | | ==Часть 1== |
| | | | |
| Строка 18: |
Строка 17: |
| | | | |
| | Лектор - [[Романов Дмитрий Сергеевич]] | | Лектор - [[Романов Дмитрий Сергеевич]] |
| − |
| |
| − | ==Часть 3==
| |
| − |
| |
| − | '''Структурные свойства графов'''
| |
| − |
| |
| − | Лектор - [[Селезнева Светлана Николаевна]]
| |
| − |
| |
| − | '''Программа''' части 3
| |
| − |
| |
| − | * Графы. Изоморфизм графов. Пути и циклы. Связность. Простейший свойства графов. Обходы графов. Деревья. Свойства деревьев. Остовные деревья. Число остовных деревьев в полном графе. Достижимость промежуточного числа висячих вершин в остовных деревьях. Число висячих вершин в остовных деревьях. Непересекающиеся остовные деревья.
| |
| − | * Разделяющие вершины в графе. Свойства разделяющих вершин. Двусвязные графы. Свойства двусвязных графов. Мосты в графе. Свойства мостов. Реберно двусвязные графы их свойства. Компоненты двусвязности графа. Свойства компонент двусвязности. Разложение графа на компоненты двусвязности. Дерево компонент двусвязности и разделяющих вершин графа. Цепные разложения графа. Независимые деревья в графе. Реберно независимые деревья в графе.
| |
| − |
| |
| − | '''Лекции'''
| |
| − |
| |
| − | [[Media:ivtg3-l1-selezn.pdf|'''Лекция 1''']]. Графы. Простейшие свойства графов. Цепи и циклы в графах. Связность. Обходы графов.
| |
| − |
| |
| − | [[Media:ivtg3-l2-selezn.pdf|'''Лекция 1''']]. Деревья. Свойства деревьев. Остовные деревья в графе. Реберно непересекающиеся остовные деревья в графе.
| |
| − |
| |
| − | '''Литература''' к части 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.
| |
| − |
| |
| − | <!---'''Дополнительная''':
| |
| − |
| |
| − | 6. Харари Ф. Теория графов. М.: Мир, 1973.
| |
| − |
| |
| − | 7. Оре О. Теория графов. М.: Наука, 1980.
| |
| − |
| |
| − | 8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
| |
| − |
| |
| − | 9. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. М.: МЦНМО, 2014.
| |
| − |
| |
| − | 10. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.--->
| |
| − | '''Проверочные работы''' по части 3.
| |
| − |
| |
| − | <!---В течение семестра по части 3 проводятся три проверочные работы:
| |
| − |
| |
| − | 1-я по темам "Простейшие свойства графов. Двусвязность. Остовные деревья";
| |
| − |
| |
| − | 2-я по темам "Раскраски вершин. Раскраски ребер. Экстремальные графы";
| |
| − |
| |
| − | 3-я по темам "Теория Рамсея. Потоки в сетях. Труднорешаемые задачи".--->
| |
| − | По итогам проверочных работ для каждого студента выводится предварительная оценка по части 3. Для подтверждения предварительной оценки по части 3 на экзамене проводится опрос студента по темам этой части (определения, формулировки теорем, основные идеи доказательств). Для повышения предварительной оценки по части 3 (не более, чем на один балл), студент тянет билет по этой части, готовится (30 мин) и отвечает на вопрос билета, после чего проводится опрос по темам этой части (определения, формулировки теорем, основные идеи доказательств).
| |
