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