Теория графов и комбинаторика

СОДЕРЖАНИЕ

Теоретико-множественное введение

Определение графа. Вершины и ребра. Графическая интерпретация графа. Смежность и инцидентность. Локальная степень. Подграф. Полный граф. Матрицы смежностей и инциденций. Изоморфизм графов.

Путь в графе и связные компоненты графа. Цепи, простые цепи, циклы, простые циклы. Операции удаления вершины, удаления ребра, подразбиения ребра. Дерево и его особенности.

Эйлеров цикл и эйлеров граф. Условия существования эйлерова цикла. Задача о разбиении графа на минимальное число цепей.

Гамильтонов цикл и гамильтонов граф. Условия Дирака, Оре и Поша, гарантирующие существование в графе гамильтонова цикла.

Формулировка теоремы Менгера (вершинный и реберный варианты), теорема Холла о системах различных представителей и теорема Кёнига о независимых клетках в матрице.

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

Цепи и антицепи в частично-упорядоченном множестве. Теорема Дилворта. Алгоритм разбиения частично-упорядоченного множества на минимальное число цепей.

Планарные и плоские графы. Формулировки теоремы Понтрягина-Куратовского и теоремы Эйлера о соотношении чисел граней, ребер и вершин плоского графа.

Раскраска графа. Формулировка теоремы о пяти красках. Хроматическое число и алгоритм Зыкова вычисления хроматического многочлена графа.

Взвешенный граф. Кратчайшие пути во взвешенном графе и алгоритм Форда построения кратчайших маршрутов.

Остов в графе и алгоритм Краскала поиска остова минимального веса во взвешенном графе.

Ориентированный граф и его графическая интерпретация.Локальные степени. Матрица смежностей. Ориентированные пути и связность в ориентированном графе.

Сети и потоки в сетях. Стационарные потоки. Алгоритм Форда-Фалкерсона поиска максимального стационарного потока.

Перестановки, размещения и сочетания. Бином Ньютона и иллюстративные примеры.

Метод включения-исключения перечисления элементов множества, не обладающих заданными свойствами. Задача о беспорядках и задача о встречах.

Формальные степенные ряды и действия над ними. Производящие функции последовательностей.

Линейные рекуррентные соотношения и их решение с помощью производящих функций. Числа Фибоначчи.