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

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