Поиск кратчайших путей в планарных графах с отрицательными весами ребер: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Нотация) |
||
| Строка 28: | Строка 28: | ||
Алгоритм выполняет рекурсивную декомпозицию: на каждом уровне фрагмент с n вершинами и r граничными вершинами разделяется на два подфрагмента, таких, что каждый подфрагмент содержит не более | Алгоритм выполняет рекурсивную декомпозицию: на каждом уровне фрагмент с n вершинами и r граничными вершинами разделяется на два подфрагмента, таких, что каждый подфрагмент содержит не более <math>2n/3 \;</math> вершин и не более <math>2r/3 + c \sqrt{n} \;</math> граничных вершин при некотором константном значении c. В данном рекурсивном контексте граничной вершиной подфрагмента считается любая граничная вершина исходного фрагмента и любая новая граничная вершина, порожденная декомпозицией фрагмента. | ||
| Строка 38: | Строка 38: | ||
Задача 2 (Структура данных для поиска кратчайших путей) | '''Задача 2 (Структура данных для поиска кратчайших путей)''' | ||
Дано: ориентированный граф G = (V, E), весовая функция w: E | Дано: ориентированный граф G = (V, E), весовая функция <math>w: E \to \mathbb{R} \;</math>, вершина-источник <math>s \in V \;</math>. | ||
Требуется: если граф G не содержит циклов отрицательной длины, вывести структуру данных, поддерживающую запросы о расстоянии между парами вершин. В противном случае выдать сообщение, что в графе имеется цикл отрицательной длины. | Требуется: если граф G не содержит циклов отрицательной длины, вывести структуру данных, поддерживающую запросы о расстоянии между парами вершин. В противном случае выдать сообщение, что в графе имеется цикл отрицательной длины. | ||
Алгоритм Факчаренфола и Рао в значительной мере опирается на планарность графа; он использует свойства, относящиеся к тому, как пересекаются кратчайшие пути в каждом фрагменте. Таким образом, в отличие от предыдущих алгоритмов, которым требовалась только возможность рекурсивной декомпозиции графа с малым количеством граничных вершин [10], этот алгоритм также требует для каждого фрагмента наличия правильного вложения. | Алгоритм Факчаренфола и Рао в значительной мере опирается на [[планарный граф|планарность]] графа; он использует свойства, относящиеся к тому, как пересекаются кратчайшие пути в каждом фрагменте. Таким образом, в отличие от предыдущих алгоритмов, которым требовалась только возможность рекурсивной декомпозиции графа с малым количеством граничных вершин [10], этот алгоритм также требует для каждого фрагмента наличия правильного вложения. | ||
Пусть дано вложение фрагмента. Дыра представляет собой ограниченную грань, в которой все смежные вершины являются граничными вершинами. В идеале можно надеяться на то, что существует планарное вложение любого фрагмента рекурсивной декомпозиции, в котором все граничные вершины располагаются на одной грани и упорядочены по кругу, т.е. в каждом фрагменте не имеется дыр. Это не всегда оказывается верным, но алгоритм работает с любой декомпозицией с константным количеством дыр в каждом фрагменте. Эту декомпозицию можно найти за время O(n log n) при помощи алгоритма Миллера [12] для поиска простого циклического сепаратора. | Пусть дано вложение фрагмента. [[Дыра]] представляет собой ограниченную грань, в которой все смежные вершины являются граничными вершинами. В идеале можно надеяться на то, что существует планарное вложение любого фрагмента рекурсивной декомпозиции, в котором все граничные вершины располагаются на одной грани и упорядочены по кругу, т.е. в каждом фрагменте не имеется дыр. Это не всегда оказывается верным, но алгоритм работает с любой декомпозицией с константным количеством дыр в каждом фрагменте. Эту декомпозицию можно найти за время O(n log n) при помощи алгоритма Миллера [12] для поиска простого циклического сепаратора. | ||
== Основные результаты == | == Основные результаты == | ||