Алгоритмы и структуры данных — различия между версиями
(Обновление тем до состояния на 17.11.2010) |
(Обновление тем до состояния на 01.12.2010) |
||
| Строка 93: | Строка 93: | ||
* [[Алгоритм Краскала]] | * [[Алгоритм Краскала]] | ||
* [[Теорема Тарьяна|Теорема Тарьяна (критерий минимальности остовного дерева)]] | * [[Теорема Тарьяна|Теорема Тарьяна (критерий минимальности остовного дерева)]] | ||
| + | * [[Алгоритм двух китайцев]] | ||
| + | |||
| + | == Задача о паросочетании == | ||
| + | * [[Теорема о максимальном паросочетании и дополняющих цепях]] | ||
| + | * [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]] | ||
| + | * [[Алгоритм Куна для поиска максимального паросочетания]] | ||
| + | * [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]] | ||
| + | * [[Связь вершинного покрытия и независимого множества]] | ||
| + | * [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]] | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
Версия 03:27, 2 декабря 2010
Содержание
Основные определения теории графов
- Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
- Лемма о рукопожатиях
- Ориентированный граф
- Вариант леммы о рукопожатиях для ориентированного графа
- Теорема о существовании простого пути в случае существования пути
- Теорема о существовании простого цикла в случае существования цикла
- Матрица смежности графа
- Связь степени матрицы смежности и количества путей
- Матрица инцидентности графа
- Циклическое пространство графа
- Фундаментальные циклы графа
- Дерево, эквивалентные определения
Связность в графах
- Отношение связности, компоненты связности
- Отношение реберной двусвязности
- Отношение вершинной двусвязности
- Граф компонент реберной двусвязности
- Граф блоков-точек сочленения
- Точка сочленения, эквивалентные определения
- Мост, эквивалентные определения
- k-связность
- Теорема Менгера
- Вершинная, реберная связность, связь между ними и минимальной степенью вершины
Остовные деревья
- Матрица Кирхгофа
- Связь матрицы Кирхгофа и матрицы инцидентности
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
- Количество помеченных деревьев
- Коды Прюфера
Обходы графов
- Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
- Покрытие ребер графа путями
- Алгоритм построения Эйлерова цикла
- Произвольно вычерчиваемые из заданной вершины графы
- Гамильтоновы графы
- Теорема Хватала
- Следствия теоремы Хватала:
- Турниры
- Теорема Редеи-Камиона
Укладки графов
- Укладка графа на плоскости
- Формула Эйлера
- Непланарность и
- Укладка дерева
- Укладка графа с планарными компонентами реберной двусвязности
- Укладка графа с планарными компонентами вершинной двусвязности
- Теорема Понтрягина-Куратовского
- Двойственный граф планарного графа
Раскраски графов
- Раскраска графа
- Двудольные графы и раскраска в 2 цвета
- Хроматический многочлен
- Формула Зыкова
- Формула Уитни
Обход в глубину
- Обход в глубину, цвета вершин
- Лемма о белых путях
- Использование обхода в глубину для проверки связности
- Использование обхода в глубину для поиска цикла в ориентированном графе
- Использование обхода в глубину для топологической сортировки
- Использование обхода в глубину для поиска компонент сильной связности
- Использование обхода в глубину для поиска точек сочленения
- Построение компонент вершинной двусвязности
- Использование обхода в глубину для поиска мостов
- Построение компонент реберной двусвязности
Кратчайшие пути в графах
Остовные деревья
- Лемма о безопасном ребре
- Алгоритм Прима
- Алгоритм Краскала
- Теорема Тарьяна (критерий минимальности остовного дерева)
- Алгоритм двух китайцев
Задача о паросочетании
- Теорема о максимальном паросочетании и дополняющих цепях
- Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
- Алгоритм Куна для поиска максимального паросочетания
- Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
- Связь вершинного покрытия и независимого множества
- Матрица Татта и связь с размером максимального паросочетания в двудольном графе
