Избранные вопросы теории графов — различия между версиями

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