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

Версия 13:34, 12 сентября 2023

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

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

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

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

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

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

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

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

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

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

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

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

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

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

@@ Строка 24: / Строка 24: @@
 Лектор - [[Селезнева Светлана Николаевна]]
+'''Программа 3 части'''
+# Графы. Простейшие свойства графов. Деревья. Свойства деревьев. Остовные деревья. Число остовных деревьев. Оценки числа вершин в остовном дереве. Достижимость промежуточного числа висячих вершин в остовном дереве.
+# Связность, компоненты связности. Разделяющие вершины и разделяющие ребра (мосты). Свойства разделяющих вершин и ребер. Двусвязность и реберная двусвязность. Свойства двусвязных и реберно двусвязных графов. Разложение связного графа на компоненты двусвязности.
 '''Литература''' к части 3