4920
правок
Полностью динамическая проверка на планарность: различия между версиями
Материал из WEGA
Полностью динамическая проверка на планарность (посмотреть исходный код)
Версия от 04:31, 19 июня 2018
, 19 июня 2018→См. также
Irina (обсуждение | вклад) (Новая страница: «== Постановка задачи == Здесь будет рассмотрена задача поддержки динамического планарног…») |
Irina (обсуждение | вклад) м (→См. также) |
||
| (не показано 5 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
Здесь будет рассмотрена задача поддержки динамического планарного графа, в котором выполняются операции вставки и удаления ребер, сохраняющие планарность, но способные изменить укладку. Предварительные определения перед формальной формулировкой задачи. | Здесь будет рассмотрена задача поддержки динамического планарного графа, в котором выполняются операции вставки и удаления ребер, сохраняющие планарность, но способные изменить укладку. Предварительные определения перед формальной формулировкой задачи. | ||
Граф является планарным, если он может быть уложен на плоскости без пересечения дуг. В динамической структуре планарный граф, связанный с конкретной укладкой, называется плоским; общий термин «планарный граф» используется только в случае, если разрешено изменение укладки. Вставка ребер, сохраняющая укладку, называется вставкой с сохранением укладки; если она сохраняет планарность графа, она называется сохраняющей планарность – укладка при этом, возможно, меняется; если же неизвестно, сохраняется ли при вставке ребра планарность, такая вставка называется произвольной. Обширные исследования динамических графовых алгоритмов применяли специализированные техники для решения множества задач – таких как нахождение минимальных остовных лесов, 2-реберная связность и проверка на планарность для плоских графов (с операциями вставки, сохраняющими укладку) [5, 6, 7, 9, 10, 11, 12]. В данном случае будут рассматриваться обновления более общего вида с сохранением планарности. | |||
Галил и коллеги [], а также Эппстайн и коллеги [3] предложили общий метод решения динамических задач на планарных графах, включая вышеприведенные: во всех этих задачах могут иметь место как произвольные вставки, так и вставки с сохранением планарности, что означает допустимость изменений укладки. | Граф является [[планарный граф|планарным]], если он может быть уложен на плоскости без пересечения дуг. В динамической структуре планарный граф, связанный с конкретной укладкой, называется [[плоский граф|плоским]]; общий термин «планарный граф» используется только в случае, если разрешено изменение укладки. Вставка ребер, сохраняющая укладку, называется вставкой с сохранением укладки; если она сохраняет планарность графа, она называется сохраняющей планарность – укладка при этом, возможно, меняется; если же неизвестно, сохраняется ли при вставке ребра планарность, такая вставка называется произвольной. Обширные исследования динамических графовых алгоритмов применяли специализированные техники для решения множества задач – таких как нахождение минимальных остовных лесов, 2-реберная связность и проверка на планарность для плоских графов (с операциями вставки, сохраняющими укладку) [5, 6, 7, 9, 10, 11, 12]. В данном случае будут рассматриваться обновления более общего вида с сохранением планарности. | ||
Галил и коллеги [8], а также Эппстайн и коллеги [3] предложили общий метод решения динамических задач на планарных графах, включая вышеприведенные: во всех этих задачах могут иметь место как произвольные вставки, так и вставки с сохранением планарности, что означает допустимость изменений укладки. | |||
Полностью динамическую задачу проверки на планарность можно определить следующим образом. Необходимо поддерживать (не обязательно планарный) граф, в котором выполняются произвольные операции вставки и удаления ребер, и выполнять запросы, проверяющие, является ли граф в текущее время планарным, а также не будет ли потенциальное новое ребро нарушать его планарность. | Полностью динамическую задачу проверки на планарность можно определить следующим образом. Необходимо поддерживать (не обязательно планарный) граф, в котором выполняются произвольные операции вставки и удаления ребер, и выполнять запросы, проверяющие, является ли граф в текущее время планарным, а также не будет ли потенциальное новое ребро нарушать его планарность. | ||
== Основные результаты == | == Основные результаты == | ||
Эппстайн и коллеги [3] предложили способ применения техники разрежения [ ] к семействам графов, уже являющихся разреженными – таким, как планарные графы. | Эппстайн и коллеги [3] предложили способ применения техники разрежения [2] к семействам графов, уже являющихся разреженными – таким, как планарные графы. | ||
Новые идеи, примененные в данном случае, заключаются в следующем. Понятие сертификата может быть расширено на определение графов, в которых подмножество вершин помечено как интересные; подобные сжатые сертификаты могут уменьшить размер графа за счет удаления неинтересных вершин. Используя это понятие, можно определить тип разрежения на основе разделителей – небольших множеств вершин, удаление которых разбивает граф на компоненты примерно равного размера. Рекурсивный поиск разделителей в этих компонентах дает в итоге дерево разделителей, которое может также использоваться как дерево разреженности; интересными вершинами для каждого сертификата будут вершины, использованные в разделителях на более высоких уровнях дерева. Вводится понятие сбалансированного дерева разделителей, которое также равномерно распределяет интересные вершины по дереву: такое дерево можно вычислить за линейное время и динамически поддерживать его. Используя эту технику, можно получить следующие результаты. | Новые идеи, примененные в данном случае, заключаются в следующем. Понятие сертификата может быть расширено на определение графов, в которых подмножество вершин помечено как интересные; подобные сжатые сертификаты могут уменьшить размер графа за счет удаления неинтересных вершин. Используя это понятие, можно определить тип разрежения на основе разделителей – небольших множеств вершин, удаление которых разбивает граф на компоненты примерно равного размера. Рекурсивный поиск разделителей в этих компонентах дает в итоге дерево разделителей, которое может также использоваться как дерево разреженности; интересными вершинами для каждого сертификата будут вершины, использованные в разделителях на более высоких уровнях дерева. Вводится понятие сбалансированного дерева разделителей, которое также равномерно распределяет интересные вершины по дереву: такое дерево можно вычислить за линейное время и динамически поддерживать его. Используя эту технику, можно получить следующие результаты. | ||
Теорема 1. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнением запросов на проверку, не нарушает ли новое ребро планарность графа, возможно выполнить за амортизированное время O( | '''Теорема 1. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнением запросов на проверку, не нарушает ли новое ребро планарность графа, возможно выполнить за амортизированное время <math>O(n^{1/2}) \;</math> на один запрос или обновление.''' | ||
| Строка 17: | Строка 19: | ||
Теорема 2. Поддержку графа с произвольными вставками и удалениями ребер и выполнением запросов на проверку, является ли граф в текущий момент планарным и не нарушит ли новое ребро планарность, возможно выполнить за амортизированное время O( | '''Теорема 2. Поддержку графа с произвольными вставками и удалениями ребер и выполнением запросов на проверку, является ли граф в текущий момент планарным и не нарушит ли новое ребро планарность, возможно выполнить за амортизированное время <math>O(n^{1/2}) \;</math> на один запрос или обновление.''' | ||
== Применение == | == Применение == | ||
| Строка 25: | Строка 26: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Граница O( | Граница <math>O(n^{1/2}) \;</math> для проверки на планарность является амортизированной. Можно ли улучшить эту границу или сделать ее границей для наихудшего случая? | ||
Сложность представленных алгоритмов и большие константные сомножители, входящие в некоторые асимптотические временные границы, делают некоторые результаты непригодными для практического применения. Можно ли упростить эти методы с сохранением сходных теоретических границ? | Сложность представленных алгоритмов и большие константные сомножители, входящие в некоторые асимптотические временные границы, делают некоторые результаты непригодными для практического применения. Можно ли упростить эти методы с сохранением сходных теоретических границ? | ||
== См. также == | == См. также == | ||
* ''[[Динамические деревья]] | |||
* ''[[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]] | |||
* ''[[Полностью динамическая связность]] | |||
* ''[[Полностью динамическая связность высоких степеней]] | |||
* ''[[Полностью динамическая связность высоких степеней в планарных графах]] | |||
* ''[[Полностью динамические минимальные остовные деревья]] | |||
* ''[[Полностью динамический алгоритм транзитивного замыкания]] | |||
== Литература == | == Литература == | ||
