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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Часть 3)
(Часть 3)
Строка 25: Строка 25:
 
Лектор - [[Селезнева Светлана Николаевна]]
 
Лектор - [[Селезнева Светлана Николаевна]]
  
'''Программа''' части 3
 
 
* Графы. Изоморфизм графов. Пути и циклы. Связность. Простейший свойства графов. Обходы графов. Деревья. Свойства деревьев. Остовные деревья. Число остовных деревьев в полном графе. Достижимость промежуточного числа висячих вершин в остовных деревьях. Число висячих вершин в остовных деревьях. Непересекающиеся остовные деревья.
 
* Разделяющие вершины в графе. Свойства разделяющих вершин. Двусвязные графы. Свойства двусвязных графов. Мосты в графе. Свойства мостов. Реберно двусвязные графы их свойства. Компоненты двусвязности графа. Свойства компонент двусвязности. Разложение графа на компоненты двусвязности. Дерево компонент двусвязности и разделяющих вершин графа.
 
 
'''Лекции'''
 
 
'''Лекция 1'''. Графы. Простейшие свойства графов. Цепи и циклы в графах. Связность. Обходы графов.
 
 
'''Лекция 2''' Деревья. Свойства деревьев. Остовные деревья в графе. Реберно непересекающиеся остовные деревья в графе.
 
 
'''Лекция 3'''. Деревья. Остовные деревья. Число остовных деревьев в полном помеченном графе. Достижимость промежуточного числа висячих вершин в остовном дереве. Оценка числа висячих вершин в остовном дереве.
 
 
'''Лекция 4'''. Двусвязность. Разделяющие вершины и мосты. Многосвязность графа. Свойства двусвязных и реберно двусвязных графов.
 
 
'''Лекция 5'''. Двусвязность. Компоненты двусвязности связного графа. Поиск разделяющих вершин в связном графе. Дерево компонент двусвязности и разделяющих вершин связного графа.
 
  
 
'''Литература''' к части 3
 
'''Литература''' к части 3

Версия 13:22, 23 января 2023

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

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

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

Часть 1

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

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

Часть 2

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

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

Часть 3

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

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


Литература к части 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 мин) и отвечает на вопрос билета, после чего проводится опрос по темам этой части (определения, формулировки теорем, основные идеи доказательств).