Программа дисциплины «теория графов»

«ТЕОРИЯ ГРАФОВ»

№ темы	Количество часов
Содержание курса	Лекции	Лабораторные занятия
1	2	3
Раздел 1. Введение	10	10
1.1. Исторический обзор. Первоначальные понятия теории графов. Изоморфизм. Подграфы.	2	2
1.2. Маршруты, цепи, циклы. Связные компоненты. Связь между числами вершин, ребер и компонент графа.	2	3
1.3. Способы задания графов. Матрицы, ассоциированные с графом. Метрические инварианты. Минимаксные задачи размещения.	2	2
1.4. Двудольные графы. Теорема Кёнига. Распознавание двудольности. Волновой алгоритм.	4	3
Раздел 2. Деревья	6	6
2.1. Эквивалентные определения дерева. Центр дерева, алгоритм Жордана.	2	3
2.2. Остов графа. Теорема Кирхгофа о числе остовов. Нахождение остова минимального веса, алгоритм Краскала. Остовы и матрица инцидентности.	4	3
Раздел 3. Независимость и покрытия	10	10
3.1. Вершинная независимость. Оценки числа независимости. О сложности алгоритмических задач. Априорные оценки погрешностей алгоритмов. Задача “Независимое множество вершин графа” – формулировка, сложность. Быстрый алгоритм с априорной оценкой погрешности. Клика. Граф клик. Модульное произведение. Связь проблем “Клика”, “Изоморфная вложимость”, “Изоморфизм”.	4	4
3.2. Вершинные и реберные покрытия. Паросочетания, их связь с покрытиями. Паросочетания в двудольных графах, теорема Холла. Связь между числами паросочетания и вершинного покрытия в двудольном графе. Теорема Кенига о бинарных матрицах.	6	6
Раздел 4. Обходы графов	8	8
4.1. Эйлеровы циклы. Критерий эйлеровости. Алгоритм Флёри.	4	4
4.2. Гамильтоновы циклы. Достаточные условия гамильтоновости.	4	4
Раздел 5. Связность	6	4
5.1. Числа вершинной и реберной связности. Дерево блоков и точек сочленения. k-Компоненты. Процедура построения произвольного 2-связного графа.	4	3
5.2. Сепараторы. Теорема Менгера.	2	1
Раздел 6. Циклы и разрезы в графе	8	5
6.1. Поле F2 из двух элементов, его особая роль в комбинаторике. Булеан B(X) конечного m-элементного множества X как линейное пространство над F2. Системы линейных однородных уравнений над F2.	2	1
6.2. Особенности матрицы инцидентности I(G) графа G = (V, E), рассматриваемой как матрица над F2. Булеан B(E) как линейное пространство над F2, его размерность, базис. Координаты вектора и столбцы матрицы инцидентности.	2	1
6.3. Пространство циклов C(G), его размерность, базис. Связь пространства C(G) с пространством решений однородной системы линейных уравнений I(G) X = 0. Фундаментальная система циклов.	2	2
6.4. Пространство разрезов C(G), аналогия с пространством циклов. Фундаментальная система разрезов. Матрица фундаментальных циклов M(G) и разрезов M(G), их одновременное вычисление, исходя из матрицы I(G).	2	1
Раздел 7. Графические последовательности	12	7
7.1. Степенная последовательность графа. Графическая последовательность, ее реализации. Критерий графичности Гавела-Хакими.	2	1
7.2. Алгоритм построения реализации графической последовательности. Реализации с предписанными свойствами.	2	1
7.3. Расщепляемые графы. Критерий расщепляемости.	2	2
7.4. Пороговые графы, их распознавание и структура.	4	2
7.5. Степенное множество графа.	2	1
Раздел 8. Асимптотические свойства графов	4	2
8.1. Асимптотические свойства “Почти все графы имеют свойство P”, “Почти нет графов со свойством P”. Примеры таких свойств.	4	2
Раздел 9. Заключение.	4	–
9.1. Проблемы теории графов.	4
Всего аудиторных часов	68	52
ИТОГО:	120

1. 
   Берж К. Теория графов и ее применение. — М.: ИЛ, 1962.
   
2. 
   Дистель Р. Теория графов. — Новосибирск: Изд-во Института математики, 2002.
   
3. 
   Зыков А.А. Основы теории графов. — М.: Наука, 1987.
   
4. 
   Оре О. Теория графов. — М.: Наука, 1980.
   
5. 
   Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984.
   
6. 
   Татт У. Теория графов. — М.: Мир, 1988.