Изменения

== Основные определения теории графов Амортизационный анализ ==* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, циклАмортизационный анализ]]* [[Лемма о рукопожатияхДинамический массив]]* [[Ориентированный графHashed Array Tree]]<tex>^\star</tex>* [[Лемма о рукопожатиях#Вариант леммы о рукопожатиях для ориентированного графа|Вариант леммы о рукопожатиях для ориентированного графаСписок]]* [[Теорема о существовании простого пути в случае существования путиСтек]]* [[Теорема о существовании простого цикла в случае существования циклаОчередь]]* [[Матрица смежности графаДек]]* [[Связь степени матрицы смежности и количества путейМажорирующий элемент]]* [[Матрица инцидентности графаСчетчик Кнута]]* [[Циклическое пространство графаМастер-теорема]]<tex>^\star</tex>* [[Фундаментальные циклы графа]]* [[Дерево, эквивалентные определенияList order maintenance]]<tex>^\star</tex>

== Связность в графах Персистентные структуры данных ==* [[Отношение связности, компоненты связностиПерсистентные структуры данных]]* [[Отношение реберной двусвязностиПерсистентный стек]]* [[Отношение вершинной двусвязностиПерсистентная очередь]]* [[Граф компонент реберной двусвязностиПерсистентный дек]]* [[Граф блоков-точек сочленения]]* [[Точка сочленения, эквивалентные определения]]* [[Мост, эквивалентные определения]]* [[k-связность]]* [[Теорема Менгера]]* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершиныПерсистентная приоритетная очередь]]

== Остовные деревья [[Приоритетные очереди]] ==* [[Матрица КирхгофаДвоичная куча]]* [[Биномиальная куча]]* [[Фибоначчиева куча]]* [[Связь матрицы Кирхгофа и матрицы инцидентностиЛевосторонняя куча]]* [[Подсчет числа остовных деревьев с помощью матрицы КирхгофаТонкая куча]]* [[Количество помеченных деревьевТолстая куча на избыточном счетчике]]* [[Коды ПрюфераКуча Бродала-Окасаки]]<tex>^\star</tex>

== Обходы графов Система непересекающихся множеств ==* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфовСНМ (наивные реализации) | Наивные реализации]]* [[Покрытие ребер графа путямиСНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]* [[Алгоритм построения Эйлерова циклаСНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]* [[Произвольно вычерчиваемые из заданной вершины графы]]* [[Гамильтоновы графы]]* [[Теорема Хватала]]* Следствия теоремы Хватала: ** [[Теорема Дирака]]** [[Теорема Оре]]* [[Турниры]]* [[Теорема Редеи-КамионаСНМ с операцией удаления за О(1)]]<tex>^\star</tex>

== Укладки графов [[Поисковые структуры данных]] ==* [[Укладка графа на плоскостиУпорядоченное множество]]* [[Формула ЭйлераДерево поиска, наивная реализация]]* [[Непланарность K5 и K3,АВЛ-дерево]]* [[2-3|Непланарность дерево]]* [[B-дерево]]* [[B+-дерево]]* [[Красно-черное дерево]]* [[Декартово дерево]]* [[Декартово дерево по неявному ключу]]* [[Splay-дерево]]* [[Взвешенное дерево]]* [[Tango-дерево]]<tex>K_5^\star</tex> и * [[Рандомизированное бинарное дерево поиска]]* [[Дерево ван Эмде Боаса]]* [[Список с пропусками]]* [[Fusion tree]]<tex>K_{3,3}^\star</tex>]]* [[Укладка дереваСверхбыстрый цифровой бор]]* [[Укладка графа с планарными компонентами реберной двусвязностиRope]]<tex>^\star</tex>* [[Укладка графа с планарными компонентами вершинной двусвязностиAA-дерево]]<tex>^\star</tex>* [[Теорема Понтрягина-КуратовскогоТехника частичного каскадирования]]<tex>^\star</tex>* [[Двойственный граф планарного графаCentroid decomposition]]<tex>^\star</tex>

== Раскраски графов Запросы на отрезках ==* [[Раскраска графа]]* [[Двудольные графы и раскраска в 2 цвета]]* [[Хроматический многочлен]]** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленов]]** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность]]* [[Формула Зыкова]]* [[Формула Уитни]]

== Обход в глубину = Корневая эвристика ===* [[Обход в глубину, цвета вершинСтатистики на отрезках. Корневая эвристика]]* [[Лемма о белых путях]]* [[Использование обхода в глубину для проверки связности]]* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]* [[Использование обхода в глубину для топологической сортировки]]* [[Использование обхода в глубину для поиска компонент сильной связности]]* [[Использование обхода в глубину для поиска точек сочленения]]* [[Построение компонент вершинной двусвязности]]* [[Использование обхода в глубину для поиска мостовКорневая декомпозиция с операциями: get, insert, erase]]* [[Построение компонент реберной двусвязностиАлгоритм Мо]]

== Кратчайшие пути в графах = Дерево отрезков ===* [[Обход Дерево отрезков. Построение]]* [[Реализация запроса в ширинудереве отрезков сверху]]* [[Алгоритм Форда-БеллманаРеализация запроса в дереве отрезков снизу]]* [[Алгоритм ДейкстрыНесогласованные поддеревья. Реализация массового обновления]]* [[Алгоритм ФлойдаМногомерное дерево отрезков]]* [[Алгоритм ДжонсонаСжатое многомерное дерево отрезков]]

== Остовные деревья Дерево Фенвика ==* [[Лемма о безопасном ребреДерево Фенвика]]* [[Алгоритм ПримаВстречное дерево Фенвика]]* [[Алгоритм КраскалаДерево Фенвика для некоммутативных операций]]* [[Теорема Тарьяна|Теорема Тарьяна (критерий минимальности остовного дерева)]]* [[Алгоритм двух китайцевМногомерное дерево Фенвика]]

== Задача о паросочетании наименьшем общем предке ==* [[Теорема о максимальном паросочетании и дополняющих цепяхСведение задачи LCA к задаче RMQ]]* [[Сведение задачи RMQ к задаче LCA]]* [[Метод двоичного подъема]]* [[Решение RMQ с помощью разреженной таблицы]]* [[Двумерная разреженная таблица]]* [[Алгоритм ФордаФарака-Фалкерсона для поиска максимального паросочетанияКолтона и Бендера]](решение +/-1 RMQ с помощью метода четырех русских)* [[Алгоритм Куна для поиска максимального паросочетанияХьюи]]* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графахHeavy-light декомпозиция]]* [[Связь вершинного покрытия и независимого множестваАлгоритм Шибера-Вишкина]]<tex>^\star</tex>* [[Матрица Татта и связь с размером максимального паросочетания Алгоритм Тарьяна поиска LCA за O(1) в двудольном графеоффлайн]]<tex>^\star</tex>* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветийLink-Cut Tree]]<tex>^\star</tex>* [[Rake-Compress деревья]]<tex>^\star</tex>

== Задача о максимальном потоке Хеширование ==* [[Определение сети, потока]]* [[Разрез, лемма о потоке через разрез]]* [[Дополняющая сеть, дополняющий путь]]* [[Лемма о сложении потоков]]* [[Теорема Форда-Фалкерсона]]* [[Алгоритм ФордаХеш-Фалкерсона, реализация с помощью поиска в глубинутаблица]]* [[Алоритм Эдмондса-КарпаРазрешение коллизий]]* [[Теорема о декомпозицииХеширование кукушки]]* [[Теорема о декомпозиционном барьереИдеальное хеширование]]* [[Блокирующий потокПерехеширование]]* [[Схема алгоритма ДиницаФильтр Блума]]* [[Алгоритм поиска блокирующего потока в ациклической сетиQuotient filter]]<tex>^\star</tex>* [[Алгоритм масштабирования потокаУниверсальное семейство хеш-функций]]* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностямиРасширяемое хеширование]]<tex>^\star</tex>

== Задача о потоке минимальной стоимости [[Сортировки]] ===== Квадратичные сортировки ===* [[Сортировка выбором]]* [[Сортировка пузырьком]]* [[Сортировка вставками]]=== Сортировки на сравнениях ===* [[Поток минимальной стоимостиСортировка Шелла]]<tex>^\star</tex>* [[Теорема Форда-Фалкерсона о потоке минимальной стоимостиСортировка кучей]]* [[Быстрая сортировка]]* [[Сортировка слиянием]]* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сетиCортировка слиянием с использованием O(1) дополнительной памяти]]* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимостиТерпеливая сортировка]]<tex>^\star</tex>* [[Использование потенциалов Джонсона при поиске потока минимальной стоимостиTimsort]]<tex>^\star</tex>* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимостиSmoothsort]]<tex>^\star</tex>* [[Венгерский алгоритм решения задачи Теорема о назначенияхнижней оценке для сортировки сравнениями]]

== Поиск подстроки в строке = Многопоточные сортировки ===* [[Многопоточная сортировка слиянием]]<tex>^\star</tex>* [[PSRS-сортировка]]<tex>^\star</tex>=== Другие сортировки ===* [[Наивный алгоритм поиска подстроки в строкеПоиск k-ой порядковой статистики]]* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабинаk-Карпаой порядковой статистики за линейное время]]* [[Поиск наибольшей общей подстроки k-ой порядковой статистики в двух строк с использованием хешированиямассивах]]<tex>^\star</tex>* [[Префикс-функцияСортировка подсчетом]]* [[Алгоритм Кнута-Морриса-ПраттаЦифровая сортировка]]* [[Z-функцияКарманная сортировка]]* [[Автомат для поиска образца в текстеСортировка Хана]]<tex>^\star</tex>* [[БорЗадача флага Нидерландов]]<tex>^\star</tex>* [[Алгоритм Ахо-КорасикБлинная сортировка]]<tex>^\star</tex>

== Словарные структуры данных Сортирующие сети ==* [[Суффиксный борСортирующие сети]]* [[Сжатое суффиксное дерево0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]* [[Алгоритм УкконенаСортирующие сети для квадратичных сортировок]]* [[Сортировочные сети с особыми свойствами]]<tex>^\star</tex>* [[Сеть Бетчера]]

== Алгоритмы поиска ==* [[Целочисленный двоичный поиск]]* [[Поиск в матрице]]<tex>^\star</tex>* [[Вещественный двоичный поиск]]* [[Троичный поиск]]* [[Поиск с помощью золотого сечения]]* [[Интерполяционный поиск]]* [[Метод Фибоначчи]]<tex>^\star</tex> == [[Динамическое программирование]] ===== Классические задачи динамического программирования ===*[[Кратчайший путь в ациклическом графе]]*[[Задача о наименьшем общем предке числе путей в ациклическом графе]]*[[Задача о расстановке знаков в выражении]]*[[Задача о порядке перемножения матриц]]*[[Задача о наибольшей общей подпоследовательности]]*[[Задача о наибольшей возрастающей подпоследовательности]]*[[Быстрый поиск наибольшей возрастающей подпоследовательности]]**[[Задача коммивояжера, ДП по подмножествам]]*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]*[[Задача о рюкзаке]] === Способы оптимизации методов динамического программирования ===* [[Метод двоичного подъемачетырех русских для умножения матриц]]* [[Сведение Применение метода четырех русских в задачах ДП на примере задачи LCA к задаче RMQо НОП]]<tex>^\star</tex>* [[Решение RMQ Задача об оптимальном префиксном коде с помощью разреженной таблицысохранением порядка. Монотонность точки разреза]]*[[Meet-in-the-middle]]<tex>^\star</tex>*[[Convex hull trick]] === Другие задачи ===* [[Алгоритм ФаракаЗадача о расстоянии Дамерау-Колтона и БендераЛевенштейна]] (решение +<tex>^\star</tex>*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]*[[Задача о наибольшей подпоследовательности-1 RMQ с помощью метода четверых русских)палиндроме]]*[[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>*[[Динамическое программирование по профилю]]<tex>^\star</tex>*[[Динамика по поддеревьям]]* [[Сведение задачи RMQ к задаче LCALevel Ancestor problem]]

== Суффиксный массив Криптографические алгоритмы ==* [[Суффиксный массив]]* [[Построение суффиксного массива с помощью стандартных методов сортировки]]* [[Алгоритм цифровой сортировки]]* [[Алгоритм цифровой сортировки суффиксов циклической строки]]* [[Алгоритм Касаи и др.]]* [[Алгоритм поиска подстроки в строке с помощью суффиксного массиваRSA]]

== Матроиды Связь между структурами данных ==* [[Определение матроида]]* [[Примеры матроидов]]* [[Прямая сумма матроидов]]* [[Теорема Радо-Эдмондса (жадный алгоритм)]]* [[Жадный алгоритм поиска базы минимального веса]]* [[Теорема о базах]]* [[Аксиоматизация матроида базами]]* [[Теорема о циклах]]* [[Аксиоматизация матроида циклами]]* [[Ранговая функция, полумодулярность]]* [[Двойственный матроид]]* [[Оператор замыкания для матроидов]]* [[Пересечение матроидов, определение, примеры]]* [[Лемма о паросочетании в графе замен]]* [[Лемма о единственном паросочетании в графе замен]]* [[Граф замен для двух матроидов]]* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]* [[Алгоритм построения базы в пересечении матроидов]]* [[Теорема Эдмондса-Лоулера]]* [[Объединение матроидов, проверка множества на независимость]]* [[Объединение матроидов, доказательство того, что объединение является матроидом]]* [[Алгоритм построения базы в объединении матроидовСвязь между структурами данных]]