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