Реферат: Программа дисциплины Теория графов Семестр

Направление 010100 Математика


Профиль Дискретная математика и приложения


Степень бакалавр


Программа

дисциплины Теория графов


Семестр 5


Цель дисциплины:

Изучение основ теории графов.


Задачи дисциплины:

ознакомить студентов с базовыми понятиями, методами и результатами теории графов;

ознакомить студентов с теоретико-графовыми алгоритмами решения различных комбинаторных задач и приложениями теории графов.


Разделы курса, темы, их краткое содержание


Маршруты, связность, циклы и разрезы. Матрицы, ассоциированные с графом.

Деревья, деревья в графах, остовы, теорема Кирхгофа.

Обходы графов, эйлеровы и гамильтоновы графы.

Матроиды и решетки, различные характеризации матроидов. Жадный алгоритм. Двойственный матроид.

Пространство циклов бинарного матроида. Пространства циклов и разрезов графа, их ортогональность.

Монотонные полумодулярные функции, индуцированный матроид. Трансверсальные матроиды и их приложения.

Дизъюнктное объединение и сумма матроидов, покрытия матроидов базами, покрытия графов остовами, число древовидности.

Блоки и точки сочленения, дерево блоков и точек сочленения связного графа.

Формула Эйлера для плоских графов и ее следствие для многогранников. Планарные графы, теоремы Понтрягина-Куратовского и Вагнера-Харари-Татта.

Двойственные графы, матроидная характеризация планарных графов, теорема Уитни.

Раскраски графов, теоремы Брукса и Хивуда. Приложения раскрасок графов в радиоэлектронике.

Хроматические многочлены и их свойства, теоремы Зыкова и Уитни.