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