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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Часть 3)
 
(не показаны 46 промежуточные версии 1 участника)
Строка 1: Строка 1:
 
[[Категория:Лекционные_курсы_кафедры_МК]]
 
[[Категория:Лекционные_курсы_кафедры_МК]]
−
 
 
Обязательный курс для студентов 418 группы
 
Обязательный курс для студентов 418 группы
  
Строка 7: Строка 6:
 
Лекторы - [[Романов Дмитрий Сергеевич]], [[Селезнева Светлана Николаевна]].
 
Лекторы - [[Романов Дмитрий Сергеевич]], [[Селезнева Светлана Николаевна]].
  
−
Список вопросов по курсу "Избранные вопросы теории графов". <sup>[[Media:Список вопросов к экзамену по курсу ИВТГ_.doc|Список в формате .doc]]</sup>
+
<!--- Список вопросов по курсу "Избранные вопросы теории графов". <sup>[[Media:Список вопросов к экзамену по курсу ИВТГ_.doc|Список в формате .doc]]</sup> --->
−
 
+
==Часть 1==
−
'''Часть 1. Алгебраические свойства графов'''. Лектор - [[Романов Дмитрий Сергеевич]]
+
−
 
+
−
'''Часть 2. Перечисления графов'''. Лектор - [[Романов Дмитрий Сергеевич]]
+
−
 
+
−
'''Часть 3. Структурные свойства графов'''. Лектор - [[Селезнева Светлана Николаевна]]
+
−
 
+
−
[[Media:ivtg-l1-selezn.pdf|'''Лекция 1''']]. Графы. Основные определения. Простейшие свойства графов. Пути и цепи в графах. Связность, k-связность. Деревья, корневые деревья. Остовные деревья.
+
  
−
[[Media:ivtg-l2-selezn.pdf|'''Лекция 2''']]. Точки сочленения и мосты. Связность, k-связность. Двусвязные графы. Компоненты двусвязности (блоки) графа. Дерево блоков и точек сочленения графа.
+
'''Алгебраические свойства графов'''
  
−
[[Media:ivtg-l3-selezn.pdf|'''Лекция 3''']]. Деревья. Остовные деревья. Достижимость промежуточного числа висячих вершин в остовном дереве. Оценка числа висячих вершин в остовном дереве.
+
Лектор - [[Романов Дмитрий Сергеевич]]
  
−
[[Media:ivtg-l4-selezn.pdf|'''Лекция 4''']]. Раскраски вершин графов. Хроматическое число графа. Критерий двуцветности графа. Верхние оценки хроматического числа графа. Существование графа без треугольников с произвольно большим хроматическим числом.
+
==Часть 2==
  
−
[[Media:ivtg-l5-selezn.pdf|'''Лекция 5''']]. Раскраски ребер графов. Хроматический индекс графа. Хроматический индекс двудольных графов. Верхняя и нижняя оценки хроматического индекса графа.
+
'''Перечисления графов'''  
  
−
[[Media:ivtg-l6-selezn.pdf|'''Лекция 6''']]. Наследственные свойства графов. Экстремальные графы. Наибольшее число ребер в графах с наследственным свойством. Наибольшее число ребер в планарных графах. Наибольшее число ребер в графах без полного подграфа с n вершинами.
+
Лектор - [[Романов Дмитрий Сергеевич]]
  
−
[[Media:ivtg-l7-selezn.pdf|'''Лекция 7''']]. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея.
+
==Часть 3==
  
−
[[Media:ivtg-l8-selezn.pdf|'''Лекция 8''']]. Сеть. Поток в сети. Теорема о величине максимального потока в сети. Построение максимального потока в сети.
+
'''Структурные свойства графов'''  
  
−
[[Media:ivtg-l9-selezn.pdf|'''Лекция 9''']]. Труднорешаемые графовые задачи распознавания. NP-полнота задачи k-раскраски графов при каждом заданном числе k \ge 3.
+
Лектор - [[Селезнева Светлана Николаевна]]
  
 +
'''Программа 3 части'''
  
−
'''Литература к части 3'''
+
*Графы. Простейшие свойства графов. Деревья. Свойства деревьев. Остовные деревья. Число остовных деревьев. Оценки числа висячих вершин в остовном дереве. Достижимость промежуточного числа висячих вершин в остовном дереве.
 +
*Связность, компоненты связности. Разделяющие вершины и разделяющие ребра (мосты). Свойства разделяющих вершин и ребер. Двусвязность и реберная двусвязность. Свойства двусвязных и реберно двусвязных графов. Разложение связного графа на компоненты двусвязности.
  
−
1. Основная литература
+
'''Литература''' к части 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.
  
−
2. Дополнительная литература
+
3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.

Текущая версия на 18:10, 11 декабря 2023

Обязательный курс для студентов 418 группы

Лекции 3 ч в неделю, отчетность - экзамен.

Лекторы - Романов Дмитрий Сергеевич, Селезнева Светлана Николаевна.

Часть 1

Алгебраические свойства графов

Лектор - Романов Дмитрий Сергеевич

Часть 2

Перечисления графов

Лектор - Романов Дмитрий Сергеевич

Часть 3

Структурные свойства графов

Лектор - Селезнева Светлана Николаевна

Программа 3 части

  • Графы. Простейшие свойства графов. Деревья. Свойства деревьев. Остовные деревья. Число остовных деревьев. Оценки числа висячих вершин в остовном дереве. Достижимость промежуточного числа висячих вершин в остовном дереве.
  • Связность, компоненты связности. Разделяющие вершины и разделяющие ребра (мосты). Свойства разделяющих вершин и ребер. Двусвязность и реберная двусвязность. Свойства двусвязных и реберно двусвязных графов. Разложение связного графа на компоненты двусвязности.

Литература к части 3

1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009.

2. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.

3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.

Источник — «https://mk.cs.msu.ru/index.php?title=Избранные_вопросы_теории_графов&oldid=10827»