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

Вид материала

Документы

Содержание Базовые курсы P”, “Почти нет графов со свойством P

Подобный материал:

• Лекций: 34 Практических: 18 Лабораторных: 0 taс. 9 Теория автоматического управления, 21.9kb.
• Лекций: 34 Практических: 34 Лабораторных: 0 tfkv. 4 Теория функций комплексного переменного., 21.85kb.
• Лекций: 22 Практических: 0 Лабораторных: 14 Динамика роботов и манипуляторов ects, 18kb.
• Лекций: 34 Практических: 0 Лабораторных: 0 em введение в математику ects, 14.77kb.
• Ж. Д. Транспорта РФ петербургский государственный университет путей сообщения, 180.1kb.
• Лекций: 24 Практических: 0 Лабораторных 10 Вариационные методы в механике деформируемого, 18.67kb.
• Лекций: 34 Практических: 18 Лабораторных: 0 sm. 5 Сопротивление материалов и основы, 22.99kb.
• Лекций: 34 Практических: 34 Лабораторных sme. 8 Статистические методы в экономике ects, 22.52kb.
• Лекций: 34 Практических: 34 Лабораторных sme. 9 Статистические методы в экономике ects, 22.54kb.
• Лекций: 18 Практических: 16 Лабораторных: 0 end. 9 Модели плоскости Лобачевского ects:, 15.95kb.

Лекций: 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.
Экзаменационная методика	Зачёт и экзамен
Рекомендуется	для студентов четвертого курса механико-математического факультета
Примечания