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

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

Текущая версия на 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»