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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Часть 3)
(Часть 3)
(не показаны 3 промежуточных версий 1 участника)
Строка 27: Строка 27:
 
'''Лекции'''
 
'''Лекции'''
  
[[Media:ivtg3-l1-selezn.pdf|'''Лекция 1''']]. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья. Остовные деревья.
+
[[Media:ivtg3-l1-selezn.pdf|'''Лекция 1''']]. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья.  
  
 
[[Media:ivtg3-l2-selezn.pdf|'''Лекция 2''']]. Точки сочленения и мосты. Связность, k-связность. Двусвязные графы. Компоненты двусвязности (блоки) графа. Дерево блоков и точек сочленения графа.
 
[[Media:ivtg3-l2-selezn.pdf|'''Лекция 2''']]. Точки сочленения и мосты. Связность, k-связность. Двусвязные графы. Компоненты двусвязности (блоки) графа. Дерево блоков и точек сочленения графа.
Строка 39: Строка 39:
 
[[Media:ivtg3-l6-selezn.pdf|'''Лекция 6''']]. Наследственные свойства графов. Экстремальные графы. Наибольшее число ребер в графах с наследственным свойством. Наибольшее число ребер в планарных графах. Наибольшее число ребер в графах без полного подграфа с n вершинами.
 
[[Media:ivtg3-l6-selezn.pdf|'''Лекция 6''']]. Наследственные свойства графов. Экстремальные графы. Наибольшее число ребер в графах с наследственным свойством. Наибольшее число ребер в планарных графах. Наибольшее число ребер в графах без полного подграфа с n вершинами.
  
'''Лекция 7'''. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея.
+
[[Media:ivtg3-l7-selezn.pdf|'''Лекция 7''']]. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея.
  
'''Лекция 8'''. Сеть. Поток в сети. Теорема о величине максимального потока в сети. Нахождение максимального потока в сети.
+
<!---'''Лекция 8'''. Сеть. Поток в сети. Теорема о величине максимального потока в сети. Нахождение максимального потока в сети.
  
'''Лекция 9'''. Труднорешаемые графовые задачи распознавания. NP-полнота задачи k-раскраски графов при каждом заданном числе k \ge 3.
+
'''Лекция 9'''. Труднорешаемые графовые задачи распознавания. NP-полнота задачи k-раскраски графов при каждом заданном числе k \ge 3.--->
  
 
'''Литература к части 3'''
 
'''Литература к части 3'''
Строка 76: Строка 76:
 
'''Проверочные работы''' по части 3.
 
'''Проверочные работы''' по части 3.
  
В течение семестра по части 3 проводятся три проверочные работы:  
+
<!---В течение семестра по части 3 проводятся три проверочные работы:  
  
 
1-я по темам "Простейшие свойства графов. Двусвязность. Остовные деревья";
 
1-я по темам "Простейшие свойства графов. Двусвязность. Остовные деревья";
Строка 82: Строка 82:
 
2-я по темам "Раскраски вершин. Раскраски ребер. Экстремальные графы";
 
2-я по темам "Раскраски вершин. Раскраски ребер. Экстремальные графы";
  
3-я по темам "Теория Рамсея. Потоки в сетях. Труднорешаемые задачи".
+
3-я по темам "Теория Рамсея. Потоки в сетях. Труднорешаемые задачи".--->
  
По итогам этих работ для каждого студента выводится предварительная оценка по части 3. Для подтверждения предварительной оценки по части 3 на экзамене проводится опрос студента по темам этой части (определения, формулировки теорем, основные идеи доказательств). Для повышения предварительной оценки по части 3 (не более, чем на один балл), студент тянет билет по этой части, готовится (30 мин) и отвечает на вопрос билета, после чего проводится опрос по темам этой части (определения, формулировки теорем, основные идеи доказательств).
+
По итогам проверочных работ для каждого студента выводится предварительная оценка по части 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 мин) и отвечает на вопрос билета, после чего проводится опрос по темам этой части (определения, формулировки теорем, основные идеи доказательств).