Алгоритмы и структуры данных
Основные определения теории графов
- Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
- Лемма о рукопожатиях
- Ориентированный граф
- Вариант леммы о рукопожатиях для ориентированного графа
- Теорема о существовании простого пути в случае существования пути
- Теорема о существовании простого цикла в случае существования цикла
- Матрица смежности графа
- Связь степени матрицы смежности и количества путей
- Матрица инцидентности графа
- Циклическое пространство графа
- Фундаментальные циклы графа
- Дерево, эквивалентные определения
Связность в графах
- Отношение связности, компоненты связности
- Отношение реберной двусвязности
- Отношение вершинной двусвязности
- Граф компонент реберной двусвязности
- Граф блоков-точек сочленения
- Точка сочленения, эквивалентные определения
- Мост, эквивалентные определения
- k-связность
- Теорема Менгера
- Вершинная, реберная связность, связь между ними и минимальной степенью вершины
Остовные деревья
Обходы графов
Укладки графов
Раскраски графов
Обход в глубину
- Обход в глубину, цвета вершин
- Лемма о белых путях
- Использование обхода в глубину для проверки связности
- Использование обхода в глубину для поиска цикла в ориентированном графе
- Использование обхода в глубину для топологической сортировки
- Использование обхода в глубину для поиска компонент сильной связности
- Использование обхода в глубину для поиска точек сочленения
- Построение компонент вершинной двусвязности
- Использование обхода в глубину для поиска мостов
- Построение компонент реберной двусвязности
Кратчайшие пути в графах
Остовные деревья
Задача о паросочетании
- Теорема о максимальном паросочетании и дополняющих цепях
- Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
- Алгоритм Куна для поиска максимального паросочетания
- Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
- Связь вершинного покрытия и независимого множества
- Матрица Татта и связь с размером максимального паросочетания в двудольном графе
- Паросочетания в недвудольных графах. Алгоритм вырезания соцветий
Задача о максимальном потоке
- Определение сети, потока
- Разрез, лемма о потоке через разрез
- Дополняющая сеть, дополняющий путь
- Лемма о сложении потоков
- Теорема Форда-Фалкерсона
- Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
- Алоритм Эдмондса-Карпа
- Теорема о декомпозиции
- Теорема о декомпозиционном барьере
- Блокирующий поток
- Схема алгоритма Диница
- Алгоритм поиска блокирующего потока в ациклической сети
- Алгоритм масштабирования потока
- Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями
Задача о потоке минимальной стоимости
- Поток минимальной стоимости
- Теорема Форда-Фалкерсона о потоке минимальной стоимости
- Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
- Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
- Использование потенциалов Джонсона при поиске потока минимальной стоимости
- Сведение задачи о назначениях к задаче о потоке минимальной стоимости
- Венгерский алгоритм решения задачи о назначениях
Поиск подстроки в строке
- Наивный алгоритм поиска подстроки в строке
- Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа
- Поиск наибольшей общей подстроки двух строк с использованием хеширования
- Префикс-функция
- Алгоритм Кнута-Морриса-Пратта
- Z-функция
- Автомат для поиска образца в тексте
- Бор
- Алгоритм Ахо-Корасик
Словарные структуры данных
Задача о наименьшем общем предке
- Метод двоичного подъема
- Сведение задачи LCA к задаче RMQ
- Решение RMQ с помощью разреженной таблицы
- Алгоритм Фарака-Колтона и Бендера (решение +/-1 RMQ с помощью метода четверых русских)
- Сведение задачи RMQ к задаче LCA
Суффиксный массив
Матроиды
- Определение матроида
- Примеры матроидов
- Прямая сумма матроидов
- Теорема Радо-Эдмондса (жадный алгоритм)
- Жадный алгоритм поиска базы минимального веса
- Теорема о базах
- Аксиоматизация матроида базами
- Теорема о циклах
- Аксиоматизация матроида циклами
- Ранговая функция, полумодулярность
- Двойственный матроид
- Примеры матроидов: графовый матроид
- Оператор замыкания для матроидов
- Пересечение матроидов, определение, примеры
- Теорема Эдмондса - Лоулера, формулировка, док-во в простую сторону
- Лемма о паросочетании в графе замен
- Лемма о единственном паросочетании в графе замен
- Граф замен для двух матроидов
- Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем
- Доказательство теоремы Эдмондса-Лоулера
- Объединение матроидов, проверка множества на независимость
- Объединение матроидов, доказательство того, что объединение является матроидом
