Викиконспекты - Вклад участника [ru]

Алгоритмы и структуры данных

2011-04-08T22:49:30Z

Vladimir.nesmelov: Обновление тем до состояния на 08.04.2011

== Основные определения теории графов ==
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
* [[Лемма о рукопожатиях]]
* [[Ориентированный граф]]
* [[Лемма о рукопожатиях#Вариант леммы о рукопожатиях для ориентированного графа|Вариант леммы о рукопожатиях для ориентированного графа]]
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Теорема о существовании простого цикла в случае существования цикла]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]
* [[Матрица инцидентности графа]]
* [[Циклическое пространство графа]]
* [[Фундаментальные циклы графа]]
* [[Дерево, эквивалентные определения]]

== Связность в графах ==
* [[Отношение связности, компоненты связности]]
* [[Отношение реберной двусвязности]]
* [[Отношение вершинной двусвязности]]
* [[Граф компонент реберной двусвязности]]
* [[Граф блоков-точек сочленения]]
* [[Точка сочленения, эквивалентные определения]]
* [[Мост, эквивалентные определения]]
* [[k-связность]]
* [[Теорема Менгера]]
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]

== Остовные деревья ==
* [[Матрица Кирхгофа]]
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
* [[Количество помеченных деревьев]]
* [[Коды Прюфера]]

== Обходы графов ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [[Покрытие ребер графа путями]]
* [[Алгоритм построения Эйлерова цикла]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
* [[Гамильтоновы графы]]
* [[Теорема Хватала]]
* Следствия теоремы Хватала:
** [[Теорема Дирака]]
** [[Теорема Оре]]
* [[Турниры]]
* [[Теорема Редеи-Камиона]]

== Укладки графов ==
* [[Укладка графа на плоскости]]
* [[Формула Эйлера]]
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
* [[Укладка дерева]]
* [[Укладка графа с планарными компонентами реберной двусвязности]]
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
* [[Теорема Понтрягина-Куратовского]]
* [[Двойственный граф планарного графа]]

== Раскраски графов ==
* [[Раскраска графа]]
* [[Двудольные графы и раскраска в 2 цвета]]
* [[Хроматический многочлен]]
** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]
** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]
** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]
** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленов]]
** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность]]
* [[Формула Зыкова]]
* [[Формула Уитни]]

== Обход в глубину ==
* [[Обход в глубину, цвета вершин]]
* [[Лемма о белых путях]]
* [[Использование обхода в глубину для проверки связности]]
* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
* [[Использование обхода в глубину для топологической сортировки]]
* [[Использование обхода в глубину для поиска компонент сильной связности]]
* [[Использование обхода в глубину для поиска точек сочленения]]
* [[Построение компонент вершинной двусвязности]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Построение компонент реберной двусвязности]]

== Кратчайшие пути в графах ==
* [[Обход в ширину]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Флойда]]
* [[Алгоритм Джонсона]]

== Остовные деревья ==
* [[Лемма о безопасном ребре]]
* [[Алгоритм Прима]]
* [[Алгоритм Краскала]]
* [[Теорема Тарьяна|Теорема Тарьяна (критерий минимальности остовного дерева)]]
* [[Алгоритм двух китайцев]]

== Задача о паросочетании ==
* [[Теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
* [[Алгоритм Куна для поиска максимального паросочетания]]
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
* [[Связь вершинного покрытия и независимого множества]]
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]

== Задача о максимальном потоке ==
* [[Определение сети, потока]]
* [[Разрез, лемма о потоке через разрез]]
* [[Дополняющая сеть, дополняющий путь]]
* [[Лемма о сложении потоков]]
* [[Теорема Форда-Фалкерсона]]
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа]]
* [[Теорема о декомпозиции]]
* [[Теорема о декомпозиционном барьере]]
* [[Блокирующий поток]]
* [[Схема алгоритма Диница]]
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Алгоритм масштабирования потока]]
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]

== Задача о потоке минимальной стоимости ==
* [[Поток минимальной стоимости]]
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
* [[Венгерский алгоритм решения задачи о назначениях]]

== Поиск подстроки в строке ==
* [[Наивный алгоритм поиска подстроки в строке]]
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
* [[Префикс-функция]]
* [[Алгоритм Кнута-Морриса-Пратта]]
* [[Z-функция]]
* [[Автомат для поиска образца в тексте]]
* [[Бор]]
* [[Алгоритм Ахо-Корасик]]

== Словарные структуры данных ==
* [[Суффиксный бор]]
* [[Сжатое суффиксное дерево]]
* [[Алгоритм Укконена]]

== Задача о наименьшем общем предке ==
* [[Метод двоичного подъема]]
* [[Сведение задачи LCA к задаче RMQ]]
* [[Решение RMQ с помощью разреженной таблицы]]
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
* [[Сведение задачи RMQ к задаче LCA]]

== Суффиксный массив ==
* [[Суффиксный массив]]
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
* [[Алгоритм цифровой сортировки]]
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
* [[Алгоритм Касаи и др.]]
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]

[[Категория: Алгоритмы и структуры данных]]

Алгоритмы и структуры данных

2011-03-04T22:13:04Z

Vladimir.nesmelov: Обновление тем до состояния на 04.03.2011

== Основные определения теории графов ==
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
* [[Лемма о рукопожатиях]]
* [[Ориентированный граф]]
* [[Лемма о рукопожатиях#Вариант леммы о рукопожатиях для ориентированного графа|Вариант леммы о рукопожатиях для ориентированного графа]]
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Теорема о существовании простого цикла в случае существования цикла]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]
* [[Матрица инцидентности графа]]
* [[Циклическое пространство графа]]
* [[Фундаментальные циклы графа]]
* [[Дерево, эквивалентные определения]]

== Связность в графах ==
* [[Отношение связности, компоненты связности]]
* [[Отношение реберной двусвязности]]
* [[Отношение вершинной двусвязности]]
* [[Граф компонент реберной двусвязности]]
* [[Граф блоков-точек сочленения]]
* [[Точка сочленения, эквивалентные определения]]
* [[Мост, эквивалентные определения]]
* [[k-связность]]
* [[Теорема Менгера]]
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]

== Остовные деревья ==
* [[Матрица Кирхгофа]]
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
* [[Количество помеченных деревьев]]
* [[Коды Прюфера]]

== Обходы графов ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [[Покрытие ребер графа путями]]
* [[Алгоритм построения Эйлерова цикла]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
* [[Гамильтоновы графы]]
* [[Теорема Хватала]]
* Следствия теоремы Хватала:
** [[Теорема Дирака]]
** [[Теорема Оре]]
* [[Турниры]]
* [[Теорема Редеи-Камиона]]

== Укладки графов ==
* [[Укладка графа на плоскости]]
* [[Формула Эйлера]]
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
* [[Укладка дерева]]
* [[Укладка графа с планарными компонентами реберной двусвязности]]
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
* [[Теорема Понтрягина-Куратовского]]
* [[Двойственный граф планарного графа]]

== Раскраски графов ==
* [[Раскраска графа]]
* [[Двудольные графы и раскраска в 2 цвета]]
* [[Хроматический многочлен]]
** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]
** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]
** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]
** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленов]]
** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность]]
* [[Формула Зыкова]]
* [[Формула Уитни]]

== Обход в глубину ==
* [[Обход в глубину, цвета вершин]]
* [[Лемма о белых путях]]
* [[Использование обхода в глубину для проверки связности]]
* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
* [[Использование обхода в глубину для топологической сортировки]]
* [[Использование обхода в глубину для поиска компонент сильной связности]]
* [[Использование обхода в глубину для поиска точек сочленения]]
* [[Построение компонент вершинной двусвязности]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Построение компонент реберной двусвязности]]

== Кратчайшие пути в графах ==
* [[Обход в ширину]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Флойда]]
* [[Алгоритм Джонсона]]

== Остовные деревья ==
* [[Лемма о безопасном ребре]]
* [[Алгоритм Прима]]
* [[Алгоритм Краскала]]
* [[Теорема Тарьяна|Теорема Тарьяна (критерий минимальности остовного дерева)]]
* [[Алгоритм двух китайцев]]

== Задача о паросочетании ==
* [[Теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
* [[Алгоритм Куна для поиска максимального паросочетания]]
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
* [[Связь вершинного покрытия и независимого множества]]
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]

== Задача о максимальном потоке ==
* [[Определение сети, потока]]
* [[Разрез, лемма о потоке через разрез]]
* [[Дополняющая сеть, дополняющий путь]]
* [[Лемма о сложении потоков]]
* [[Теорема Форда-Фалкерсона]]
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа]]
* [[Теорема о декомпозиции]]
* [[Теорема о декомпозиционном барьере]]
* [[Блокирующий поток]]
* [[Схема алгоритма Диница]]
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Алгоритм масштабирования потока]]
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]

== Задача о потоке минимальной стоимости ==
* [[Поток минимальной стоимости]]
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
* [[Венгерский алгоритм решения задачи о назначениях]]

== Поиск подстроки в строке ==
* [[Наивный алгоритм поиска подстроки в строке]]
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
* [[Префикс-функция]]
* [[Алгоритм Кнута-Морриса-Пратта]]
* [[Z-функция]]
* [[Автомат для поиска образца в тексте]]
* [[Бор]]
* [[Алгоритм Ахо-Корасик]]

== Словарные структуры данных ==
* [[Суффиксный бор]]
* [[Сжатое суффиксное дерево]]
* [[Алгоритм Укконена]]

[[Категория: Алгоритмы и структуры данных]]

Алгоритмы и структуры данных

2011-02-17T01:37:07Z

Vladimir.nesmelov: Обновление тем до состояния на 16.02.2011

== Основные определения теории графов ==
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
* [[Лемма о рукопожатиях]]
* [[Ориентированный граф]]
* [[Лемма о рукопожатиях#Вариант леммы о рукопожатиях для ориентированного графа|Вариант леммы о рукопожатиях для ориентированного графа]]
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Теорема о существовании простого цикла в случае существования цикла]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]
* [[Матрица инцидентности графа]]
* [[Циклическое пространство графа]]
* [[Фундаментальные циклы графа]]
* [[Дерево, эквивалентные определения]]

== Связность в графах ==
* [[Отношение связности, компоненты связности]]
* [[Отношение реберной двусвязности]]
* [[Отношение вершинной двусвязности]]
* [[Граф компонент реберной двусвязности]]
* [[Граф блоков-точек сочленения]]
* [[Точка сочленения, эквивалентные определения]]
* [[Мост, эквивалентные определения]]
* [[k-связность]]
* [[Теорема Менгера]]
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]

== Остовные деревья ==
* [[Матрица Кирхгофа]]
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
* [[Количество помеченных деревьев]]
* [[Коды Прюфера]]

== Обходы графов ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [[Покрытие ребер графа путями]]
* [[Алгоритм построения Эйлерова цикла]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
* [[Гамильтоновы графы]]
* [[Теорема Хватала]]
* Следствия теоремы Хватала:
** [[Теорема Дирака]]
** [[Теорема Оре]]
* [[Турниры]]
* [[Теорема Редеи-Камиона]]

== Укладки графов ==
* [[Укладка графа на плоскости]]
* [[Формула Эйлера]]
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
* [[Укладка дерева]]
* [[Укладка графа с планарными компонентами реберной двусвязности]]
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
* [[Теорема Понтрягина-Куратовского]]
* [[Двойственный граф планарного графа]]

== Раскраски графов ==
* [[Раскраска графа]]
* [[Двудольные графы и раскраска в 2 цвета]]
* [[Хроматический многочлен]]
** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]
** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]
** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]
** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленов]]
** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность]]
* [[Формула Зыкова]]
* [[Формула Уитни]]

== Обход в глубину ==
* [[Обход в глубину, цвета вершин]]
* [[Лемма о белых путях]]
* [[Использование обхода в глубину для проверки связности]]
* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
* [[Использование обхода в глубину для топологической сортировки]]
* [[Использование обхода в глубину для поиска компонент сильной связности]]
* [[Использование обхода в глубину для поиска точек сочленения]]
* [[Построение компонент вершинной двусвязности]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Построение компонент реберной двусвязности]]

== Кратчайшие пути в графах ==
* [[Обход в ширину]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Флойда]]
* [[Алгоритм Джонсона]]

== Остовные деревья ==
* [[Лемма о безопасном ребре]]
* [[Алгоритм Прима]]
* [[Алгоритм Краскала]]
* [[Теорема Тарьяна|Теорема Тарьяна (критерий минимальности остовного дерева)]]
* [[Алгоритм двух китайцев]]

== Задача о паросочетании ==
* [[Теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
* [[Алгоритм Куна для поиска максимального паросочетания]]
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
* [[Связь вершинного покрытия и независимого множества]]
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]

== Задача о максимальном потоке ==
* [[Определение сети, потока]]
* [[Разрез, лемма о потоке через разрез]]
* [[Дополняющая сеть, дополняющий путь]]
* [[Лемма о сложении потоков]]
* [[Теорема Форда-Фалкерсона]]
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа]]
* [[Теорема о декомпозиции]]
* [[Теорема о декомпозиционном барьере]]
* [[Блокирующий поток]]
* [[Схема алгоритма Диница]]
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Алгоритм масштабирования потока]]
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]

== Задача о потоке минимальной стоимости ==
* [[Поток минимальной стоимости]]
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
* [[Венгерский алгоритм решения задачи о назначениях]]

== Поиск подстроки в строке ==
* [[Наивный алгоритм поиска подстроки в строке]]
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
* [[Префикс-функция]]
* [[Алгоритм Кнута-Морриса-Пратта]]
* [[Z-функция]]
* [[Автомат для поиска образца в тексте]]
* [[Бор]]
* [[Алгоритм Ахо-Корасик]]

[[Категория: Алгоритмы и структуры данных]]

Алгоритмы и структуры данных

2011-02-16T06:56:16Z

Vladimir.nesmelov: Обновление тем до состояния на 15.02.2011

== Основные определения теории графов ==
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
* [[Лемма о рукопожатиях]]
* [[Ориентированный граф]]
* [[Лемма о рукопожатиях#Вариант леммы о рукопожатиях для ориентированного графа|Вариант леммы о рукопожатиях для ориентированного графа]]
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Теорема о существовании простого цикла в случае существования цикла]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]
* [[Матрица инцидентности графа]]
* [[Циклическое пространство графа]]
* [[Фундаментальные циклы графа]]
* [[Дерево, эквивалентные определения]]

== Связность в графах ==
* [[Отношение связности, компоненты связности]]
* [[Отношение реберной двусвязности]]
* [[Отношение вершинной двусвязности]]
* [[Граф компонент реберной двусвязности]]
* [[Граф блоков-точек сочленения]]
* [[Точка сочленения, эквивалентные определения]]
* [[Мост, эквивалентные определения]]
* [[k-связность]]
* [[Теорема Менгера]]
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]

== Остовные деревья ==
* [[Матрица Кирхгофа]]
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
* [[Количество помеченных деревьев]]
* [[Коды Прюфера]]

== Обходы графов ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [[Покрытие ребер графа путями]]
* [[Алгоритм построения Эйлерова цикла]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
* [[Гамильтоновы графы]]
* [[Теорема Хватала]]
* Следствия теоремы Хватала:
** [[Теорема Дирака]]
** [[Теорема Оре]]
* [[Турниры]]
* [[Теорема Редеи-Камиона]]

== Укладки графов ==
* [[Укладка графа на плоскости]]
* [[Формула Эйлера]]
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
* [[Укладка дерева]]
* [[Укладка графа с планарными компонентами реберной двусвязности]]
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
* [[Теорема Понтрягина-Куратовского]]
* [[Двойственный граф планарного графа]]

== Раскраски графов ==
* [[Раскраска графа]]
* [[Двудольные графы и раскраска в 2 цвета]]
* [[Хроматический многочлен]]
** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]
** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]
** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]
** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленов]]
** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность]]
* [[Формула Зыкова]]
* [[Формула Уитни]]

== Обход в глубину ==
* [[Обход в глубину, цвета вершин]]
* [[Лемма о белых путях]]
* [[Использование обхода в глубину для проверки связности]]
* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
* [[Использование обхода в глубину для топологической сортировки]]
* [[Использование обхода в глубину для поиска компонент сильной связности]]
* [[Использование обхода в глубину для поиска точек сочленения]]
* [[Построение компонент вершинной двусвязности]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Построение компонент реберной двусвязности]]

== Кратчайшие пути в графах ==
* [[Обход в ширину]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Флойда]]
* [[Алгоритм Джонсона]]

== Остовные деревья ==
* [[Лемма о безопасном ребре]]
* [[Алгоритм Прима]]
* [[Алгоритм Краскала]]
* [[Теорема Тарьяна|Теорема Тарьяна (критерий минимальности остовного дерева)]]
* [[Алгоритм двух китайцев]]

== Задача о паросочетании ==
* [[Теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
* [[Алгоритм Куна для поиска максимального паросочетания]]
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
* [[Связь вершинного покрытия и независимого множества]]
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]

== Задача о максимальном потоке ==
* [[Определение сети, потока]]
* [[Разрез, лемма о потоке через разрез]]
* [[Дополняющая сеть, дополняющий путь]]
* [[Лемма о сложении потоков]]
* [[Теорема Форда-Фалкерсона]]
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа]]
* [[Теорема о декомпозиции]]
* [[Теорема о декомпозиционном барьере]]
* [[Блокирующий поток]]
* [[Схема алгоритма Диница]]
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Алгоритм масштабирования потока]]
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]

== Задача о потоке минимальной стоимости ==
* [[Поток минимальной стоимости]]
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
* [[Венгерский алгоритм решения задачи о назначениях]]

== Поиск подстроки в строке ==
* [[Наивный алгоритм поиска подстроки в строке]]
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
* [[Префикс-функция]]
* [[Алгоритм Кнута-Морриса-Пратта]]
* [[Z-функция]]

[[Категория: Алгоритмы и структуры данных]]

Алгоритм Дейкстры

2011-01-15T19:23:14Z

Vladimir.nesmelov: /* Псевдокод */ корректировка

В ориентированном взвешанном графе <tex>G = (V, E)</tex>, вес рёбер которого неотрицателен и определяется весовой функцией <tex>w(uv) \geqslant 0</tex>, Алгоритм Дейкстры находит длину кратчайшего пути из одной вершины <tex>s</tex> до всех остальных.

== Алгоритм ==
В алгоритме поддерживается множество вершин <tex>S</tex>, для которых уже вычислены кратчайшие пути к ним из вершины <tex>s</tex>. На каждой итерации основного цикла выбирается вершина <tex> u \in V \setminus S</tex>, которой на текущий момент соответствует минимальная оценка кратчайшего пути. Вершина <tex>u</tex> добавляется в множество <tex>S</tex> и производится релаксация всех исходящих из неё рёбер.

== Псевдокод ==
'''Dijkstra'''(<tex>G</tex>, <tex>w</tex>, <tex>s</tex>)
<tex>d \gets \infty</tex>
<tex>d[s] \gets 0</tex>
<tex>S \gets \emptyset</tex>
'''while''' <tex>V \setminus S \neq \emptyset</tex>
'''do''' <tex>u \gets </tex> ''argmin''(<tex>v : v \in V \setminus S, d[v]</tex>)
<tex>S \gets S \cup \{u\}</tex>
'''for''' <tex>(uv) \in E</tex>
'''do''' ''relax''(<tex>u</tex>, <tex>v</tex>, <tex>w</tex>)

== Обоснование корректности работы ==
{{Теорема
|statement=После окончания работы алгоритма Дейкстры для всех вершин <tex>u \in V</tex> будет выполняться равенство <tex>d[u] = \delta(s, u)</tex>
|proof=
Рассмотрим инвариант основного цикла: в начале каждой итерации для всех вершин <tex>v \in S</tex> выполняется <tex>d[v] = \delta(s, v)</tex>

'''Инициализация'''. Изначально множество <tex>S</tex> пусто, инвариант выполняется.

[[Файл:DijkstraProove.png|thumb|right|Рис. 1]]
'''Сохранение'''. Покажем, что при каждой итерации инвариант сохраняется для каждой вершины, добавленной в <tex>S</tex>, для этого воспользуемся методом «от противного». Предположим, что <tex>u</tex> первая добавленная в <tex>S</tex> вершина, для которой равенство <tex>d[u] = \delta(s, u)</tex> не выполняется. Рассмотрим ситуацию, сложившуюся в начале итерации, в которой <tex>u</tex> будет добавлена в <tex>S</tex>. Рассмотрев кратчайший путь из <tex>s</tex> в <tex>u</tex>, можно получить противоречие, заключающееся в том, что на рассматриваемый момент справедливо равенство <tex>d[u] = \delta(s, u)</tex>. Должно выполняться условие <tex>u \neq s</tex>, так как <tex>s</tex> является первой вершиной, добавленной в <tex>S</tex> и в момент её добавления равенство <tex>d[u] = \delta(s, u)</tex> выполняется. Из условия <tex>u \neq s</tex> следует, в частности, что <tex>S</tex> не пусто. Из вершины <tex>s</tex> в вершину <tex>u</tex> должен существовать какой-нибудь путь, так как иначе выполняется соотношение <tex>d[u] = \delta(s, u) = \infty</tex>, нарушающее предположение о том, что равенство <tex>d[u] = \delta(s, u)</tex> не выполняется. Из существования пути следует, что существует и кратчайший путь <tex>p</tex> из <tex>s</tex> в <tex>u</tex>. Перед добавлением <tex>u</tex> в <tex>S</tex> путь <tex>p</tex> соединяет вершину из множества <tex>S</tex> с вершиной принадлежащей множеству <tex>V \setminus S</tex>. Рассмотрим первую вершину <tex>y</tex> на пути <tex>p</tex> принадлежащую <tex>V \setminus S</tex>, и положим, что её предшествует вершина <tex>x \in S</tex>. Тогда, как видно из рис.1, путь <tex>p</tex> можно разложить на составляющие <tex>s \overset{p_1}{\leadsto} x \to y \overset{p_2}{\leadsto} u</tex>.

Утверждается, что в момент добавления вершины <tex>u</tex> в множество <tex>S</tex>, выполняется равенство <tex>d[u] = \delta(s, y)</tex>. Так как вершина <tex>u</tex> выбрана как первая вершина, после добавления которой в множество <tex>S</tex> не выполянется соотношение <tex>d[u] = \delta(s, u)</tex>, то после добавления вершины <tex>x</tex> в <tex>S</tex> справедливо равенство <tex>d[x] = \delta(s, x)</tex>. В это время происходит релаксация ребра <tex>xy</tex>, поэтому вышеописанное утверждение выполняется.

Поскольку на кратчайшем пути из <tex>s</tex> в <tex>u</tex> вершина <tex>y</tex> находиться перед <tex>u</tex> и вес каждого из ребер выражается неотрицательным значением, выполняется неравенство <tex>\delta(s, y) \leqslant \delta(s, u)</tex>, поэтому <tex>d[y] = \delta(s, y) \leqslant \delta(s, u) \leqslant d[u]</tex>. Но так как и вершина <tex>u</tex>, и вершина <tex>y</tex> во время выбора вершины <tex>u</tex> находились в множестве <tex>V \setminus S</tex>, выполняется неравенство <tex>d[u] \leqslant d[y]</tex>. Таким образом, оба <tex>d[y] = \delta(s, y) = \delta(s, u) = d[u]</tex>.

Значит, <tex>d[u] = \delta(s, u)</tex>, что противоречит нашему выбору вершины <tex>u</tex>. Следовательно, во время добавления вершины <tex>u</tex> в множество <tex>S</tex> выполняется равенство<tex>d[u] = \delta(s, u)</tex>, а следовательно, оно выполняется и в дальнейшем.

'''Завершение'''. По завершении работы алгоритма множество <tex>V \setminus S</tex> пусто. Из этого равенства следует, что <tex>S = V</tex>. Таким образом, для всех вершин <tex>u \in V</tex> выполняется равенство <tex>d[u] = \delta(s, u)</tex>.
}}

== Оценка сложности ==
Основной цикл выполняется <tex>V</tex> раз. Релаксация выполниться всего <tex>E</tex> раз. В реализации алгоритма присутствует функция ''argmin'', асимптотика её работы зависит от реализации.

Таким образом:
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=30%
!style="background:#f2f2f2"|Структура данных для хранения множества <tex>V \setminus S</tex>
!style="background:#f2f2f2"|Асимптотика времени работы
|-
|style="background:#f9f9f9"|Наивная реализация
|style="background:#f9f9f9"|<tex>O(V^2+E)</tex>
|-
|style="background:#f9f9f9"|Куча
|style="background:#f9f9f9"|<tex>O(E\log{V})</tex>
|-
|style="background:#f9f9f9"|Куча Фибоначчи
|style="background:#f9f9f9"|<tex>O(V\log{V}+E)</tex>
|}

== Литература ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах ]]

Алгоритмы и структуры данных

2010-12-22T19:32:03Z

Vladimir.nesmelov: /* Задача о паросочетании */ небольшая корректировка

== Основные определения теории графов ==
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
* [[Лемма о рукопожатиях]]
* [[Ориентированный граф]]
* [[Лемма о рукопожатиях#Вариант леммы о рукопожатиях для ориентированного графа|Вариант леммы о рукопожатиях для ориентированного графа]]
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Теорема о существовании простого цикла в случае существования цикла]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]
* [[Матрица инцидентности графа]]
* [[Циклическое пространство графа]]
* [[Фундаментальные циклы графа]]
* [[Дерево, эквивалентные определения]]

== Связность в графах ==
* [[Отношение связности, компоненты связности]]
* [[Отношение реберной двусвязности]]
* [[Отношение вершинной двусвязности]]
* [[Граф компонент реберной двусвязности]]
* [[Граф блоков-точек сочленения]]
* [[Точка сочленения, эквивалентные определения]]
* [[Мост, эквивалентные определения]]
* [[k-связность]]
* [[Теорема Менгера]]
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]

== Остовные деревья ==
* [[Матрица Кирхгофа]]
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
* [[Количество помеченных деревьев]]
* [[Коды Прюфера]]

== Обходы графов ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [[Покрытие ребер графа путями]]
* [[Алгоритм построения Эйлерова цикла]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
* [[Гамильтоновы графы]]
* [[Теорема Хватала]]
* Следствия теоремы Хватала:
** [[Теорема Дирака]]
** [[Теорема Оре]]
* [[Турниры]]
* [[Теорема Редеи-Камиона]]

== Укладки графов ==
* [[Укладка графа на плоскости]]
* [[Формула Эйлера]]
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
* [[Укладка дерева]]
* [[Укладка графа с планарными компонентами реберной двусвязности]]
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
* [[Теорема Понтрягина-Куратовского]]
* [[Двойственный граф планарного графа]]

== Раскраски графов ==
* [[Раскраска графа]]
* [[Двудольные графы и раскраска в 2 цвета]]
* [[Хроматический многочлен]]
** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]
** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]
** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]
** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленов]]
** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность]]
* [[Формула Зыкова]]
* [[Формула Уитни]]

== Обход в глубину ==
* [[Обход в глубину, цвета вершин]]
* [[Лемма о белых путях]]
* [[Использование обхода в глубину для проверки связности]]
* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
* [[Использование обхода в глубину для топологической сортировки]]
* [[Использование обхода в глубину для поиска компонент сильной связности]]
* [[Использование обхода в глубину для поиска точек сочленения]]
* [[Построение компонент вершинной двусвязности]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Построение компонент реберной двусвязности]]

== Кратчайшие пути в графах ==
* [[Обход в ширину]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Флойда]]
* [[Алгоритм Джонсона]]

== Остовные деревья ==
* [[Лемма о безопасном ребре]]
* [[Алгоритм Прима]]
* [[Алгоритм Краскала]]
* [[Теорема Тарьяна|Теорема Тарьяна (критерий минимальности остовного дерева)]]
* [[Алгоритм двух китайцев]]

== Задача о паросочетании ==
* [[Теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
* [[Алгоритм Куна для поиска максимального паросочетания]]
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
* [[Связь вершинного покрытия и независимого множества]]
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]

== Задача о максимальном потоке ==
* [[Определение сети, потока]]
* [[Разрез, лемма о потоке через разрез]]
* [[Дополняющая сеть, дополняющий путь]]
* [[Лемма о сложении потоков]]
* [[Теорема Форда-Фалкерсона]]
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа]]
* [[Теорема о декомпозиции]]
* [[Теорема о декомпозиционном барьере]]
* [[Блокирующий поток]]
* [[Схема алгоритма Диница]]
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Алгоритм масштабирования потока]]
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]

== Задача о потоке минимальной стоимости ==
* [[Поток минимальной стоимости]]
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
* [[Венгерский алгоритм решения задачи о назначениях]]

[[Категория: Алгоритмы и структуры данных]]

Алгоритмы и структуры данных

2010-12-22T14:47:29Z

Vladimir.nesmelov: Обновление тем до состояния на 22.12.2010

== Основные определения теории графов ==
* [[Основные определения теории графов|Основные определения: граф, ребро, вершина, степень, петля, путь, цикл]]
* [[Лемма о рукопожатиях]]
* [[Ориентированный граф]]
* [[Лемма о рукопожатиях#Вариант леммы о рукопожатиях для ориентированного графа|Вариант леммы о рукопожатиях для ориентированного графа]]
* [[Теорема о существовании простого пути в случае существования пути]]
* [[Теорема о существовании простого цикла в случае существования цикла]]
* [[Матрица смежности графа]]
* [[Связь степени матрицы смежности и количества путей]]
* [[Матрица инцидентности графа]]
* [[Циклическое пространство графа]]
* [[Фундаментальные циклы графа]]
* [[Дерево, эквивалентные определения]]

== Связность в графах ==
* [[Отношение связности, компоненты связности]]
* [[Отношение реберной двусвязности]]
* [[Отношение вершинной двусвязности]]
* [[Граф компонент реберной двусвязности]]
* [[Граф блоков-точек сочленения]]
* [[Точка сочленения, эквивалентные определения]]
* [[Мост, эквивалентные определения]]
* [[k-связность]]
* [[Теорема Менгера]]
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]]

== Остовные деревья ==
* [[Матрица Кирхгофа]]
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
* [[Количество помеченных деревьев]]
* [[Коды Прюфера]]

== Обходы графов ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [[Покрытие ребер графа путями]]
* [[Алгоритм построения Эйлерова цикла]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
* [[Гамильтоновы графы]]
* [[Теорема Хватала]]
* Следствия теоремы Хватала:
** [[Теорема Дирака]]
** [[Теорема Оре]]
* [[Турниры]]
* [[Теорема Редеи-Камиона]]

== Укладки графов ==
* [[Укладка графа на плоскости]]
* [[Формула Эйлера]]
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
* [[Укладка дерева]]
* [[Укладка графа с планарными компонентами реберной двусвязности]]
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
* [[Теорема Понтрягина-Куратовского]]
* [[Двойственный граф планарного графа]]

== Раскраски графов ==
* [[Раскраска графа]]
* [[Двудольные графы и раскраска в 2 цвета]]
* [[Хроматический многочлен]]
** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]
** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]
** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]
** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленов]]
** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность]]
* [[Формула Зыкова]]
* [[Формула Уитни]]

== Обход в глубину ==
* [[Обход в глубину, цвета вершин]]
* [[Лемма о белых путях]]
* [[Использование обхода в глубину для проверки связности]]
* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
* [[Использование обхода в глубину для топологической сортировки]]
* [[Использование обхода в глубину для поиска компонент сильной связности]]
* [[Использование обхода в глубину для поиска точек сочленения]]
* [[Построение компонент вершинной двусвязности]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Построение компонент реберной двусвязности]]

== Кратчайшие пути в графах ==
* [[Обход в ширину]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Флойда]]
* [[Алгоритм Джонсона]]

== Остовные деревья ==
* [[Лемма о безопасном ребре]]
* [[Алгоритм Прима]]
* [[Алгоритм Краскала]]
* [[Теорема Тарьяна|Теорема Тарьяна (критерий минимальности остовного дерева)]]
* [[Алгоритм двух китайцев]]

== Задача о паросочетании ==
* [[Теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
* [[Алгоритм Куна для поиска максимального паросочетания]]
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
* [[Связь вершинного покрытия и независимого множества]]
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]

== Задача о максимальном потоке ==
* [[Определение сети, потока]]
* [[Разрез, лемма о потоке через разрез]]
* [[Дополняющая сеть, дополняющий путь]]
* [[Лемма о сложении потоков]]
* [[Теорема Форда-Фалкерсона]]
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа]]
* [[Теорема о декомпозиции]]
* [[Теорема о декомпозиционном барьере]]
* [[Блокирующий поток]]
* [[Схема алгоритма Диница]]
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Алгоритм масштабирования потока]]
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]

== Задача о потоке минимальной стоимости ==
* [[Поток минимальной стоимости]]
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
* [[Венгерский алгоритм решения задачи о назначениях]]

[[Категория: Алгоритмы и структуры данных]]

Алгоритм Дейкстры

2010-12-12T20:39:53Z

Vladimir.nesmelov:

В ориентированном взвешанном графе <tex>G = (V, E)</tex>, вес рёбер которого неотрицателен и определяется весовой функцией <tex>w(uv) \geqslant 0</tex>, Алгоритм Дейкстры находит длину кратчайшего пути из одной вершины <tex>s</tex> до всех остальных.

== Алгоритм ==
В алгоритме поддерживается множество вершин <tex>S</tex>, для которых уже вычислены кратчайшие пути к ним из вершины <tex>s</tex>. На каждой итерации основного цикла выбирается вершина <tex> u \in V \setminus S</tex>, которой на текущий момент соответствует минимальная оценка кратчайшего пути. Вершина <tex>u</tex> добавляется в множество <tex>S</tex> и производится релаксация всех исходящих из неё рёбер.

== Псевдокод ==
'''Dijkstra'''(<tex>G</tex>, <tex>w</tex>, <tex>s</tex>)
<tex>d \gets \infty</tex>
<tex>d[s] \gets 0</tex>
<tex>S \gets \emptyset</tex>
'''while''' <tex>V \setminus S \neq \emptyset</tex>
'''do''' ''argmin''(<tex>v : v \in V \setminus S, d[v]</tex>)
<tex>S \gets S \cup \{u\}</tex>
'''for''' <tex>(uv) \in E</tex>
'''do''' ''relax''(<tex>u</tex>, <tex>v</tex>, <tex>w</tex>)

== Обоснование корректности работы ==
{{Теорема
|statement=После окончания работы алгоритма Дейкстры для всех вершин <tex>u \in V</tex> будет выполняться равенство <tex>d[u] = \delta(s, u)</tex>
|proof=
Рассмотрим инвариант основного цикла: в начале каждой итерации для всех вершин <tex>v \in S</tex> выполняется <tex>d[v] = \delta(s, v)</tex>

'''Инициализация'''. Изначально множество <tex>S</tex> пусто, инвариант выполняется.

[[Файл:DijkstraProove.png|thumb|right|Рис. 1]]
'''Сохранение'''. Покажем, что при каждой итерации инвариант сохраняется для каждой вершины, добавленной в <tex>S</tex>, для этого воспользуемся методом «от противного». Предположим, что <tex>u</tex> первая добавленная в <tex>S</tex> вершина, для которой равенство <tex>d[u] = \delta(s, u)</tex> не выполняется. Рассмотрим ситуацию, сложившуюся в начале итерации, в которой <tex>u</tex> будет добавлена в <tex>S</tex>. Рассмотрев кратчайший путь из <tex>s</tex> в <tex>u</tex>, можно получить противоречие, заключающееся в том, что на рассматриваемый момент справедливо равенство <tex>d[u] = \delta(s, u)</tex>. Должно выполняться условие <tex>u \neq s</tex>, так как <tex>s</tex> является первой вершиной, добавленной в <tex>S</tex> и в момент её добавления равенство <tex>d[u] = \delta(s, u)</tex> выполняется. Из условия <tex>u \neq s</tex> следует, в частности, что <tex>S</tex> не пусто. Из вершины <tex>s</tex> в вершину <tex>u</tex> должен существовать какой-нибудь путь, так как иначе выполняется соотношение <tex>d[u] = \delta(s, u) = \infty</tex>, нарушающее предположение о том, что равенство <tex>d[u] = \delta(s, u)</tex> не выполняется. Из существования пути следует, что существует и кратчайший путь <tex>p</tex> из <tex>s</tex> в <tex>u</tex>. Перед добавлением <tex>u</tex> в <tex>S</tex> путь <tex>p</tex> соединяет вершину из множества <tex>S</tex> с вершиной принадлежащей множеству <tex>V \setminus S</tex>. Рассмотрим первую вершину <tex>y</tex> на пути <tex>p</tex> принадлежащую <tex>V \setminus S</tex>, и положим, что её предшествует вершина <tex>x \in S</tex>. Тогда, как видно из рис.1, путь <tex>p</tex> можно разложить на составляющие <tex>s \overset{p_1}{\leadsto} x \to y \overset{p_2}{\leadsto} u</tex>.

Утверждается, что в момент добавления вершины <tex>u</tex> в множество <tex>S</tex>, выполняется равенство <tex>d[u] = \delta(s, y)</tex>. Так как вершина <tex>u</tex> выбрана как первая вершина, после добавления которой в множество <tex>S</tex> не выполянется соотношение <tex>d[u] = \delta(s, u)</tex>, то после добавления вершины <tex>x</tex> в <tex>S</tex> справедливо равенство <tex>d[x] = \delta(s, x)</tex>. В это время происходит релаксация ребра <tex>xy</tex>, поэтому вышеописанное утверждение выполняется.

Поскольку на кратчайшем пути из <tex>s</tex> в <tex>u</tex> вершина <tex>y</tex> находиться перед <tex>u</tex> и вес каждого из ребер выражается неотрицательным значением, выполняется неравенство <tex>\delta(s, y) \leqslant \delta(s, u)</tex>, поэтому <tex>d[y] = \delta(s, y) \leqslant \delta(s, u) \leqslant d[u]</tex>. Но так как и вершина <tex>u</tex>, и вершина <tex>y</tex> во время выбора вершины <tex>u</tex> находились в множестве <tex>V \setminus S</tex>, выполняется неравенство <tex>d[u] \leqslant d[y]</tex>. Таким образом, оба <tex>d[y] = \delta(s, y) = \delta(s, u) = d[u]</tex>.

Значит, <tex>d[u] = \delta(s, u)</tex>, что противоречит нашему выбору вершины <tex>u</tex>. Следовательно, во время добавления вершины <tex>u</tex> в множество <tex>S</tex> выполняется равенство<tex>d[u] = \delta(s, u)</tex>, а следовательно, оно выполняется и в дальнейшем.

'''Завершение'''. По завершении работы алгоритма множество <tex>V \setminus S</tex> пусто. Из этого равенства следует, что <tex>S = V</tex>. Таким образом, для всех вершин <tex>u \in V</tex> выполняется равенство <tex>d[u] = \delta(s, u)</tex>.
}}

== Оценка сложности ==
Основной цикл выполняется <tex>V</tex> раз. Релаксация выполниться всего <tex>E</tex> раз. В реализации алгоритма присутствует функция ''argmin'', асимптотика её работы зависит от реализации.

Таким образом:
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=30%
!style="background:#f2f2f2"|Структура данных для хранения множества <tex>V \setminus S</tex>
!style="background:#f2f2f2"|Асимптотика времени работы
|-
|style="background:#f9f9f9"|Наивная реализация
|style="background:#f9f9f9"|<tex>O(V^2+E)</tex>
|-
|style="background:#f9f9f9"|Куча
|style="background:#f9f9f9"|<tex>O(E\log{V})</tex>
|-
|style="background:#f9f9f9"|Куча Фибоначчи
|style="background:#f9f9f9"|<tex>O(V\log{V}+E)</tex>
|}

== Литература ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах ]]

Алгоритм Дейкстры

2010-12-08T22:00:58Z

Vladimir.nesmelov:

В ориентированном взвешанном графе <tex>G = (V, E)</tex>, вес рёбер которого неотрицателен и определяется весовой функцией <tex>w(uv) \geqslant 0</tex>, Алгоритм Дейкстры находит длину кратчайшего пути из одной вершины <tex>s</tex> до всех остальных.

== Алгоритм ==
В алгоритме поддерживается множество вершин <tex>S</tex>, для которых уже вычислены кратчайшие пути к ним из вершины <tex>s</tex>. На каждой итерации основного цикла выбирается вершина <tex> u \in V \setminus S</tex>, которой на текущий момент соответствует минимальная оценка кратчайшего пути. Вершина <tex>u</tex> добавляется в множество <tex>S</tex> и производится релаксация всех исходящих из неё рёбер.

== Псевдокод ==
'''Dijkstra'''(<tex>G</tex>, <tex>w</tex>, <tex>s</tex>)
<tex>d \gets \infty</tex>
<tex>d[s] \gets 0</tex>
<tex>S \gets \emptyset</tex>
'''while''' <tex>V \setminus S \neq \emptyset</tex>
'''do''' ''argmin''(<tex>v : v \in V \setminus S, d[v]</tex>)
<tex>S \gets S \cup \{u\}</tex>
'''for''' <tex>(uv) \in E</tex>
'''do''' ''relax''(<tex>u</tex>, <tex>v</tex>, <tex>w</tex>)

== Обоснование корректности работы ==
{{Теорема
|statement=После окончания работы алгоритма Дейкстры для всех вершин <tex>u \in V</tex> будет выполняться равенство <tex>d[u] = \delta(s, u)</tex>
|proof=
Рассмотрим инвариант основного цикла: в начале каждой итерации для всех вершин <tex>v \in S</tex> выполняется <tex>d[v] = \delta(s, v)</tex>

'''Инициализация'''. Изначально множество <tex>S</tex> пусто, инвариант выполняется.

[[Файл:DijkstraProove.png|thumb|right|Рис. 1]]
'''Сохранение'''. Покажем, что при каждой итерации инвариант сохраняется для каждой вершины, добавленной в <tex>S</tex>, для этого воспользуемся методом «от противного». Предположим, что <tex>u</tex> первая добавленная в <tex>S</tex> вершина, для которой равенство <tex>d[u] = \delta(s, u)</tex> не выполняется. Рассмотрим ситуацию, сложившуюся в начале итерации, в которой <tex>u</tex> будет добавлена в <tex>S</tex>. Рассмотрев кратчайший путь из <tex>s</tex> в <tex>u</tex>, можно получить противоречие, заключающееся в том, что на рассматриваемый момент справедливо равенство <tex>d[u] = \delta(s, u)</tex>. Должно выполняться условие <tex>u \neq s</tex>, так как <tex>s</tex> является первой вершиной, добавленной в <tex>S</tex> и в момент её добавления равенство <tex>d[u] = \delta(s, u)</tex> выполняется. Из условия <tex>u \neq s</tex> следует, в частности, что <tex>S</tex> не пусто. Из вершины <tex>s</tex> в вершину <tex>u</tex> должен существовать какой-нибудь путь, так как иначе выполняется соотношение <tex>d[u] = \delta(s, u) = \infty</tex>, нарушающее предположение о том, что равенство <tex>d[u] = \delta(s, u)</tex> не выполняется. Из существования пути следует, что существует и кратчайший путь <tex>p</tex> из <tex>s</tex> в <tex>u</tex>. Перед добавлением <tex>u</tex> в <tex>S</tex> путь <tex>p</tex> соединяет вершину из множества <tex>S</tex> с вершиной принадлежащей множеству <tex>V \setminus S</tex>. Рассмотрим первую вершину <tex>y</tex> на пути <tex>p</tex> принадлежащую <tex>V \setminus S</tex>, и положим, что её предшествует вершина <tex>x \in S</tex>. Тогда, как видно из рис.1, путь <tex>p</tex> можно разложить на составляющие <tex>s \overset{p_1}{\leadsto} x \to y \overset{p_2}{\leadsto} u</tex>.

Утверждается, что в момент добавления вершины <tex>u</tex> в множество <tex>S</tex>, выполняется равенство <tex>d[u] = \delta(s, y)</tex>. Так как вершина <tex>u</tex> выбрана как первая вершина, после добавления которой в множество <tex>S</tex> не выполянется соотношение <tex>d[u] = \delta(s, u)</tex>, то после добавления вершины <tex>x</tex> в <tex>S</tex> справедливо равенство <tex>d[x] = \delta(s, x)</tex>. В это время происходит релаксация ребра <tex>xy</tex>. В это время происходит релаксация ребра <tex>xy</tex>, поэтому вышеописанное утверждение выполняется.

Поскольку на кратчайшем пути из <tex>s</tex> в <tex>u</tex> вершина <tex>y</tex> находиться перед <tex>u</tex> и вес каждого из ребер выражается неотрицательным значением, выполняется неравенство <tex>\delta(s, y) \leqslant \delta(s, u)</tex>, поэтому <tex>d[y] = \delta(s, y) \leqslant \delta(s, u) \leqslant d[u]</tex>. Но так как и вершина <tex>u</tex>, и вершина <tex>y</tex> во время выбора вершины <tex>u</tex> находились в множестве <tex>V \setminus S</tex>, выполняется неравенство <tex>d[u] \leqslant d[y]</tex>. Таким образом, оба <tex>d[y] = \delta(s, y) = \delta(s, u) = d[u]</tex>.

Значит, <tex>d[u] = \delta(s, u)</tex>, что противоречит нашему выбору вершины <tex>u</tex>. Следовательно, во время добавления вершины <tex>u</tex> в множество <tex>S</tex> выполняется равенство<tex>d[u] = \delta(s, u)</tex>, а следовательно, оно выполняется и в дальнейшем.

'''Завершение'''. По завершении работы алгоритма множество <tex>V \setminus S</tex> пусто. Из этого равенства следует, что <tex>S = V</tex>. Таким образом, для всех вершин <tex>u \in V</tex> выполняется равенство <tex>d[u] = \delta(s, u)</tex>.
}}

== Оценка сложности ==
Основной цикл выполняется <tex>V</tex> раз. Релаксация выполниться всего <tex>E</tex> раз. В реализации алгоритма присутствует функция ''argmin'', асимптотика её работы зависит от реализации.

Таким образом:
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=30%
!style="background:#f2f2f2"|Структура данных для хранения множества <tex>V \setminus S</tex>
!style="background:#f2f2f2"|Асимптотика времени работы
|-
|style="background:#f9f9f9"|Наивная реализация
|style="background:#f9f9f9"|<tex>O(V^2+E)</tex>
|-
|style="background:#f9f9f9"|Куча
|style="background:#f9f9f9"|<tex>O(E\log{V})</tex>
|-
|style="background:#f9f9f9"|Куча Фибоначчи
|style="background:#f9f9f9"|<tex>O(V\log{V}+E)</tex>
|}

== Литература ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах ]]

Алгоритмы и структуры данных

2010-12-08T21:35:27Z

Vladimir.nesmelov: Обновление тем до состояния на 08.12.2010

Алгоритм Дейкстры

2010-12-07T06:58:58Z

Vladimir.nesmelov:

В ориентированном взвешанном графе <tex>G = (V, E)</tex>, вес рёбер которого неотрицателен и определяется весовой функцией <tex>w(uv) \geqslant 0</tex>, Алгоритм Дейкстры находит длину кратчайшего пути из одной вершины <tex>s</tex> до всех остальных.

== Алгоритм ==
В алгоритме поддерживается множество вершин <tex>S</tex>, для которых уже вычислены кратчайшие пути к ним из вершины <tex>s</tex>. На каждой итерации основного цикла выбирается вершина <tex> u \in V \setminus S</tex>, которой на текущий момент соответствует минимальная оценка кратчайшего пути. Вершина <tex>u</tex> добавляется в множество <tex>S</tex> и производится релаксация всех исходящих из неё рёбер.

== Псевдокод ==
'''Dijkstra'''(<tex>G</tex>, <tex>w</tex>, <tex>s</tex>)
<tex>d \gets \infty</tex>
<tex>d[s] \gets 0</tex>
<tex>S \gets \emptyset</tex>
'''while''' <tex>V \setminus S \neq \emptyset</tex>
'''do''' ''argmin''(<tex>v : v \in V \setminus S, d[v]</tex>)
<tex>S \gets S \cup \{u\}</tex>
'''for''' <tex>(uv) \in E</tex>
'''do''' ''relax''(<tex>u</tex>, <tex>v</tex>, <tex>w</tex>)

== Обоснование корректности работы ==
{{Теорема
|statement=После окончания работы алгоритма Дейкстры для всех вершин <tex>u \in V</tex> будет выполняться равенство <tex>d[u] = \delta(s, u)</tex>
|proof=
Рассмотрим инвариант основного цикла: в начале каждой итерации для всех вершин <tex>v \in S</tex> выполняется <tex>d[v] = \delta(s, v)</tex>

'''Инициализация'''. Изначально множество <tex>S</tex> пусто, инвариант выполняется.

[[Файл:DijkstraProove.png|thumb|right|Рис. 1]]
'''Сохранение'''. Покажем, что при каждой итерации инвариант сохраняется для каждой вершины, добавленной в <tex>S</tex>, для этого воспользуемся методом «от противного». Предположим, что <tex>u</tex> первая добавленная в <tex>S</tex> вершина, для которой равенство <tex>d[u] = \delta(s, u)</tex> не выполняется. Рассмотрим ситуацию, сложившуюся в начале итерации, в которой <tex>u</tex> будет добавлена в <tex>S</tex>. Рассмотрев кратчайший путь из <tex>s</tex> в <tex>u</tex>, можно получить противоречие, заключающееся в том, что на рассматриваемый момент справедливо равенство <tex>d[u] = \delta(s, u)</tex>. Должно выполняться условие <tex>u \neq s</tex>, так как <tex>s</tex> является первой вершиной, добавленной в <tex>S</tex> и в момент её добавления равенство <tex>d[u] = \delta(s, u)</tex> выполняется. Из условия <tex>u \neq s</tex> следует, в частности, что <tex>S</tex> не пусто. Из вершины <tex>s</tex> в вершину <tex>u</tex> должен существовать какой-нибудь путь, так как иначе выполняется соотношение <tex>d[u] = \delta(s, u) = \infty</tex>, нарушающее предположение о том, что равенство <tex>d[u] = \delta(s, u)</tex> не выполняется. Из существования пути следует, что существует и кратчайший путь <tex>p</tex> из <tex>s</tex> в <tex>u</tex>. Перед добавлением <tex>u</tex> в <tex>S</tex> путь <tex>p</tex> соединяет вершину из множества <tex>S</tex> с вершиной принадлежащей множеству <tex>V \setminus S</tex>. Рассмотрим первую вершину <tex>y</tex> на пути <tex>p</tex> принадлежащую <tex>V \setminus S</tex>, и положим, что её предшествует вершина <tex>x \in S</tex>. Тогда, как видно из рис.1, путь <tex>p</tex> можно разложить на составляющие <tex>s \overset{p_1}{\leadsto} x \to y \overset{p_2}{\leadsto} u</tex>.

Утверждается, что в момент добавления вершины <tex>u</tex> в множество <tex>S</tex>, выполняется равенство <tex>d[u] = \delta(s, y)</tex>. Так как вершина <tex>u</tex> выбрана как первая вершина, после добавления которой в множество <tex>S</tex> не выполянется соотношение <tex>d[u] = \delta(s, u)</tex>, то после добавления вершины <tex>x</tex> в <tex>S</tex> справедливо равенство <tex>d[x] = \delta(s, x)</tex>. В это время происходит релаксация ребра <tex>xy</tex>. В это время происходит релаксация ребра <tex>xy</tex>, поэтому вышеописанное утверждение выполняется.

Поскольку на кратчайшем пути из <tex>s</tex> в <tex>u</tex> вершина <tex>y</tex> находиться перед <tex>u</tex> и вес каждого из ребер выражается неотрицательным значением, выполняется неравенство <tex>\delta(s, y) \leqslant \delta(s, u)</tex>, поэтому <tex>d[y] = \delta(s, y) \leqslant \delta(s, u) \leqslant d[u]</tex>. Но так как и вершина <tex>u</tex>, и вершина <tex>y</tex> во время выбора вершины <tex>u</tex> находились в множестве <tex>V \setminus S</tex>, выполняется неравенство <tex>d[u] \leqslant d[y]</tex>. Таким образом, оба <tex>d[y] = \delta(s, y) = \delta(s, u) = d[u]</tex>.

Значит, <tex>d[u] = \delta(s, u)</tex>, что противоречит нашему выбору вершины <tex>u</tex>. Следовательно, во время добавления вершины <tex>u</tex> в множество <tex>S</tex> выполняется равенство<tex>d[u] = \delta(s, u)</tex>, а следовательно, оно выполняется и в дальнейшем.

'''Завершение'''. По завершении работы алгоритма множество <tex>V \setminus S</tex> пусто. Из этого равенства следует, что <tex>S = V</tex>. Таким образом, для всех вершин <tex>u \in V</tex> выполняется равенство <tex>d[u] = \delta(s, u)</tex>.
}}

== Оценка сложности ==
Основной цикл выполняется <tex>V</tex> раз. Релаксация выполниться всего <tex>E</tex> раз. В реализации алгоритма присутствует функция ''argmin'', ассимптотика её работы зависит от реализации.

Таким образом:
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=30%
!style="background:#f2f2f2"|Структура данных для хранения множества <tex>V \setminus S</tex>
!style="background:#f2f2f2"|Ассимптотика времени работы
|-
|style="background:#f9f9f9"|Наивная реализация
|style="background:#f9f9f9"|<tex>O(V^2+E)</tex>
|-
|style="background:#f9f9f9"|Куча
|style="background:#f9f9f9"|<tex>O(E\log{V})</tex>
|-
|style="background:#f9f9f9"|Куча Фибоначчи
|style="background:#f9f9f9"|<tex>O(V\log{V}+E)</tex>
|}

== Литература ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах ]]

Файл:DijkstraProove.png

2010-12-07T06:52:53Z

Vladimir.nesmelov: Иллюстрация к доказательству корректности работы алгоритма Дейкстры

Иллюстрация к доказательству корректности работы алгоритма Дейкстры

Алгоритм Дейкстры

2010-12-06T07:34:53Z

Vladimir.nesmelov: Добавлено доказательство и оценка времени работы

{{В разработке}}

В ориентированном взвешанном графе <tex>G = (V, E)</tex>, вес рёбер которого неотрицателен и определяется весовой функцией <tex>w(uv) \geqslant 0</tex>, Алгоритм Дейкстры находит длину кратчайшего пути из одной вершины <tex>s</tex> до всех остальных.

== Алгоритм ==
В алгоритме поддерживается множество вершин <tex>S</tex>, для которых уже вычислены кратчайшие пути к ним из вершины <tex>s</tex>. На каждой итерации основного цикла выбирается вершина <tex> u \in V \setminus S</tex>, которой на текущий момент соответствует минимальная оценка кратчайшего пути. Вершина <tex>u</tex> добавляется в множество <tex>S</tex> и производится релаксация всех исходящих из неё рёбер.

== Псевдокод ==
'''Dijkstra'''(<tex>G</tex>, <tex>w</tex>, <tex>s</tex>)
<tex>d \gets \infty</tex>
<tex>d[s] \gets 0</tex>
<tex>S \gets \emptyset</tex>
'''while''' <tex>V \setminus S \neq \emptyset</tex>
'''do''' ''argmin''(<tex>v : v \in V \setminus S, d[v]</tex>)
<tex>S \gets S \cup \{u\}</tex>
'''for''' <tex>(uv) \in E</tex>
'''do''' ''relax''(<tex>u</tex>, <tex>v</tex>, <tex>w</tex>)

== Обоснование корректности работы ==
{{Теорема
|statement=После окончания работы алгоритма Дейкстры для всех вершин <tex>u \in V</tex> будет выполняться равенство <tex>d[u] = \delta(s, u)</tex>
|proof=
Рассмотрим инвариант основного цикла: в начале каждой итерации для всех вершин <tex>v \in S</tex> выполняется <tex>d[v] = \delta(s, v)</tex>

'''Инициализация'''. Изначально множество <tex>S</tex> пусто, инвариант выполняется.

[[Файл:DijkstraProove.png|thumb|right|Рис. 1]]
'''Сохранение'''. Покажем, что при каждой итерации инвариант сохраняется для каждой вершины, добавленной в <tex>S</tex>, для этого воспользуемся методом «от противного». Предположим, что <tex>u</tex> первая добавленная в <tex>S</tex> вершина, для которой равенство <tex>d[u] = \delta(s, u)</tex> не выполняется. Рассмотрим ситуацию, сложившуюся в начале итерации, в которой <tex>u</tex> будет добавлена в <tex>S</tex>. Рассмотрев кратчайший путь из <tex>s</tex> в <tex>u</tex>, можно получить противоречие, заключающееся в том, что на рассматриваемый момент справедливо равенство <tex>d[u] = \delta(s, u)</tex>. Должно выполняться условие <tex>u \neq s</tex>, так как <tex>s</tex> является первой вершиной, добавленной в <tex>S</tex> и в момент её добавления равенство <tex>d[u] = \delta(s, u)</tex> выполняется. Из условия <tex>u \neq s</tex> следует, в частности, что <tex>S</tex> не пусто. Из вершины <tex>s</tex> в вершину <tex>u</tex> должен существовать какой-нибудь путь, так как иначе выполняется соотношение <tex>d[u] = \delta(s, u) = \infty</tex>, нарушающее предположение о том, что равенство <tex>d[u] = \delta(s, u)</tex> не выполняется. Из существования пути следует, что существует и кратчайший путь <tex>p</tex> из <tex>s</tex> в <tex>u</tex>. Перед добавлением <tex>u</tex> в <tex>S</tex> путь <tex>p</tex> соединяет вершину из множества <tex>S</tex> с вершиной принадлежащей множеству <tex>V \setminus S</tex>. Рассмотрим первую вершину <tex>y</tex> на пути <tex>p</tex> принадлежащую <tex>V \setminus S</tex>, и положим, что её предшествует вершина <tex>x \in S</tex>. Тогда, как видно из рис.1, путь <tex>p</tex> можно разложить на составляющие <tex>s \overset{p_1}{\leadsto} x \to y \overset{p_2}{\leadsto} u</tex>.

Утверждается, что в момент добавления вершины <tex>u</tex> в множество <tex>S</tex>, выполняется равенство <tex>d[u] = \delta(s, y)</tex>. Так как вершина <tex>u</tex> выбрана как первая вершина, после добавления которой в множество <tex>S</tex> не выполянется соотношение <tex>d[u] = \delta(s, u)</tex>, то после добавления вершины <tex>x</tex> в <tex>S</tex> справедливо равенство <tex>d[x] = \delta(s, x)</tex>. В это время происходит релаксация ребра <tex>xy</tex>. В это время происходит релаксация ребра <tex>xy</tex>, поэтому вышеописанное утверждение выполняется.

Поскольку на кратчайшем пути из <tex>s</tex> в <tex>u</tex> вершина <tex>y</tex> находиться перед <tex>u</tex> и вес каждого из ребер выражается неотрицательным значением, выполняется неравенство <tex>\delta(s, y) \leqslant \delta(s, u)</tex>, поэтому <tex>d[y] = \delta(s, y) \leqslant \delta(s, u) \leqslant d[u]</tex>. Но так как и вершина <tex>u</tex>, и вершина <tex>y</tex> во время выбора вершины <tex>u</tex> находились в множестве <tex>V \setminus S</tex>, выполняется неравенство <tex>d[u] \leqslant d[y]</tex>. Таким образом, оба <tex>d[y] = \delta(s, y) = \delta(s, u) = d[u]</tex>.

Значит, <tex>d[u] = \delta(s, u)</tex>, что противоречит нашему выбору вершины <tex>u</tex>. Следовательно, во время добавления вершины <tex>u</tex> в множество <tex>S</tex> выполняется равенство<tex>d[u] = \delta(s, u)</tex>, а следовательно, оно выполняется и в дальнейшем.

'''Завершение'''. По завершении работы алгоритма множество <tex>V \setminus S</tex> пусто. Из этого равенства следует, что <tex>S = V</tex>. Таким образом, для всех вершин <tex>u \in V</tex> выполняется равенство <tex>d[u] = \delta(s, u)</tex>.
}}

== Оценка сложности ==
Основной цикл выполняется <tex>V</tex> раз. Релаксация выполниться всего <tex>E</tex> раз. В реализации алгоритма присутствует функция ''argmin'', ассимптотика её работы зависит от реализации.

Таким образом:
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=30%
!style="background:#f2f2f2"|Структура данных для хранения множества <tex>V \setminus S</tex>
!style="background:#f2f2f2"|Ассимптотика времени работы
|-
|style="background:#f9f9f9"|Наивная реализация
|style="background:#f9f9f9"|<tex>O(V^2+E)</tex>
|-
|style="background:#f9f9f9"|Куча
|style="background:#f9f9f9"|<tex>O(E\log{V})</tex>
|-
|style="background:#f9f9f9"|Куча Фибоначчи
|style="background:#f9f9f9"|<tex>O(V\log{V}+E)</tex>
|}

== Литература ==
* ''Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К.'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах ]]

Алгоритм Дейкстры

2010-12-06T05:43:43Z

Vladimir.nesmelov: Добавлена часть доказательства

Алгоритм Дейкстры

2010-12-06T04:29:21Z

Vladimir.nesmelov:

Алгоритм Дейкстры

2010-12-06T01:40:20Z

Vladimir.nesmelov: Новая страница: «{{В разработке}} == Алгоритм == В ориентированном взвешанном графе <tex>G = (V, E)</tex>, вес рёбер кот…»

{{В разработке}}

== Алгоритм ==
В ориентированном взвешанном графе <tex>G = (V, E)</tex>, вес рёбер которого неотрицателен, Алгоритм Дейкстры находит длинну кратчайшего пути из одной вершины <tex>s</tex> до всех остальных.
== Псевдокод ==
'''Dijkstra'''(<tex>G</tex>, <tex>w</tex>, <tex>s</tex>)
<tex>d \gets \infty</tex>
<tex>d[s] \gets 0</tex>
<tex>S \gets \emptyset</tex>
<tex>Q \gets V[G]</tex>
'''while''' <tex>Q \neq \emptyset</tex>
'''do''' <tex>u \gets</tex> ''Extract_Min''(<tex>Q</tex>)
<tex>s \gets S \cup \{u\}</tex>
'''for''' <tex>(uv) \in E</tex>
'''do''' ''Relax''(<tex>u</tex>, <tex>v</tex>, <tex>w</tex>)
== Обоснование корректности работы ==
== Оценка сложности ==
== литература ==
* ''Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К.'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах ]]

Алгоритмы и структуры данных

2010-12-02T00:27:45Z

Vladimir.nesmelov: Обновление тем до состояния на 01.12.2010

Алгоритмы и структуры данных

2010-11-18T02:04:00Z

Vladimir.nesmelov: Обновление тем до состояния на 17.11.2010

Категория:Кратчайшие пути в графах

2010-11-11T02:35:21Z

Vladimir.nesmelov: Новая страница: «Категория: Алгоритмы и структуры данных»

[[Категория: Алгоритмы и структуры данных]]

Алгоритмы и структуры данных

2010-11-11T02:32:38Z

Vladimir.nesmelov: Обновление тем до состояния на 10.11.2010

Использование обхода в глубину для поиска цикла

2010-11-10T23:00:53Z

Vladimir.nesmelov: Добавлены категории

= Постановка задачи =
Пусть дан [[ориентированный граф|ориентированный граф]] без петель и кратных рёбер. Требуется проверить наличие [[Основные определения теории графов|цикла]] в этом графе.

Решим эту задачу с помощью [[Обход в глубину, цвета вершин|поиска в глубину]] за O (M).

= Алгоритм =

Произведём серию поисков в глубину в графе. Т.е. из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе - в чёрный. И если поиск в глубину пытается пойти в серую вершину, то это означает, что мы нашли цикл.

Сам цикл можно восстановить проходом по массиву предков.

= Реализация =

Здесь приведена реализация алгоритма на С++.

===С++===

vector < vector<int> > graph;
vector<int> color;

void dfs(int index)
{
color[index] = 1; // красит вершину в серый цвет
for (vector<int>::iterator i = graph[index].begin(); i != graph[index].end(); ++i)
{
if ( color[*i] == 0 )
dfs(*i);
if ( color[*i] == 1 )
print(); // вывод ответа
}
color[index] = 2; // красит вершину в черный цвет
}

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]

Использование обхода в глубину для проверки связности

2010-11-10T23:00:19Z

Vladimir.nesmelov: Добавлены категории

== Задача ==
Дан [[Основные определения теории графов|неориентированный граф]]. Необходимо проверить является ли он связным.

== Идея ==
Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Смысл алгоритма заключается в том, чтобы считать сколько вершин мы посетили во время обхода.

== Алгоритм ==
Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу перед выходом из процедуры. Запустимся от какой-то вершины нашего графа. По окончании работы процедуры dfs() сравним счётчик с нулём. Если они равны, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то в графе несколько компонент связности. Работает алгоритм за O(M + N).

== Псевдокод ==
string color[]; //изначально массив color заполнен значениями white.
int count = n; //счётчик количества вершин; изначально равен количеству вершин в графе
bool if_connected()
dfs(0); //запуск от какой-то вершины
if(count == 0)
return true;
else
return false;

int dfs(int u) //процедура обхода в глубину. запуск от номера вершины
for(v: uv - ребро)
if(color[v] == white)
dfs(v);
color[u] = black;
count--;

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]

Обход в глубину, цвета вершин

2010-11-10T22:59:42Z

Vladimir.nesmelov: Добавлены категории

'''Обход в глубину''' (поиск в глубину, англ. Depth-First Search, DFS) - один из основных методов обхода графа, часто используемый для [[Использование обхода в глубину для проверки связности|проверки связности]], поиска [[Использование обхода в глубину для поиска цикла в ориентированном графе|цикла]] и [[Использование обхода в глубину для поиска компонент сильной связности|компонент сильной связности]] и для [[Использование обхода в глубину для топологической сортировки|топологической сортировки]].

== Алгоритм ==

=== Общая идея ===
Общая идея алгоритма состоит в следующем: для каждой ''не пройденной'' вершины необходимо найти все ''не пройденные'' смежные вершины и повторить поиск для них.

=== Пошаговое представление ===
#Выбираем любую вершину из еще ''не пройденных'', обозначим ее как u.
#Запускаем процедуру DFS(u)
#*Помечаем вершину u как ''пройденную''
#*Для каждой ''не пройденной'' смежной с u вершиной (назовем ее v) запускаем DFS(v)
#Повторяем шаги 1 и 2, пока все вершины не окажутся ''пройденными''.

=== Реализация ===
vector<bool> visited; //вектор для хранения информации о ''пройденных'' и ''не пройденных'' вершинах

void dfs(int u)
{
visited[u] = true; //помечаем вершину как пройденную
for (v таких, что (u, v) - ребро в G) //проходим по смежным с u вершинам
if (!visited[v]) //проверяем, не находились ли мы ранее в выбранной вершине
dfs(v);
}

int main()
{
... //задание графа G с количеством вершин n.
visited.assign(n, false); //в начале все вершины в графе ''не пройденные''
for (int i = 0; i < n; ++i) //проходим по всем вершинам графа...
if (!visited[i]) //...не забыв проверить, были мы уже в очередной вершине или нет
dfs(i);
return 0;
}

== Цвета вершин ==
Зачастую, простой информации "были/не были в вершине" не хватает для конкретных целей. 
Поэтому в процессе алгоритма вершинам задают некоторые цвета: 
:если вершина ''белая'', значит, мы в ней еще не были, вершина ''не пройдена''; 
:''серая'' - вершина ''проходится'' в текущей процедуре DFS; 
:''черная'' - вершина ''пройдена'', все итерации DFS от нее завершены. 

Такие "метки" в основном используются при [[Использование обхода в глубину для поиска цикла в ориентированном графе|поиске цикла]].

=== Реализация ===
Отличие реализации с цветами от предыдущей лишь в массиве visited, который мы назовем теперь color, и дополнительной ''черной'' "метки". При этом цвета вершин будут заданы следующим образом: ''белый'' - 0, ''серый'' - 1, ''черный'' - 2. Все отличия помечены '''жирным''' шрифтом.

vector<'''int'''> '''color'''; //вектор для хранения информации '''о цвете''' вершин

void dfs(int u)
{
'''color[u] = 1; //раскрашиваем вершину в ''серый'' цвет'''
for (v таких, что (u, v) - ребро в G) //проходим по смежным с u вершинам
if (!color[v]) //проверяем, не находились ли мы ранее в выбранной вершине, '''условие не требует изменений,'''
dfs(v); '''//поскольку мы считаем вершину "не пройденной" только тогда, когда она ''белого'' цвета, т.е. когда color[v] = 0'''
'''color[u] = 2; //раскрашиваем вершину в ''черный'' цвет'''
}

int main()
{
... //задание графа G с количеством вершин n.
'''color.assign(n, 0);''' //в начале все вершины в графе ''не пройденные'', '''т.е. ''белые''.'''
for (int i = 0; i < n; ++i) //проходим по всем вершинам графа...
if (!visited[i]) //...не забыв проверить, были мы уже в очередной вершине или нет
dfs(i);
return 0;
}

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]

Основные определения теории графов

2010-10-28T02:14:27Z

Vladimir.nesmelov: корректировка формул

==Граф==
{{Определение
|definition =
Графом <tex>G</tex> называется пара <tex>G = (V, E);</tex> где V - конечное множество вершин, а <tex> E \subset V \times V </tex> - множество рёбер.
}}
В неориентированном графе <tex>(v, u) = (u, v)</tex>.

==Ребро==
====Для неориентированного графа====
{{Определение
|definition =
Ребром называют неупорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}
====Для ориентированного графа====
{{Определение
|definition =
Ребром называют упорядоченную пару вершин <tex> (v, u) \in E </tex>.
}}

==Степень вершины==
====Для неориентированного графа====
{{Определение
|definition =
Степенью вершины vi называется число рёбер инцидентных <tex>v_i</tex>, и обозначается deg <tex>v_i</tex>
}}
Говорят, что ребро <tex> e = (u, v) </tex> инцидентно вершине a, если <tex>u = a</tex> или <tex>v = a</tex>.

====Для ориентированного графа====
{{Определение
|definition =
Полустепенью входа вершины vi называется число рёбер, входящих в эту вершину, и обозначается <tex>deg^+</tex> <tex>v_i</tex>.
}}
{{Определение
|definition =
Полустепенью выхода вершины <tex>v_i</tex> называется число рёбер, выходящих из этой вершину, и обозначается <tex>deg^-</tex> vi.
}}

==Петля==
{{Определение
|definition =
Петлёй в ориентированном графе называется ребро, концы которого совпадают, то есть <tex>e=\{v,v\}</tex>.
}}
По умолчанию петли в неориентированном графе запрещены.

==Путь==
{{Определение
|definition =
Путём в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>; где <tex>e_i = (v_{i-1}; v_i)</tex>.
}}

==Цикл==
====Для ориентированного графа====
{{Определение
|definition =
Циклом называется путь у которого <tex>v_0 = v_k; k > 0</tex>, а так же <tex>v_0 e_1 v_1 ... e_k v_k \sim u_0 f_1 u_1 ... f_k u_k</tex>; где <tex>u_i = v_{(i+j) \pmod k}; f_i = e_{(i+j) \pmod k}; i = 1..k</tex>
}}

====Для неориентированного графа====
{{Определение
|definition =
Циклом называется путь в котором нет двух одинаковых рёбер подряд, а также начало и конец которого совпадают, то есть <tex>v_0 = v_k</tex>
}}

Категория:Обход в глубину

2010-10-27T22:02:02Z

Vladimir.nesmelov: Новая страница: «Категория: Алгоритмы и структуры данных»

[[Категория: Алгоритмы и структуры данных]]

Категория:Раскраски графов

2010-10-27T22:00:45Z

Vladimir.nesmelov: Новая страница: «Категория: Алгоритмы и структуры данных»

[[Категория: Алгоритмы и структуры данных]]

Алгоритмы и структуры данных

2010-10-27T21:37:29Z

Vladimir.nesmelov: Обновление тем до состояния на 27.10.2010

Хроматический многочлен

2010-10-23T03:06:38Z

Vladimir.nesmelov: Добавлены категории

{{Определение
|definition=
}}

== Хроматический многочлен полного графа ==
<tex>P(K_{n},x)=x(x-1)...(x-n+1)=x^{\underline{n}}</tex>, так как первую вершину полного графа <tex>K_{n}</tex> можно окрасить в любой из <tex>x</tex> цветов, вторую - в любой из оставшихся <tex>x-1</tex> цветов и т. д. Очевидно, что если <tex>x</tex> меньше <tex>n</tex>, то и многочлен равен <tex>0</tex>, потому что один из его множителей <tex>0</tex>. 
Примечание. В некоторых источниках <tex>x^{\underline{n}}</tex> (<tex>x</tex> в <tex>n</tex>-убывающей) обозначают <tex>x^{(n)}</tex>. Это не очень удобно, так как легко спутать с <tex>n</tex>-ой производной.

== Хроматический многочлен пустого графа ==
<tex>P(O_{n},x)=x^{n}</tex>, так как каждую из <tex>n</tex> вершин нулевого графа <tex>O_{n}</tex> можно независимо окрасить в любой из <tex>x</tex> цветов. 
Примечание. Нулевой граф <tex>O_{n}</tex> также можно обозначать <tex>\overline{K_{n}}</tex> (дополнительный граф для полного графа <tex>K_{n}</tex>).

== Хроматический многочлен дерева ==
{{Теорема
|about=
хроматический многочлен дерева
|statement=
Граф <tex>G</tex> с <tex>n</tex> вершинами является деревом тогда и только тогда, когда <tex>P(G,x)=x(x-1)^{n-1}</tex>.
|proof=
Сначала покажем, что хроматический многочлен любого дерева <tex>T</tex> с <tex>n</tex> вершинами есть <tex>x(x-1)^{n-1}</tex>. 
Доказательство индукцией по числу <tex>n</tex>. Для <tex>n=1</tex> и <tex>n=2</tex> результат очевиден. Предположим, что <tex>P(T',x)=x(x-1)^{n-2}</tex> для любого дерева <tex>T'</tex> с количеством вершин равным <tex>n-1</tex>. Пусть <tex>uv</tex> - ребро дерева <tex>T</tex>, такое что <tex>v</tex> является висячей вершиной. Хроматический многочлен дерева <tex>T</tex> без ребра <tex>uv</tex> равен <tex>P(T/uv,x)=x(x-1)^{n-2}</tex> по нашему предположению. Вершину <tex>v</tex> можно окрасить <tex>x-1</tex> способом, так как её цвет должен только лишь отличаться от цвета вершины <tex>u</tex>. Итого: <tex>P(T,x)=(x-1)P(T/uv,x)=x(x-1)^{n-1}</tex>. 
Обратно, пусть <tex>G</tex> - граф, у которого <tex>P(G,x)=x(x-1)^{n-1}</tex>. Тогда верны 2 следующих утверждения: 
1. Граф <tex>G</tex> связен, потому что если было бы 2 компоненты связности (или больше), то <tex>P(G,x)</tex> делился бы на <tex>x^2</tex> без остатка. 
2. В графе <tex>G</tex> количество рёбер равно <tex>n-1</tex>, так как по теореме о коэффициентах хроматического многочлена, количество рёбер в графе соответствует коэффициенту при <tex>x^{n-1}</tex>, взятому со знаком минус. В нашем случае, этот коэффициент удобно искать, используя бином Ньютона: 
<tex>{P(G,x)=x(x-1)^{n-1}=x(x^{n-1}-\begin{pmatrix}n-1\\1\end{pmatrix}x^{n-2}+\begin{pmatrix}n-1\\2\end{pmatrix}x^{n-3}-...+(-1)^{n-1})=x^{n}-(n-1)x^{n-1}+...+(-1)^{n-1}x}</tex> 
Из этих двух утверждений (связность и <tex>n-1</tex> ребро) следует, что граф <tex>G</tex> является деревом (см. [[Дерево, эквивалентные определения]], теорема, утверждения 1 и 3).
}}

== Коэффициенты хроматического многочлена ==
== Рекуррентные формулы для хроматических многочленов ==
== См. также ==
== Литература ==
1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. - СПб.: Издательство "Лань", 2010. - 368 с.: ил. - (Учебники для вузов. Специальная литература). '''ISBN 978-5-8114-1068-2''' 
2. Харари Ф. - Теория графов: Изд. 4-е. - М.: Книжный дом "ЛИБРОКОМ", 2009. - 296 с. '''ISBN 978-5-397-00622-4'''

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Раскраски графов]]

Хроматический многочлен

2010-10-21T20:11:12Z

Vladimir.nesmelov: Новая страница: «{{Определение |definition= }} == Хроматический многочлен полного графа == == Хроматический многочл…»

{{Определение
|definition=
}}

== Хроматический многочлен полного графа ==
== Хроматический многочлен пустого графа ==
== Хроматический многочлен дерева ==
== Коэффициенты хроматического многочлена ==
== Рекуррентные формулы для хроматических многочленов ==
== См. также ==
== Литература ==

Алгоритмы и структуры данных

2010-10-21T20:04:45Z

Vladimir.nesmelov: /* Раскраски графов */

Алгоритмы и структуры данных

2010-10-21T20:02:58Z

Vladimir.nesmelov: /* Раскраски графов */

Укладка графа с планарными компонентами рёберной двусвязности

2010-10-21T20:00:00Z

Vladimir.nesmelov:

{{Теорема
|about=об укладке графа с планарными компонентами реберной двусвязности
|statement=Если [[Отношение реберной двусвязности|компоненты реберной двусвязности]] (к.р.д.) [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] <tex>G</tex> [[Укладка графа на плоскости|планарны]], то и сам граф <tex>G</tex> планарен.
|proof=

Докажем для начала ряд вспомогательных лемм.

{{Лемма
|id=l1
|about=I
|statement=Граф <tex>G</tex> планарен тогда и только тогда, когда он обладает укладкой на сфере
|proof=

Рассмотрим укладку графа <tex>G</tex> на сфере. Возьмем на сфере точку <tex>N</tex>, не лежащую на ребре, и не вершину. Выберем на сфере точку <tex>S</tex> противолежащую <tex>N</tex> (<tex>N</tex> и <tex>S</tex> лежат на одном диаметре и при этом не совпадают). Проведем через точку <tex>S</tex> касательную к сфере плоскость. Спроектируем на плоскость все точки сферы, проведя все возможные лучи из точки <tex>N</tex> через точки сферы до пересечения с плоскостью. Ясно, что эта проекция дает укладку графа <tex>G</tex> на плоскости.

Обратно рассмотрим укладку графа <tex>G</tex> на плоскости. Возьмем сферу, которая касается плоскости, и обозначим точку касания за <tex>S</tex>. Противолежащую <tex>S</tex> точку на сфере обозначим за <tex>N</tex>. Проведем все возможные лучи от точек плоскости через точки сферы до точки <tex>N</tex>. Ясно что при этом укладка графа <tex>G</tex> на плоскости будет перенесена на некоторую укладку графа <tex>G</tex> на сфере.
}}

{{Лемма
|id=l2
|about=II
|statement=Для любого выделенного ребра планарного графа найдется такая укладка графа на плоскости, что выделенное ребро будет лежать на границе внешней грани.
|proof=

Возьмем укладку графа на сфере. Перенесем эту укладку графа на сфере в укладку на плоскости так как это сделано в [[#l1|лемме I]], за точку <tex>N</tex> возьмем точку на сфере, не лежащую на ребре, не являющуюся вершиной и принадлежащую грани на границе которой лежит выделенное ребро. Полученная укладка на плоскости обладает нужным нам свойством.
}}

Докажем утверждение теоремы для одной из компонент связности графа <tex>G</tex>. Ясно, что имея укладки на плоскости каждой из компонент связности графа, мы можем получить укладку на плоскости и всего графа.
Итак пусть граф <tex>G</tex> связен. Рассмотрим связный подграф <tex>T</tex> графа к.р.д. графа <tex>G</tex>. Из [[Граф компонент реберной двусвязности|леммы]] и из связности <tex>T</tex> получаем, что <tex>T</tex> — [[Дерево, эквивалентные определения|дерево]].

Докажем индукцией по числу вершин в графе <tex>T</tex>, что подграф <tex>G'</tex> графа <tex>G</tex> состоящий из к.р.д. и мостов графа <tex>G</tex> принадлежащих графу <tex>T</tex> планарен (далее будем говорить, что <tex>G'</tex> соответствует <tex>T</tex>).

'''База индукции.'''

<div style="border:1px solid #000; width:90%; margin: 10px; padding:4px; background-color: #fdfdfd; padding-left:10px;">
Если <tex>|VT| = 1</tex>, то граф <tex>T</tex> - тривиальный. Его единственная вершина - это к.р.д. графа <tex>G</tex>, которая по утверждению теоремы - планарна.
</div>

'''Индукционный переход.'''

<div style="border:1px solid #000; width:90%; margin: 10px; padding:4px; background-color: #fdfdfd; padding-left:10px;">
Пусть утверждение верно для <tex>|VT| < m</tex>. Рассмотрим <tex>T</tex>, для которого <tex>|VT| = m > 1</tex>, и соответствующий <tex>T</tex> подграф <tex>G'</tex> графа <tex>G</tex>. Докажем, что <tex>G'</tex> планарен.

Положим <tex>G_1</tex> — к.р.д. графа <tex>G'</tex> являющийся висячей вершиной дерева <tex>T</tex>, a <tex>e</tex> — мост в <tex>G'</tex> инцидентный <tex>G_1</tex> в <tex>T</tex>. <tex>G_1</tex> планарен по утверждению теоремы, т.к. к.р.д. графа <tex>G'</tex> совпадают с к.р.д. графа <tex>G</tex>. Далее рассмотрим подграф <tex>G_2</tex> графа <tex>G'</tex>, соответствующий дереву <tex>T\backslash \{G_1\}</tex>. Поскольку <tex>G_1</tex> — висячая вершина <tex>T</tex>, то <tex>T\backslash \{G_1\}</tex> связен, и, очевидно, также как и <tex>T</tex> является подграфом графа к.р.д. <tex>G</tex>. Итак <tex>G_2</tex> планарен по предположению индукции, т.к. <tex>|V(T\backslash \{u\})| = |VT| - 1 = m - 1 < m</tex>.

Из определения ребер дерева к.р.д. получаем, что графы <tex>G_1</tex> и <tex>G_2</tex> соединены в графе <tex>G'</tex> единственным мостом <tex>e \in G'</tex> инцидентным блоку <tex>G_1</tex> в дереве <tex>T</tex>. Поскольку <tex>T = \{G_1\}\cup e\cup \{G_2\}</tex>, то и <tex>G' = \{G_1\}\cup e\cup \{G_2\}</tex>. Покажем как из укладок <tex>G_1</tex> и <tex>G_2</tex> получить укладку <tex>G'</tex>.

Уложим <tex>G_2</tex> на сфере и уложим <tex>G_1</tex> на плоскости так, чтобы ребро <tex>e_1 \in G_1</tex> смежное с <tex>e</tex> в G' (если таковое имеется) оказалось на границе внешней грани (по [[#l2|лемме II]] это возможно). Если такого ребра <tex>e_1</tex> не существует, значит к.р.д. <tex>G_1</tex> — тривиальный граф. В таком случае возьмем любую укладку <tex>G_1</tex> на плоскости. Обозначим за <tex>u</tex> вершину из <tex>G_2</tex> инцедентную <tex>e</tex>. Сожмем часть плоскости, содержащую укладку <tex>G_1</tex>, так, чтобы она вмещалась в одну из граней укладки <tex>G_2</tex> смежную с <tex>u</tex>. Проведем жорднанову кривую, соответствующую ребру <tex>e</tex>, от вершины <tex>u</tex> к инцидентоной <tex>e</tex> вершине графа <tex>G_1</tex> так, чтобы она не пересекалась с укладками <tex>G_1</tex> и <tex>G_2</tex>. Мы получили укладку графа <tex>G'</tex> на сфере, а значит (по [[#l1|лемме I]]) <tex>G'</tex> планарен, следовательно предположение индукции верно.
</div>

Рассматривая в качестве <tex>T</tex> граф к.р.д. <tex>G</tex> получаем что <tex>G</tex> - планарен.
}}

'''Замечание.''' Доказательство теоремы непосредственно задает способ укладки графа <tex>G</tex>.

==Источники==

Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001.

H. Whitney - Non-separable and planar graphs - Trans. Amer. Math. Soc., 1932.

Алгоритмы и структуры данных

2010-10-21T19:58:42Z

Vladimir.nesmelov: /* Раскраски графов */ объединение хроматических многочленов разных графов

Теорема Понтрягина-Куратовского

2010-10-21T06:49:46Z

Vladimir.nesmelov: Добавлены категории, замена некоторых дефисов длинными тире

__TOC__

{{Теорема
|statement =
Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных <tex> K_{5} </tex>, и не содержит подграфов, гомеоморфных <tex> K_{3, 3} </tex> .
|proof =
=== Необходимость ===
Необходимость условия очевидна.
=== Достаточность ===
От противного: пусть существует непланарный граф, который не содержит подграфов, гомеоморфных <tex> K_{5} </tex> или <tex> K_{3, 3} </tex>. Пусть <tex> G </tex> — такой граф с наименьшим возможным числом рёбер, не содержащий изолированных вершин.
==== G связен ====
Если <tex> G </tex> не связен, то его компоненты связности планарны и, следовательно, сам граф <tex> G </tex> планарен.
==== G — обыкновенный граф ====
В самом деле, пусть в графе <tex> G </tex> есть петля или кратное ребро <tex> e </tex>. Тогда граф <tex> G - e </tex> планарен. Добавляя ребро <tex> e </tex> к графу <tex> G - e </tex> получим, что граф <tex> G </tex> он планарен.
==== G — блок ====
Пусть, от противного, в графе есть точка сочленения <tex> v </tex>. Через <tex> G_1 </tex> обозначим подграф графа <tex> G </tex>, порождённый вершинами одной из компонент связности графа <tex> G - v</tex> и вершинной <tex> v </tex>, а через
<tex> G_2 </tex> подграф графа <tex> G </tex>, порождённый вершинами остальных компонент связности графа <tex> G - v </tex> и вершиной <tex> v </tex>. (рис. 1)
[[Файл:p-k.1.png|thumb|right|рис. 1]]
Возьмём укладку графа <tex> G_1 </tex> на плоскости такую, что вершина <tex> v </tex> лежит на границе верхней грани. Затем во внешней грани графа <tex> G_1 </tex> возьмём укладку графа <tex> G_2 </tex> такую, что вершина <tex> v </tex> будет представлена на плоскости в двух экземплярах. (рис. 2)
[[Файл:p-k.2.png|thumb|right|рис. 2]]
Соединим два экземпляра вершины <tex> v </tex> пучком жордановых линий, не допуская лишних пересечений с укладками графов <tex> G_1 </tex> и <tex> G_2 </tex>, состоящим из такого количества линий, какова степень вершины <tex> v </tex> в графе <tex> G_2 </tex>. Далее отбросим вхождение вершины <tex> v </tex> в граф <tex> G_2 </tex>, заменяя инцидентные её рёбра на жордановы линии, полученные из линий указанного пучка и рёбер (рис. 3)
[[Файл:p-k.3.png|thumb|right|рис. 3]]
Таким образом мы получили укладку графа <tex> G </tex> на плоскости, что невозможно.
 
Пусть <tex> e = ab </tex> — произвольное ребро графа <tex> G </tex>, <tex> G' = G - e </tex>.
# граф <tex> G' </tex> планарен в силу минимальности графа <tex> G </tex>.
# граф <tex> G' </tex> связен в силу отсутствия в графе <tex> G </tex> мостов.

==== В G' существует цикл, содержащий вершины a и b ====
Пусть <tex> a </tex> и <tex> b </tex> лежат в одном блоке <tex> B </tex> графа <tex> G' </tex>.
# Если <tex> |VB| >= 3 </tex>, то существует цикл графа G', содержащий вершины <tex> a </tex> и <tex> b </tex>.
# Если <tex> |VB| = 2 </tex>, то в <tex> B </tex> имеется ребро <tex> e' = ab </tex>, но тогда в <tex> G </tex> имеются кратные рёбра <tex> e </tex> и <tex> e' </tex>, что невозможно.
# Если вершины <tex> a </tex> и <tex> b </tex> лежат в разных блоках графа <tex> G' </tex>, что существует точка сочленения <tex> v </tex>, принадлежащая любой простой (a, b)-цепи графа <tex> G' </tex>. Через <tex> G'_1 </tex> обозначим подграф графа <tex> G' </tex>, порождённый вершиной <tex> v </tex> и вершинами компоненты связности графа <tex> G' - v </tex>, содержащей <tex> a </tex>, а через <tex> G'_2 </tex> - подграф графа <tex> G' </tex>, порождённый вершиной <tex> v </tex> и вершинами остальных компонент связности графа <tEx> G' - v </tex> (в этом множестве лежит вершина <tex> b </tex>). Пусть <tex> G''_1 = G'_1 + e_1 </tex>, где <tex> e_1 = vb </tex> — новое ребро (рис. 4)
[[Файл:p-k.4.png|thumb|right|рис. 4]]
Заметим, что в графе <tex> G''_1 </tex> рёбер меньше, чем в графе <tex> G </tex>. Действительно, вместо ребра <tex> e </tex> в <tex> G''_1 </tex> есть ребро <tex> e_1 </tex> и часть рёбер из графа <tex> G </tex> осталась в графе <tex> G''_2 </tex>. Аналогично, в графе <tex> G''_2 </tex> рёбер меньше, чем в графе <tex> G </tex>. 
Покажем, далее, что в графе <tex> G''_1 </tex> и, аналогично, в графе <tex> G''_2 </tex> нет подграфов, гомеоморфных <tex> K_5 </tex> или <tex> K_{3,3} </tex>. Действительно, если в <tex> G''_1 </tex> имеется такой подграф, то в этом подграфе присутствует вновь присоединенное ребро, но это ребро <tex> e_1 </tex> можно заменить на цепь 
a -> b -> ... -> v, взяв некоторую простую (b, v)-цепь <tex> P_2 </tex> в графе <tex> G'_2 </tex>. Следовательно, мы получили подграф в <tex> G </tex>, гомеоморфный <tex> K_5 </tex> или <tex> K_{3,3} </tex>, что невозможно. 
Теперь в силу минимальности графа <tex> G </tex> графы <tex> G''_1 </tex> и <tex> G''_2 </tex> планарны. Возьмем укладку графа <tex> G''_1 </tex> на плоскости такую, что ребро <tex> e_1 = av </tex> лежит на границе внешней грани. Во внешней грани графа <tex> G''_1 </tex> возьмем укладку графа <tex> G''_2 </tex> такую, что ребро <tex> e_2 = vb </tex> лежит па границе внешпей грани (рис. 5).
[[Файл:p-k.5.png|thumb|right|рис. 5]]
Отметим, что опять вершина <tex> v </tex> представлена на плоскости в двух экземплярах. Очевидно, добавление ребра <tex> e = ab </tex> не меняет планарности графа <tex> G''_1 U G''_2</tex>. Склеим оба вхождения вершины <tex> v </tex> точно так же, как это мы сделали в предыдущем пункте доказательства (рис. 6).
[[Файл:p-k.6.png|thumb|right|рис. 6]]
Сотрем затем ранее добавленные ребра <tex> e_1 </tex> и <tex> e_2 </tex>. В результате мы получим укладку графа <tex> G </tex> на плоскости, что невозможно. Утверждение доказано.

====Вспомогательные определения и утверждение об одновременно разделяющейся внутренней части====
Среди всех укладок графа <tex>G'</tex> на плоскости и среди всех циклов <tex>C</tex>, содержащих <tex>a</tex> и <tex>b</tex>, зафиксируем такую укладку и такой цикл, что внутри области, ограниченной циклом <tex>C</tex>, лежит максимальное возможное число граней графа <tex>G'</tex>. Зафиксируем один из обходов по циклу <tex>C</tex> (на рисунках будем рассматривать обход по часовой стрелке по циклу <tex>C</tex>). Для вершин <tex>u</tex> и <tex>v</tex> цикла <tex>C</tex> через <tex>C[u,v]</tex> будем обозначать простую <tex>(u,v)</tex>-цепь, идущую по циклу <tex>C</tex> от <tex>u</tex> до <tex>v</tex> в направлении обхода цикла. Конечно, <tex>C[u,v] \ne C[v,u]</tex>. Положим <tex>C(u,v) = C[u,v] \setminus</tex> {<tex>u,v</tex>}, т.е. <tex>C(u,v)</tex> получено из <tex>C[u,v]</tex> отбрасыванием вершин <tex>u</tex> и <tex>v</tex>.
{{Определение
|definition =
Внешним графом (относительно цикла <tex>C</tex>) будем называть подграф графа <tex>G'</tex>, порождённый всеми вершинами графа <tex>G'</tex>, лежащими снаружи от цикла <tex>C</tex>.
}}
{{Определение
|definition =
Внешними компонентами будем называть компоненты связности внешнего графа.
}}
В силу связности графа <tex>G'</tex> для любой внешней компоненты должны существовать рёбра в <tex>G'</tex>, соединяющие её с вершинами цикла <tex>C</tex>.
{{Определение
|definition =
Внешними частями будем называть внешние компоненты вместе со всеми рёбрами, соединяющими компоненту с вершинами цикла <tex>C</tex>, и инцидентными им вершинами (см. рис. 7), либо рёбра графа <tex>G'</tex>, лежащие снаружи от цикла <tex>C</tex> и соединяющие две вершины из <tex>C</tex>, вместе с инцидентными такому ребру вершинами (см. рис. 8).
}}
[[Файл:pict-1.jpg|center|200px|рис. 7]][[Файл:pict-2.jpg|center|125px|рис. 8]]
{{Определение
|definition =
Внутренним графом (относительно цикла <tex>C</tex>) будем называть подграф графа <tex>G'</tex>, порождённый всеми вершинами графа <tex>G'</tex>, лежащими внутри цикла <tex>C</tex>.
}}
{{Определение
|definition =
Внутренними компонентами будем называть компоненты связности внутреннего графа.
}}
В силу связности графа <tex>G'</tex> для любой внутренней компоненты должны существовать рёбра в <tex>G'</tex>, соединяющие её с вершинами цикла <tex>C</tex>.
{{Определение
|definition =
Внутренними частями будем называть внутренние компоненты вместе со всеми рёбрами, соединяющими компоненту с вершинами цикла <tex>C</tex>, и инцидентными им вершинами, либо рёбра графа <tex>G'</tex>, лежащие внутри цикла <tex>C</tex> и соединяющие две вершины из <tex>C</tex>, вместе с инцидентными такому ребру вершинами
}}
Будем говорить, что внешняя (внутренняя) часть ''встречает цикл'' <tex>C</tex> в своих точках прикрепления к циклу <tex>C</tex>.
{{Лемма
|statement =
1) Любая внешняя часть встречает цикл <tex>C</tex> точно в двух точках, одна из которых лежит в <tex>C(a,b)</tex>, а другая — в <tex>C(b,a)</tex>.
|proof =
Если внешняя часть встречает цикл <tex>C</tex> точно в одной точке <tex>v</tex>, то <tex>v</tex> является точкой сочленения графа <tex>G</tex>, что невозможно (см. рис. 9).
[[Файл:pict-3.jpg|center|рис. 9]]
Таким образом, внешняя часть встречает цикл <tex>C</tex> не менее чем в двух точках. Если внешняя часть встречает цикл <tex>C</tex> в двух точках из <tex>C[a,b]</tex> (случай <tex>C[b,a]</tex> рассматривается аналогично), то в <tex>G'</tex> имеется цикл, содержащий внутри себя больше граней, чем цикл <tex>C</tex>, и проходящий через <tex>a</tex> и <tex>b</tex>, что невозможно (см. рис. 10).
[[Файл:pict-4.jpg|center|рис. 10]]
Итого, внешняя часть встречает цикл <tex>C</tex> хотя бы в двух точках, никакие две из которых не лежат в <tex>C[a,b]</tex> и <tex>C[b,a]</tex>. То есть ровно одна лежит в <tex>C[a,b]</tex> и ровно одна - в <tex>C[b,a]</tex>.
}}
{{Определение
|definition =
Ввиду леммы 1 будем говорить, что любая внешняя часть является <tex>(a,b)</tex>-разделяющей частью, поскольку она встречает и <tex>C(a,b)</tex>, и <tex>C(b,a)</tex>.
}}
Аналогично можно ввести понятие <tex>(a,b)</tex>-разделяющей внутренней части. Заметим, что внутрення часть может встречать цикл <tex>C</tex>, вообще говоря, более чем в двух точках, но не менее чем в двух точках.
{{Лемма
|statement =
2) Существует хотя бы одна <tex>(a,b)</tex>-разделяющая внутренняя часть.
|proof =
Пусть, от противного, таких частей нет. Тогда, выходя из <tex>a</tex> внутри области, ограниченной <tex>C</tex>, и двигаясь вблизи от <tex>C</tex> по направлению обхода <tex>C</tex> и вблизи от встречающихся внутренних частей, можно уложить ребро <tex>e = ab</tex> внутри цикла <tex>C</tex> (см. рис. 11), т.е. <tex>G</tex> - планарный граф, что невозможно.[[Файл:pict-5.jpg|center|130px|рис. 11]]
}}
{{Лемма
|statement =
3) Существует внешняя часть, встречающая <tex>C(a,b)</tex> в точке <tex>c</tex> и <tex>C(b,a)</tex> — в точке <tex>d</tex>, для которой найдётся внутренняя часть, являющаяся одновременно <tex>(a,b)</tex>-разделяющей и <tex>(c,d)</tex>-разделяющей (см. рис. 12).
[[Файл:pict-6.jpg|center|120px|рис. 12]]
|proof =
Пусть, от противного, лемма 3 неверна. Упорядочим <tex>(a,b)</tex>-разделяющие внутренние части в порядке их прикрепления к циклу <tex>C</tex> при движении по циклу от <tex>a</tex> до <tex>b</tex> и обозначим их соответственно через <tex>In_{1},In_{2},...</tex>. Пусть <tex>u_{1}</tex> и <tex>u_{2}</tex> — первая и последняя вершины из <tex>C(a,b)</tex>, в которых <tex>In_{1}</tex> встречает цикл <tex>C</tex>, а <tex>v_{1}</tex> и <tex>v_{2}</tex> — первая и последняя вершины из <tex>C(b,a)</tex>, в которых <tex>In_{1}</tex> встречает цикл <tex>C</tex> (возможно, вообще говоря, <tex>u_{1} = u_{2}</tex> или <tex>v_{1} = v_{2}</tex>). Поскольку лемма 3 неверна, для любой внешней части обе её вершины, в которых она встречает <tex>C</tex>, лежат либо на <tex>C[v_{2},u_{1}]</tex>, либо на <tex>C[u_{2},v_{1}]</tex>. Тогда снаружи цикла <tex>C</tex> можно провести жорданову кривую <tex>P</tex>, не пересекая рёбер графа <tex>G'</tex>, соединяющую <tex>v_{2}</tex> с <tex>u_{1}</tex> (см. рис. 13).
[[Файл:pict-7.jpg|center|160px|рис. 13]]
Поскольку на участках <tex>C(u_{1},u_{2})</tex> и <tex>C(v_{1},v_{2})</tex> нет точек прикрепления внешних частей, используя жорданову кривую <tex>P</tex>, внутреннюю часть <tex>In_{1}</tex> можно перебросить ("вывернуть" наружу от цикла <tex>C</tex>) во внешнюю область цикла <tex>C</tex>, т.е. уложить её снаружи от цикла <tex>C</tex> и сделать её внешней частью.
Аналогично все остальные <tex>(a,b)</tex>-разделяющие внутренние части можно перебросить во внешнюю область от цикла <tex>C</tex>. После этого точно так же, как в доказательстве леммы 2, ребро <tex>e = ab</tex> можно уложить внутри цикла <tex>C</tex>, так как не останется <tex>(a,b)</tex>-разделяющих внутренних частей. Следовательно, мы получим укладку графа <tex>G</tex>, что невозможно.
}}

== Разбор случаев взаимного положения ''a, b, c, d, u1, u2, v1, v2'' ==
Рассмотрим 2 случая.
[[Файл:Case_1.png|thumb|right|рис. 1]]

1. Пусть пара вершин <tex>\ v_1 </tex> и <tex>\ v_2 </tex> является <tex>(a, b)</tex>-разделяющей. 
Тогда, в частности, <tex>v_2 \ne a</tex> и <tex> v_1 \ne b</tex>. В этом случае граф <tex>G</tex> содержит подграф, гомеоморфный <tex>\ K_{3,3} </tex> (отметим, что в <tex> In </tex> существует простая <tex>(v_1, v_2)</tex>-цепь)(рис. 1).

2. Пусть пара вершин <tex>v_1</tex> и <tex>v_2</tex> не является <tex>(a, b)</tex>-разделяющей. 
Тогда <tex>v_1, v_2</tex> лежат на <tex>C[a, b]</tex> или на <tex>C[b, a]</tex>. Без ограничения общности будет считать, что <tex>v_1</tex> и <tex>v_2</tex> лежат на <tex>C[a, b]</tex>. 

2.1. Пусть <tex>v_1</tex> и <tex>v_2</tex> лежат на <tex>C(a, b)</tex>, т.е. <tex>v_1 \ne b</tex> и <tex>v_2 \ne a</tex>(рис. 2). 

2.1.1 Пусть <tex>u_2</tex> лежит на <tex>C(d, a)</tex>. 
Тогда в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 3). 

2.1.2. Пусть <tex>u_2 = d</tex>. 
Тогда во внешней части <tex>In</tex> имеется вершина <tex>w</tex> и три простые цепи от <tex>w</tex> соответственно до <tex>d, v_1, v_2</tex>, которые в качестве общей точки имеют только точку <tex>w</tex>. В этом случае в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 4). 

2.1.3. Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>. 
Тогда в графе <tex>G</tex> есть подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 5). 


[[Файл:Сase_2.1.png|150px|рис. 2]]
[[Файл:Сase_2.1.1.png|150px|рис. 3]]
[[Файл:Сase_2.1.2.png|150px|рис. 4]]
[[Файл:Сase_2.1.3.png|150px|рис. 5]]


Теперь рассмотрим случаи, когда хотя бы одна из вершин <tex>v_1</tex> и <tex>v_2</tex> не лежит на <tex>С(a, b)</tex>. Без ограничения общности будем считать, что это вершина <tex>v_1</tex>, т.е <tex>v_1 = b</tex>(поскольку <tex>v_1</tex> лежит на <tex>C[a, b]</tex>). 

2.2. Пусть <tex>v_2 \ne a</tex>. 

2.2.1. Пусть <tex>u_2</tex> лежит на <tex>C(d, a)</tex>. 
Тогда в графе <tex>G</tex> есть пограф, гомеоморфный <tex>K_{3,3}</tex>(рис. 6). 

2.2.2. Пусть <tex>u_2 = d</tex>. 
Тогда в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 7). 

2.2.3. Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>. 
Тогда в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 8). 

[[Файл:Сase_2.2.1.png|150px|рис. 6]]
[[Файл:Сase_2.2.2.png|150px|рис. 7]]
[[Файл:Сase_2.2.3.png|150px|рис. 8]]


2.3. Пусть <tex>v_2 = a</tex>(рис. 9). 
Рассмотрим теперь пару вершин <tex>u_1</tex> и <tex>u_2</tex>. Будем считать, что <tex>u_1 = c</tex> и <tex>u_2 = d</tex>, поскольку все другие случаи расположения вершин <tex>u_1</tex> и <tex>u_2</tex> так же, как были рассмотрены все случаи расположения <tex>v_1</tex> и <tex>v_2</tex>. Пусть <tex>P_1</tex> и <tex>P_2</tex> — соответственно кратчайшие простые <tex>(a, b)</tex>-цепь и <tex>(c, d)</tex>-цепь по внутренней части <tex>In</tex>(рис. 10).
Заметим, что <tex>P_1</tex> и <tex>P_2</tex> имеют общую точку. 

2.3.1. Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют более одной общей точки. 
Тогда в графе <tex>G</tex> есть подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 11). 

2.3.2. Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют точно одну общую точку <tex>w</tex>. 
Тогда в графе <tex>G</tex> есть подграф, гомеоморфный <tex>K_5</tex>(рис. 12). 


[[Файл:Сase_2.3(a).png|150px|рис. 9]]
[[Файл:Сase_2.3(b).png|150px|рис. 10]]
[[Файл:Сase_2.3.1.png|150px|рис. 11]]
[[Файл:Сase_2.3.2.png|150px|рис. 12]]


Таким образом, доказано, что в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex> или <tex>K_5</tex>, что противоречит нашему первому предположению. 
}}

==Литература==
* Асанов М., Баранский В., Расин В. — Дискретная математика — Графы, матроиды, алгоритмы

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов ]]

Укладка графа на плоскости

2010-10-21T06:28:54Z

Vladimir.nesmelov: Добавлены категории

{{Определение
|definition=
Граф '''обладает укладкой''' в пространстве <tex>L</tex>, если он изоморфен графу, вершинами которого являются некоторые точки пространства, а ребрами {{---}} жордановы кривые, соединяющие соответствующие вершины, причем
 1) кривая, являющаяся ребром не проходит через другие вершины графа, кроме вершин, которые она соединяет;
 2) две кривые, являющиеся ребрами, пересекаются лишь в вершинах, инцидентных одновременно обоим этим ребрам.
 Соответствующий граф, составленный из точек пространства и жордановых кривых из <tex>L</tex>, называют '''укладкой''' исходного графа.
}}
{{Определение
|definition=
Граф называется '''планарным''', если он обладает укладкой на плоскости. Всевозможные укладки планарных графов на плоскости будем называются '''плоскими''' графами.
}}
{{Определение
|definition=
Плоский граф разбивает плоскость на несколько областей, называемых '''гранями'''. Одна из граней не ограничена, ее называют '''внешней''' гранью, а остальные {{---}} '''внутренними''' гранями.
}}

==Литература==
* Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов ]]

Формула Эйлера

2010-10-19T12:18:59Z

Vladimir.nesmelov: Добавлены категории

{{Теорема
|about=
Формула Эйлера
|statement=
Для произвольного плоского связного графа <tex>G</tex> с <tex>V</tex> вершинами, <tex>E</tex> ребрами и <tex>F</tex> гранями справедливо следующее соотношение:
 <tex>V - E + F = 2</tex>
|proof=
}}
{{Теорема
|about=
Следствие из формулы Эйлера
|statement=
Пусть <tex>G</tex> произвольный граф с <tex>V</tex> вершинами (<tex>V \ge 3</tex>), <tex>E</tex> ребрами и <tex>F</tex> гранями. Тогда <tex>E \le 3V - 6</tex>
|proof=
Поскольку <tex>G</tex> не содержит петель и кратных ребер, то каждая грань граничит хотя бы с тремя ребрами. Пусть, двигаясь вдоль <tex>i</tex>-й грани мы пройдем <tex>l_i</tex> ребер. Очевидно, что <tex>\sum_{i=1}^{F}l_i = 2E</tex>. Поскольку <tex>l_i \ge 3 (i = 1..F)</tex>, получаем <tex>3F \le 2E</tex>. Из формулы Эйлера <tex>3E - 3V + 6 = 3F \le 2E</tex>, то есть <tex>E \le 3V - 6</tex>.
}}

==Литература==
* Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов ]]

Непланарность K5 и K3,3

2010-10-19T12:18:38Z

Vladimir.nesmelov: Добавлены категории

{{Теорема
|about=
Непланарность <tex>K_5</tex>
|statement=
Граф <tex>K_5</tex> непланарен.
|proof=
Граф <tex>K_5</tex> имеет 5 вершин и 10 ребер. Если он планарен, то по [[Формула Эйлера|следствию из формулы Эйлера]] получаем <tex>10 \le 3 \cdot 5 - 6 = 9</tex>. Что невозможно.
}}
{{Теорема
|about=
Непланарность <tex>K_{3,3}</tex>
|statement=
Граф <tex>K_{3,3}</tex> непланарен.
|proof=
Граф <tex>K_{3,3}</tex> содержит <tex>V = 6</tex>, <tex>E = 9</tex> и <tex>F</tex> граней. 
Пусть граф <tex>K_{3,3}</tex> планарен. Тогда по [[Формула Эйлера|формуле Эйлера]] <tex>F = E - V + 2 = 9 - 6 + 2 = 5</tex>. Пусть, двигаясь вдоль <tex>i</tex>-й грани мы пройдем <tex>l_i</tex> ребер. Очевидно, что <tex>\sum_{i=1}^{F}l_i = 2E</tex>. Поскольку граф двудольный, все его циклы имеют четную длину. Значит <tex>l_i \ge 4</tex>. Получаем <tex>4F \le 2E</tex>, то есть <tex>2F \le E</tex>. То есть <tex>2\cdot5 = 10 \le 9</tex>, что невозможно.
}}

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов ]]

Теорема Понтрягина-Куратовского

2010-10-19T12:18:11Z

Vladimir.nesmelov: Добавлены категории

==== Разбор случаев взаимного положения ''a, b, c, d, u1, u2, v1, v2'' ====
Рассмотрим 2 случая.
[[Файл:Case_1.png|thumb|right|рис. 1]]
----

1. Пусть пара вершин <tex>\ v_1 </tex> и <tex>\ v_2 </tex> является <tex>(a, b)</tex>-разделяющей. 
Тогда, в частности, <tex>v_2 \ne a</tex> и <tex> v_1 \ne b</tex>. В этом случае граф G содержит подграф, гомеоморфный <tex>\ K_{3,3} </tex> (отметим, что в <tex> In </tex> существует простая <tex>(v_1, v_2)</tex>-цепь)(рис. 1).

----
2. Пусть пара вершин <tex>v_1</tex> и <tex>v_2</tex> не является <tex>(a, b)</tex>-разделяющей. 
Тогда <tex>v_1, v_2</tex> лежат на <tex>C[a, b]</tex> или на <tex>C[b, a]</tex>. Без ограничения общности будет считать, что <tex>v_1</tex> и <tex>v_2</tex> лежат на <tex>C[a, b]</tex>. 

2.1. Пусть <tex>v_1</tex> и <tex>v_2</tex> лежат на <tex>C(a, b)</tex>, т.е. <tex>v_1 \ne b</tex> и <tex>v_2 \ne a</tex>(рис. 2). 

2.1.1 Пусть <tex>u_2</tex> лежит на <tex>C(d, a)</tex>. 
Тогда в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 3). 

2.1.2. Пусть <tex>u_2 = d</tex>. 
Тогда во внешней части <tex>In</tex> имеется вершина <tex>w</tex> и три простые цепи от <tex>w</tex> соответственно до <tex>d, v_1, v_2</tex>, которые в качестве общей точки имеют только точку <tex>w</tex>. В этом случае в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 4). 

2.1.3. Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>. 
Тогда в графе G есть подграф, гомеоморфный <tex>K{3,3}</tex>(рис. 5). 


[[Файл:Сase_2.1.png|150px|рис. 2]]
[[Файл:Сase_2.1.1.png|150px|рис. 3]]
[[Файл:Сase_2.1.2.png|150px|рис. 4]]
[[Файл:Сase_2.1.3.png|150px|рис. 5]]


----

Теперь рассмотрим случаи, когда хотя бы одна из вершин <tex>v_1</tex> и <tex>v_2</tex> не лежит на <tex>С(a, b)</tex>. Без ограничения общности будем считать, что это вершина <tex>v_1</tex>, т.е <tex>v_1 = b</tex>(поскольку <tex>v_1</tex> лежит на <tex>C[a, b]</tex>). 

2.2. Пусть <tex>v_2 \ne a</tex>. 

2.2.1. Пусть <tex>u_2</tex> лежит на <tex>C(d, a)</tex>. 
Тогда в графе G есть пограф, гомеоморфный <tex>K_{3,3}</tex>(рис. 6). 

2.2.2. Пусть <tex>u_2 = d</tex>. 
Тогда в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 7). 

2.2.3. Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>. 
Тогда в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 8). 

[[Файл:Сase_2.2.1.png|150px|рис. 6]]
[[Файл:Сase_2.2.2.png|150px|рис. 7]]
[[Файл:Сase_2.2.3.png|150px|рис. 8]]


----

2.3. Пусть <tex>v_2 = a</tex>(рис. 9). 
Рассмотрим теперь пару вершин <tex>u_1</tex> и <tex>u_2</tex>. Будем считать, что <tex>u_1 = c</tex> и <tex>u_2 = d</tex>, поскольку все другие случаи расположения вершин <tex>u_1</tex> и <tex>u_2</tex> так же, как были рассмотрены все случаи расположения <tex>v_1</tex> и <tex>v_2</tex>. Пусть <tex>P_1</tex> и <tex>P_2</tex> -- соответственно кратчайшие простые <tex>(a, b)</tex>-цепь и <tex>(c, d)</tex>-цепь по внутренней части <tex>In</tex>(рис. 10).
Заметим, что <tex>P_1</tex> и <tex>P_2</tex> имеют общую точку. 

2.3.1. Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют более одной общей точки. 
Тогда в графе G есть подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 11). 

2.3.2. Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют точно одну общую точку <tex>w</tex>. 
Тогда в графе G есть подграф, гомеоморфный <tex>K_5</tex>(рис. 12). 


[[Файл:Сase_2.3(a).png|150px|рис. 9]]
[[Файл:Сase_2.3(b).png|150px|рис. 10]]
[[Файл:Сase_2.3.1.png|150px|рис. 11]]
[[Файл:Сase_2.3.2.png|150px|рис. 12]]


Таким образом, доказано, что в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex> или <tex>K_5</tex>, что противоречит нашему первому предположению. 

==Литература==
* Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов ]]

Алгоритмы и структуры данных

2010-10-17T04:55:42Z

Vladimir.nesmelov: Обновление тем до актуального состояния на 17.10.10

Матрица смежности графа

2010-10-13T21:17:49Z

Vladimir.nesmelov: вставка шаблона

__NOTOC__
{{Определение
|definition ='''Матрицей смежности''' (англ. Adjacency matrix) <tex>A=||\alpha_{i,j}||</tex> ''помеченного графа'' <tex>G(V,E)</tex> называется матрица <tex>A_{[V\times{}V]}</tex>, в которой <tex>\alpha_{i,j}</tex> — количество рёбер, соединяющих вершины <tex>v_i</tex> и <tex>v_j</tex>, причём при <tex>i=j</tex> каждую петлю учитываем дважды, если граф не является ориентированным, и один раз, если граф ориентирован.
}}

== Пример ==
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center"
!style="background:#f2f2f2"|Граф
!style="background:#f2f2f2"|Матрица смежности
|-
|style="background:#f9f9f9"|[[Файл:Graph 5-7.png|175px]]
|style="background:#f9f9f9"|<tex>\begin{pmatrix}
0 & 1 & 0 & 0 & 1\\
1 & 0 & 1 & 1 & 1\\
0 & 1 & 0 & 1 & 0\\
0 & 1 & 1 & 0 & 1\\
1 & 1 & 0 & 1 & 0\\
\end{pmatrix}</tex>
|}

== Свойства ==
Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей.

=== Случай ориентированного графа ===
Сумма элементов <tex>i</tex>-й строки равна <tex>\deg^- v_i</tex>, то есть <tex>\sum\limits_{j=1}^{n}\alpha_{i,j} = \deg^- v_i</tex>.
Аналогично сумма элементов <tex>j</tex>-го стоблца равна <tex>\deg^+ v_j</tex>, то есть <tex>\sum\limits_{i=1}^{n}\alpha_{i,j} = \deg^+ v_j</tex>.

=== Случай неориентированного графа ===
Для неориентированных графов матрица смежности является симметричной.

Сумма элементов <tex>i</tex>-й строки равна <tex>\deg v_i</tex>, то есть <tex>\sum\limits_{j=1}^{n}\alpha_{i,j} = \deg v_i</tex>. В следствии симметричности суммы элементов <tex>i</tex>-й строки и <tex>i</tex>-го столбца равны.

== См. также ==
* [[Связь степени матрицы смежности и количества путей]]
* [[Матрица инцидентности графа]]
== Литература ==
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]

Теорема о существовании простого цикла в случае существования цикла

2010-10-11T04:45:30Z

Vladimir.nesmelov: корректировка ссылок, выставление категорий

{{Определение
|definition=
'''Простой (рёберно-простой) цикл''' в графе – [[Основные_определения_теории_графов#Цикл|цикл]], в котором каждое из рёбер графа встречается не более одного раза.
}}
Для удобства будем считать, что цикл задаётся <math>n</math> вершинами и <math>n</math> рёбрами:
<math>V_0E_1V_1E_2 ... V_{n-1}E_n</math>, – причём ребро <math>E_i</math> соединяет вершины <math>V_{i-1}</math> и <math>V_{i % n}</math>.

{{Определение
|definition=
'''Длина цикла''' – количество рёбер, входящих в последовательность, задающую этот цикл.
}}

{{Теорема
|statement=
Если две вершины графа лежат на цикле, то они лежат на простом цикле.
|proof=
}}

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]

Двойственный граф планарного графа

2010-10-08T01:51:06Z

Vladimir.nesmelov: Добавлены категории

{{В разработке}}

Двойственный граф — это здорово!

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Укладки графов]]

Алгоритмы и структуры данных

2010-10-08T00:26:14Z

Vladimir.nesmelov: Обновление тем до состояния на 07.10.2010

Категория:Укладки графов

2010-10-08T00:09:15Z

Vladimir.nesmelov: Новая страница: «Категория: Алгоритмы и структуры данных»

[[Категория: Алгоритмы и структуры данных]]

Категория:Обходы графов

2010-10-08T00:08:36Z

Vladimir.nesmelov: Новая страница: «Категория: Алгоритмы и структуры данных»

[[Категория: Алгоритмы и структуры данных]]

Категория:Остовные деревья

2010-10-08T00:07:50Z

Vladimir.nesmelov: Новая страница: «Категория: Алгоритмы и структуры данных»

[[Категория: Алгоритмы и структуры данных]]

Категория:Связность в графах

2010-10-08T00:07:14Z

Vladimir.nesmelov: Новая страница: «Категория: Алгоритмы и структуры данных»

[[Категория: Алгоритмы и структуры данных]]

Категория:Основные определения теории графов

2010-10-08T00:04:20Z

Vladimir.nesmelov: Новая страница: «Категория: Алгоритмы и структуры данных»

[[Категория: Алгоритмы и структуры данных]]

Матрица смежности графа

2010-10-08T00:03:26Z

Vladimir.nesmelov: Добавлены категории

== Определение ==
'''Матрицей смежности''' (англ. Adjacency matrix) <tex>A=||\alpha_{i,j}||</tex> ''помеченного графа'' <tex>G(V,E)</tex> называется матрица <tex>A_{[V\times{}V]}</tex>, в которой <tex>\alpha_{i,j}</tex> — количество рёбер, соединяющих вершины <tex>v_i</tex> и <tex>v_j</tex>, причём при <tex>i=j</tex> каждую петлю учитываем дважды, если граф не является ориентированным, и один раз, если граф ориентирован.

=== Пример ===
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center"
!style="background:#f2f2f2"|Граф
!style="background:#f2f2f2"|Матрица смежности
|-
|style="background:#f9f9f9"|[[Файл:Graph 5-7.png|175px]]
|style="background:#f9f9f9"|<tex>\begin{pmatrix}
0 & 1 & 0 & 0 & 1\\
1 & 0 & 1 & 1 & 1\\
0 & 1 & 0 & 1 & 0\\
0 & 1 & 1 & 0 & 1\\
1 & 1 & 0 & 1 & 0\\
\end{pmatrix}</tex>
|}

== Свойства ==
Для графов без петель и кратных рёбер матрица смежности бинарна (состоит из нулей и единиц), причём её главная диагональ целиком состоит из нулей.

=== Ориентированный граф ===
Сумма элементов <tex>i</tex>-й строки равна <tex>\deg^- v_i</tex>, то есть <math>\sum_{j=1}^{n}\alpha_{i,j} = \deg^- v_i</math>.
Аналогично сумма элементов <tex>j</tex>-го стоблца равна <tex>\deg^+ v_j</tex>, то есть <math>\sum_{i=1}^{n}\alpha_{i,j} = \deg^+ v_j</math>.

=== Неориентированный граф ===
Для неориентированных графов матрица смежности является симметричной.

Сумма элементов <tex>i</tex>-й строки равна <tex>\deg v_i</tex>, то есть <math>\sum_{j=1}^{n}\alpha_{i,j} = \deg v_i</math>. В следствии симметричности суммы элементов <tex>i</tex>-й строки и <tex>i</tex>-го столбца равны.

== См. также ==
* [[Связь степени матрицы смежности и количества путей]]
* [[Матрица инцидентности графа]]
== Литература ==
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* Асанов М. О., Баранский В. А., Расин В. В. '''Дискретная математика: графы, матроиды, алгоритмы''' — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]

Матрица смежности графа

2010-10-08T00:00:59Z

Vladimir.nesmelov: Новая страница: «== Определение == '''Матрицей смежности''' (англ. Adjacency matrix) <tex>A=||\alpha_{i,j}||</tex> ''помеченного графа…»