== Основные определения теории графов ==* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]* [[Лемма о рукопожатиях]]* [[Теорема о существовании простого пути в случае существования пути]]* [[Теорема о существовании простого цикла в случае существования цикла]]* [[Матрица смежности графа]]* [[Связь степени матрицы смежности и количества путей]]* [[Матрица инцидентности графа]]* [[Циклическое пространство графа]]* [[Фундаментальные циклы графа]]* [[Дерево, эквивалентные определения]] == Связность в графах ==* [[Отношение связности, компоненты связности]]* [[Отношение реберной двусвязности]]* [[Отношение вершинной двусвязности]]* [[Граф компонент реберной двусвязности]]* [[Граф блоков-точек сочленения]]* [[Точка сочленения, эквивалентные определения]]* [[Мост, эквивалентные определения]]* [[k-связность]]* [[Теорема Менгера]]* [[Теорема Менгера, альтернативное доказательство]]* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] == Остовные деревья ==* [[Матрица Кирхгофа]]* [[Связь матрицы Кирхгофа и матрицы инцидентности]]* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]* [[Количество помеченных деревьев]]* [[Коды Прюфера]] == Обходы графов ==* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]* [[Покрытие ребер графа путями]]* [[Алгоритм построения Эйлерова цикла]]* [[Произвольно вычерчиваемые из заданной вершины графы]]* [[Гамильтоновы графы]]* [[Теорема Хватала]]* Следствия теоремы Хватала: ** [[Теорема Дирака]]* [[Теорема Оре]]* [[Турниры]]* [[Теорема Редеи-Камиона]] == Укладки графов ==* [[Укладка графа на плоскости]]* [[Формула Эйлера]]* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]* [[Укладка дерева]]* [[Укладка графа с планарными компонентами реберной двусвязности]]* [[Укладка графа с планарными компонентами вершинной двусвязности]]* [[Теорема Понтрягина-Куратовского]]* [[Двойственный граф планарного графа]] == Раскраски графов ==* [[Раскраска графа]]* [[Двудольные графы и раскраска в 2 цвета]]* [[Хроматический многочлен]]** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленов]]** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность]]* [[Формула Зыкова]]* [[Формула Уитни]] == Обход в глубину ==* перенаправление [[Обход в глубинуДискретная математика, цвета вершин]]* [[Лемма о белых путях]]* [[Использование обхода в глубину для проверки связности]]* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]* [[Использование обхода в глубину для топологической сортировки]]* [[Использование обхода в глубину для поиска компонент сильной связности]]* [[Использование обхода в глубину для поиска точек сочленения]]* [[Построение компонент вершинной двусвязности]]* [[Использование обхода в глубину для поиска мостов]]* [[Построение компонент реберной двусвязности]] == Кратчайшие пути в графах ==* [[Обход в ширину]]* [[Алгоритм Форда-Беллмана]]* [[Алгоритм Дейкстры]]* [[Алгоритм Флойда]]* [[Алгоритм A*]]* [[Алгоритм Джонсона]] == Остовные деревья ==* [[Лемма о безопасном ребре]]* [[Алгоритм Прима]]* [[Алгоритм Краскала]]* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]* [[Алгоритм двух китайцев]] == Задача о паросочетании ==* [[Теорема о максимальном паросочетании и дополняющих цепях]]* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]* [[Алгоритм Куна для поиска максимального паросочетания]]* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]* [[Связь вершинного покрытия и независимого множества]]* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] == Задача о максимальном потоке ==* [[Определение сети, потока]]* [[Разрез, лемма о потоке через разрез]]* [[Дополняющая сеть, дополняющий путь]]* [[Лемма о сложении потоков]]* [[Теорема Форда-Фалкерсона]]* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]* [[Алоритм Эдмондса-Карпа]]* [[Теорема о декомпозиции]]* [[Теорема о декомпозиционном барьере]]* [[Блокирующий поток]]* [[Схема алгоритма Диница]]* [[Циркуляция потока]]* [[Алгоритм поиска блокирующего потока в ациклической сети]]* [[Алгоритм масштабирования потока]]* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]] == Задача о потоке минимальной стоимости ==* [[Поток минимальной стоимости]]* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]* [[Лемма об эквивалентности свойства потока быть минимальной стоимости алгоритмы и отсутствии отрицательных циклов в остаточной сети]]* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]* [[Венгерский алгоритм решения задачи о назначениях]] == Поиск подстроки в строке ==* [[Наивный алгоритм поиска подстроки в строке]]* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]* [[Префикс-функция]]* [[Алгоритм Кнута-Морриса-Пратта]]* [[Z-функция]]* [[Автомат для поиска образца в тексте]]* [[Бор]]* [[Алгоритм Ахо-Корасик]] == Словарные структуры данных ==* [[Суффиксный бор]]* [[Сжатое суффиксное дерево]]* [[Алгоритм Укконена]] == Задача о наименьшем общем предке ==* [[Метод двоичного подъема]]* [[Сведение задачи LCA к задаче RMQ]]* [[Решение RMQ с помощью разреженной таблицы]]* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четверых русских)* [[Сведение задачи RMQ к задаче LCA]] == Суффиксный массив ==* [[Суффиксный массив]]* [[Построение суффиксного массива с помощью стандартных методов сортировки]]* [[Алгоритм цифровой сортировки]]* [[Алгоритм цифровой сортировки суффиксов циклической строки]]* [[Алгоритм Касаи и др.]]* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]] == Матроиды ==* [[Определение матроида]]* [[Примеры матроидов]]* [[Прямая сумма матроидов]]* [[Теорема Радо-Эдмондса (жадный алгоритм)]]* [[Жадный алгоритм поиска базы минимального веса]]* [[Теорема о базах]]* [[Аксиоматизация матроида базами]]* [[Теорема о циклах]]* [[Аксиоматизация матроида циклами]]* [[Ранговая функция, полумодулярность]]* [[Двойственный матроид]]* [[Оператор замыкания для матроидов]]* [[Пересечение матроидов, определение, примеры]]* [[Лемма о паросочетании в графе замен]]* [[Лемма о единственном паросочетании в графе замен]]* [[Граф замен для двух матроидов]]* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]* [[Алгоритм построения базы в пересечении матроидов]]* [[Теорема Эдмондса-Лоулера]]* [[Объединение матроидов, проверка множества на независимость]]* [[Объединение матроидов, доказательство того, что объединение является матроидом]]* [[Алгоритм построения базы в объединении матроидов]]
[[Категория: Алгоритмы и структуры данных]]
