Информация о курсе
В курсе излагаются основные понятия теории графов. Описаны методы решения задач. Сделана попытка, в популярной форме познакомить читателя с некоторыми приложениями теории графов.

Материал организован так, что знакомство с графами происходит в процессе решения самых разнообразных задач, в формулировках условий которых не упоминаются графы. Для решения их требуется увидеть возможность перевести условие на язык графов, решить задачу внутри теории графов, интерпретировать получение решение в исходных терминах. Если в начале курса рассматриваются приложения частного характера, иллюстрирующие теорию графов и ее связь с жизнью, то вторая половина книги посвящена прикладным разделам теории графов, имеющим практическое значение в экономике и управлении.

Лекции		Описание
1.	Основные понятия теории графов	Определение графа. Определение орграфа. Полный граф. Полный ориентированный граф. Двудольный граф. Степень вершины. Связность графа. Задачи, приводящие к графам
2.	Некоторые определения теории графов	Определения и примеры. Удаление ребер, мосты. Деревья. Перечисление деревьев.
3.	Представления о планарном графе	Плоский граф. Гомеоморфные графы. Формула Эйлера. Триангулированный граф. Задачи.
4.	Эйлеровы графы	Эйлеровы графы. Лабиринты. Геометрическая постановка задачи о лабиринтах. Решение задачи о лабиринтах.
5.	Гамильтоновы графы	Гамильтоновы графы. Теорема Дирака.
6.	Бесконечные графы	Бесконечные графы. Краткий обзор свойств бесконечных эйлеровых графов.
7.	Графы с цветными ребрами	Реберная раскраска. Задачи на графы с цветными ребрами и вытекающие из них свойства. Задача о несцепленных треугольниках с одноцветными сторонами.
8.	Раскрашивание графов	Хроматическое число. Гипотеза о четырех красках. Раскрашивание карт.
9.	Орграфы	Определения. Эйлеровы и гамильтоновы орграфы. Турниры.
10.	Цепи Маркова	Еще раз об ориентированных графах. Задачи на круговые бескомпромиссные турниры. Цепи Маркова.
11.	О деревьях	Представления деревьев. Представление с помощью матрицы смежности. Представление с помощью списков смежности. Представление с помощью списка ребер и кода Прюфера. Алгоритм построения кода Прюфера. Алгоритм раскодирования. Уровневые коды корневых деревьев. Перечисление и подсчет деревьев. Непомеченные деревья. Ориентированные деревья. Каркасы в неориентированном графе. Каркасы в ориентированных графах.
12.	Каркасы и изоморфизм деревьев	Каркас неориентированного графа. Нахождение каркасов в графе. Алгоритм Краскала. Изоморфизм деревьев.
13.	Деревья, вероятность и генетика	Поиск кратчайшего пути. Вероятность и генетика.
14.	Сетевое планирование и управление	Введение. Сетевой график. Правила построения сетевого графика. Анализ сетевой модели. Определение критического пути. Определение полного резерва времени ненапряженного пути. Формирование временных оценок работ.
15.	Паросочетания и свадьбы	Паросочетания и свадьбы. Теорема Холла о свадьбах. Приложение теоремы Холла. Латинские квадраты.
16.	Теория трансверсалей	Теория трансверсалей. Приложение теории трансверсалей.
17.	Потоки в сетях
	Предметный указатель На главную