4446
правок
Полностью динамическая связность высоких степеней в планарных графах: различия между версиями
Перейти к навигации
Перейти к поиску
Полностью динамическая связность высоких степеней в планарных графах (посмотреть исходный код)
Версия от 17:19, 17 июля 2014
, 17 июля 2014→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Здесь будет рассмотрена задача поддержки динамического планарного графа, в котором выполняются операции вставки и удаления ребер, сохраняющие планарность, но способные изменить укладку. Более конкретно, задача заключается в эффективной поддержке информации о реберной и вершинной связности в подобном динамически меняющемся планарном графе. Алгоритмы, решающие эту задачу, должны поддерживать операции вставки, при которых граф сохраняет планарность, независимо от конкретной укладки графа. Подробнее об этом в статье | Здесь будет рассмотрена задача поддержки динамического планарного графа, в котором выполняются операции вставки и удаления ребер, сохраняющие планарность, но способные изменить укладку. Более конкретно, задача заключается в эффективной поддержке информации о реберной и вершинной связности в подобном динамически меняющемся планарном графе. Алгоритмы, решающие эту задачу, должны поддерживать операции вставки, при которых граф сохраняет планарность, независимо от конкретной укладки графа. Подробнее об этом в статье «[[Полностью динамическая проверка на планарность]]», в которой описываются эффективные процедуры проверки, выясняющие, остается ли граф планарным после вставки и удаления ребер (независимо от конкретной укладки). | ||
| Строка 20: | Строка 20: | ||
Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким как вставка ребра, удаление ребра и обновление веса ребра. Динамический алгоритм должен быстро обрабатывать запросы о свойстве P, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм является полностью динамическим, если он поддерживает как вставку ребер, так и удаление ребер. Частично динамический алгоритм поддерживает либо вставку, либо удаление ребер; инкрементный алгоритм поддерживает только вставку ребер, декрементный – только удаление. | Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким как вставка ребра, удаление ребра и обновление веса ребра. Динамический алгоритм должен быстро обрабатывать запросы о свойстве P, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм является полностью динамическим, если он поддерживает как вставку ребер, так и удаление ребер. Частично динамический алгоритм поддерживает либо вставку, либо удаление ребер; инкрементный алгоритм поддерживает только вставку ребер, декрементный – только удаление. | ||
В полностью динамической задаче k-реберной связности для планарного графа нам требуется поддержка неориентированного графа G = (V, E) и выполнение в различном порядке последовательности таких операций, как вставка ребер, удаление ребер и запросы о k-реберной связности для данного планарного графа. Аналогично, в полностью динамической задаче k-вершинной связности для планарного графа нам требуется поддержка неориентированного графа G = (V, E) и выполнение в различном порядке последовательности таких операций, как вставка ребер, удаление ребер и запросы о k-вершинной связности для данного планарного графа. | В полностью динамической задаче k-реберной связности для планарного графа нам требуется поддержка неориентированного графа G = (V, E) и выполнение в различном порядке последовательности таких операций, как вставка ребер, удаление ребер и запросы о k-реберной связности для данного планарного графа. Аналогично, в полностью динамической задаче k-вершинной связности для планарного графа нам требуется поддержка неориентированного графа G = (V, E) и выполнение в различном порядке последовательности таких операций, как вставка ребер, удаление ребер и запросы о k-вершинной связности для данного планарного графа. | ||
Основные результаты | |||
== Основные результаты == | |||
Алгоритмы, предложенные в работах [2] и [3], эффективно решают эти задачи для небольших значений k: | Алгоритмы, предложенные в работах [2] и [3], эффективно решают эти задачи для небольших значений k: | ||
Теорема 3. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнением запросов на проверку 3-вершинной связности графа либо проверку принадлежности двух вершин к одной и той же 3-вершинно-связной компоненте, возможно выполнить за амортизированное время O(n1/2) на один запрос или обновление. | '''Теорема 1. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнением запросов на проверку 2-реберной связности графа либо проверку принадлежности двух вершин к одной и той же 2-реберно-связной компоненте, возможно выполнить за амортизированное время <math>O(log \; n)</math> на одну вставку или запрос и <math>O(log^2 \; n)</math> на одно удаление.''' | ||
'''Теорема 2. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнение запросов на проверку 3-реберной и 4-реберной связности графа возможно выполнить за время O(n1/2) на одно обновление; проверку 3- или 4-реберной связности двух вершин возможно выполнить за время O(n1/2) на одно обновление или запрос.''' | |||
'''Теорема 3. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнением запросов на проверку 3-вершинной связности графа либо проверку принадлежности двух вершин к одной и той же 3-вершинно-связной компоненте, возможно выполнить за амортизированное время O(n1/2) на один запрос или обновление.''' | |||
Границы, определяемые этими теоремами, улучшены по сравнению с границами для графов общего вида, представленными в статье «Полностью динамическая связность высоких степеней». | Границы, определяемые этими теоремами, улучшены по сравнению с границами для графов общего вида, представленными в статье «Полностью динамическая связность высоких степеней». | ||
Применение | |||
== Применение == | |||
Применение динамических алгоритмов реберной и вершинной связности приведено в соответствующем разделе статьи «Полностью динамическая связность высоких степеней». Случай планарных графов особенно важен, поскольку они часто встречаются в различных приложениях. | Применение динамических алгоритмов реберной и вершинной связности приведено в соответствующем разделе статьи «Полностью динамическая связность высоких степеней». Случай планарных графов особенно важен, поскольку они часто встречаются в различных приложениях. | ||