Реферат: Лекций: 34 Практических: 0 Лабораторных: 17 tg. 7 Теория графов II ects: 3

Лекций: 34

Практических: 0

Лабораторных: 17
TG.7 Теория графов II
ECTS: 3

Лектор

Доктор физико-математических наук, профессор кафедры уравнений математической физики Тышкевич Р.И.

Цель курса

Обучение студентов основам теории графов и ознакомление с ее приложениями.

Образовательная цель: Изложение ряда базовых разделов теории графов и их приложений, обучение решению задач из соответствующих разделов.

Развивающая цель: Дальнейшее формирование у студентов навыков дискретного математического мышления и умения применять его в конкретных задачах.

^ Базовые курсы

Необходимо иметь понятие об общей теории отображений, начальных сведениях теории множеств и линейной алгебры.

Содержание

Числа вершинной и реберной связности. Дерево блоков и точек сочленения. k-Компоненты. Процедура построения произвольного 2-связного графа. Сепараторы. Теорема Менгера.

Поле F2 из двух элементов, его особая роль в комбинаторике. Булеан B(X) конечного m-элементного множества X как линейное пространство над F2. Системы линейных однородных уравнений над F2. Особенности матрицы инцидентности I(G) графа G = (V, E), рассматриваемой как матрица над F2. Булеан B(E) как линейное пространство над F2, его размерность, базис. Координаты вектора и столбцы матрицы инцидентности. Пространство циклов C(G), его размерность, базис. Связь пространства C(G) с пространством решений однородной системы линейных уравнений I(G) X = 0. Фундаментальная система циклов. Пространство разрезов C(G), аналогия с пространством циклов. Фундаментальная система разрезов. Матрица фундаментальных циклов M(G) и разрезов M(G), их одновременное вычисление, исходя из матрицы I(G).

Степенная последовательность графа. Графическая последовательность, ее реализации. Критерий графичности Гавела-Хакими. Алгоритм построения реализации графической последовательности. Реализации с предписанными свойствами. Расщепляемые графы. Критерий расщепляемости. Пороговые графы, их распознавание и структура. Степенное множество графа.

Асимптотические свойства “Почти все графы имеют свойство ^ P”, “Почти нет графов со свойством P”. Примеры таких свойств.

Методика преподавания

Лекции и лабораторные занятия

Литература

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

2.  Дистель Р. Теория графов. Новосибирск: Изд-во Института математики. 2002.

Экзаменационная методика

Зачёт и экзамен

Рекомендуется

для студентов четвертого курса механико-математического факультета

Примечания