Свойства: рефлексивность, симметричность, транзитивность, антирефлексивность, антисимметричность, асимметричность. При проверке свойств отсутствие свойства доказывается приведением одного контр-примера. Наличие свойства доказывается отсутствием контр-примеров.
Представление отношения в виде матрицы и в виде графа.
Проверка свойств отношений на основе матрицы и на основе графа отношения.
Отношения эквивалентности и классы эквивалентности.
Отношения строгого и нестрогого порядка. Частичный и линейный порядок. Задача топологической сортировки и простейший алгоритм топологической сортировки с повторением поиска минимального элемента.
Транзитивное замыкание: определение.
Неориентированный граф и основные понятия: вершины, рёбра, степень вершины.
Пути в графе: замкнутый и незамкнутый путь, простой путь. Циклы и цепи.
Связные графы, компоненты связности. Мосты, точки сочленения.
Связь количества рёбер и суммы степеней вершин. Количество вершин нечётной степени чётно.
Деревья. В дереве есть хотя бы две висячие вершины. Количество рёбер и вершин в дереве.
Количество рёбер в полном графе.
Планарные графы. Формула Эйлера в случае связного и несвязных графов. Связь количества вершин и рёбер: $m \le 3n-6$. Непланарные графы $K_5$ и $K_{3,3}$, теорема Понтрягина-Куратовского.
Хроматизм
Раскраска графа. Определение двудольного графа и критерий двудольности (все циклы чётные).
Хроматическое число. Хроматическое число полного графа. Хроматическое число не больше максимальной степени вершин плюс один. Хроматическое число планарного графа не больше пяти (на самом деле — четырёх).
Хроматические многочлены. Формулы для вычисления хроматических многочленов: для пустого, полного графов, дерева, цикла ($\chi(C_n, k) = (k-1)^n+(-1)^n(k-1)$). Удаление вершины степени 1 и степени 2. Добавление или удаление ребра.
Свойства хроматического многочлена: старший коэффициент равен единице, степень многочлена равна количеству вершин. Коэффициент при предпоследней степени равен минус количеству рёбер. Знаки при коэффициентах чередуются. Младший коэффициент равен нулю.
Эйлеров цикл и эйлеров путь. Критерий наличия Эйлерова цикла (все степени чётные) и Эйлерова пути (все степени четные кроме, возможно, двух нечетных. Путь начинается и заканчивается в нечетных вершинах). Алгоритм построения Эйлерова цикла или пути.
Гамильтонов цикл и путь.
Длина пути в графе, радиус графа, диаметр графа, центр графа. Диаметр не больше двух радиусов. В дереве может быть не больше двух центров.
Длина путей в ориентированных графах. Пути между всеми парами вершин существуют равносильно отсутствию отрицательных циклов.
Представление графов в компьютере: матрицы смежности, списки смежности, неявное представление.
Алгоритмы поиска расстояний в графах
Алгоритмы Форда-Беллмана. Релаксация ребра. Требует только отсутствие отрицательных циклов. Инвариант шага алгоритма: после шага $n$ все расстояния, соответствующие путям из не более, чем $n$ ребер, вычислены верно. Восстановление пути.
Алгоритм Дейкстры. Требует положительных весов. Требует очередь с приоритетами для эффективной реализации. Инвариант шага алгоритма: после каждого шага все расстояния, соответствующие путям, где все вершины кроме последней обработаны, вычислены верно. Восстановление пути.
Алгоритмы Флойда (Флойда-Уоршалла). Инвариант шага алгоритма: после шага $n$ все расстояния, соответствующие путям с промежуточными вершинами от $1$ до $n$, вычислены верно. Восстановление пути.
Построение транзитивного замыкания с помощью алгоритма Флойда.
Потоки в сетях
Определение сети и определение потока в заданной сети.
Суммарный поток на рёбрах, выходящих из истока равен суммарному потоку на рёбрах, входящих в сток. Эта величина называется величина потока.
Разрез в сети. Прямые и обратные рёбра разреза. Величина разреза равна суммарной пропускной способности прямых ребер. Величина потока в сети равна суммарному потоку по прямым рёбрам разреза минус суммарный поток по обратным рёбрам разреза.
Величина любого потока не больше величины любого разреза. Следовательно, величина максимального потока не больше величины минимального разреза.
Теорема Форда-Фалкерсона: величина максимального потока равна величине максимального разреза (в случае целочисленной сети).
Дополнительный граф для потока в сети. Минимальный разрез как множество вершин, достижимых из истока в дополнительном графе.
Паросочетания в двудольном графе.
Определение паросочетания и максимального паросочетания.
Сведение задачи о поиске максимального паросочетания к задаче о поиске максимального потока.
Контролирующее множество. Построение контроллирующего множества с помощью минимального разреза, полученного методом Форда-Фалкерсона (Пересекаем левую долю со вторым множеством разреза, а правую долю — с первым). Вывод, что минимальное контролирующее множество совпадает по размеру с паросочетанием.
Обход графа в ширину и глубину.
Структуры данных стек и очередь.
Алгоритмы поиска в глубину (с помощью стека) и в ширину (с помощью очереди).
Полный поиск в глубину или ширину: совершаем поиск из произвольной непосещенной вершины, пока они еще есть.
Прямая и обратная нумерация вершин после поиска. Совпадение прямой и обратной нумерации в поиске в ширину.
Поиск в ширину эквивалентен алгоритму Дейкстры с ребрами веса 1.
Обратная нумерация в графе без циклов: если есть путь из $u$ в $v$, то номер первой — больше. Алгоритм топологической сортировки.
Отношение взаимной достижимости вершин в ориентированном графе, компоненты сильной связности. Граф конденсации. Утверждение о максимальных значениях вершин каждой компоненты сильной связности в обратной нумерации: если из компоненты $u_0$ есть путь в компоненту $v_0$, то максимальный номер в компоненте $u_0$ больше максимального номера в компоненте $v_0$. Алгоритм поиска компонент сильной связности.