Алгоритмы и структуры данных
Версия от 22:32, 22 декабря 2010; Vladimir.nesmelov (обсуждение | вклад) (→Задача о паросочетании: небольшая корректировка)
Основные определения теории графов
- Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
- Лемма о рукопожатиях
- Ориентированный граф
- Вариант леммы о рукопожатиях для ориентированного графа
- Теорема о существовании простого пути в случае существования пути
- Теорема о существовании простого цикла в случае существования цикла
- Матрица смежности графа
- Связь степени матрицы смежности и количества путей
- Матрица инцидентности графа
- Циклическое пространство графа
- Фундаментальные циклы графа
- Дерево, эквивалентные определения
Связность в графах
- Отношение связности, компоненты связности
- Отношение реберной двусвязности
- Отношение вершинной двусвязности
- Граф компонент реберной двусвязности
- Граф блоков-точек сочленения
- Точка сочленения, эквивалентные определения
- Мост, эквивалентные определения
- k-связность
- Теорема Менгера
- Вершинная, реберная связность, связь между ними и минимальной степенью вершины
Остовные деревья
Обходы графов
Укладки графов
Раскраски графов
Обход в глубину
- Обход в глубину, цвета вершин
- Лемма о белых путях
- Использование обхода в глубину для проверки связности
- Использование обхода в глубину для поиска цикла в ориентированном графе
- Использование обхода в глубину для топологической сортировки
- Использование обхода в глубину для поиска компонент сильной связности
- Использование обхода в глубину для поиска точек сочленения
- Построение компонент вершинной двусвязности
- Использование обхода в глубину для поиска мостов
- Построение компонент реберной двусвязности
Кратчайшие пути в графах
Остовные деревья
Задача о паросочетании
- Теорема о максимальном паросочетании и дополняющих цепях
- Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
- Алгоритм Куна для поиска максимального паросочетания
- Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
- Связь вершинного покрытия и независимого множества
- Матрица Татта и связь с размером максимального паросочетания в двудольном графе
- Паросочетания в недвудольных графах. Алгоритм вырезания соцветий
Задача о максимальном потоке
- Определение сети, потока
- Разрез, лемма о потоке через разрез
- Дополняющая сеть, дополняющий путь
- Лемма о сложении потоков
- Теорема Форда-Фалкерсона
- Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
- Алоритм Эдмондса-Карпа
- Теорема о декомпозиции
- Теорема о декомпозиционном барьере
- Блокирующий поток
- Схема алгоритма Диница
- Алгоритм поиска блокирующего потока в ациклической сети
- Алгоритм масштабирования потока
- Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями
Задача о потоке минимальной стоимости
- Поток минимальной стоимости
- Теорема Форда-Фалкерсона о потоке минимальной стоимости
- Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
- Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
- Использование потенциалов Джонсона при поиске потока минимальной стоимости
- Сведение задачи о назначениях к задаче о потоке минимальной стоимости
- Венгерский алгоритм решения задачи о назначениях
