Алгоритмы и структуры данных — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 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]]
 
 
 
== Суффиксный массив ==
 
* [[Суффиксный массив]]
 
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
 
* [[Алгоритм цифровой сортировки]]
 
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
 
* [[Алгоритм Касаи и др.]]
 
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
 
 
 
== Матроиды ==
 
* [[Определение матроида]]
 
* [[Примеры матроидов]]
 
* [[Прямая сумма матроидов]]
 
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
 
* [[Жадный алгоритм поиска базы минимального веса]]
 
* [[Теорема о базах]]
 
* [[Аксиоматизация матроида базами]]
 
* [[Теорема о циклах]]
 
* [[Аксиоматизация матроида циклами]]
 
* [[Ранговая функция, полумодулярность]]
 
* [[Двойственный матроид]]
 
* [[Оператор замыкания для матроидов]]
 
* [[Пересечение матроидов, определение, примеры]]
 
* [[Лемма о паросочетании в графе замен]]
 
* [[Лемма о единственном паросочетании в графе замен]]
 
* [[Граф замен для двух матроидов]]
 
* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
 
* [[Алгоритм построения базы в пересечении матроидов]]
 
* [[Теорема Эдмондса-Лоулера]]
 
* [[Объединение матроидов, проверка множества на независимость]]
 
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]
 
* [[Алгоритм построения базы в объединении матроидов]]
 
 
 
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]

Версия 15:53, 10 марта 2012