Полностью динамическая связность высоких степеней в планарных графах
Ключевые слова и синонимы
Полностью динамическая реберная связность; полностью динамическая вершинная связность
Постановка задачи
Здесь будет рассмотрена задача поддержки динамического планарного графа, в котором выполняются операции вставки и удаления ребер, сохраняющие планарность, но способные изменить укладку. Более конкретно, задача заключается в эффективной поддержке информации о реберной и вершинной связности в подобном динамически меняющемся планарном графе. Алгоритмы, решающие эту задачу, должны поддерживать операции вставки, при которых граф сохраняет планарность, независимо от конкретной укладки графа. Подробнее об этом в статье «Полностью динамическая проверка на планарность», в которой описываются эффективные процедуры проверки, выясняющие, остается ли граф планарным после вставки и удаления ребер (независимо от конкретной укладки).
Предварительные определения перед формальным изложением задачи.
Пусть даны неориентированный граф G = (V, E) и целое число [math]\displaystyle{ k \ge 2 }[/math]. Пара вершин {u, v} называется k-реберно-связной, если при удалении любых (k — 1) ребер графа G вершины u и v остаются связанными. Нетрудно заметить, что в данном случае имеет место отношение эквивалентности: вершины графа G этим отношением разбиваются на классы эквивалентности, называемые k-реберно-связными компонентами. Граф G называется k-реберно-связным, если при удалении любых (k — 1) ребер G сохраняет связность. Согласно этим определениям, граф G является k-реберно-связным в том и только том случае, если любые две вершины G являются k-реберно-связными. Множество ребер [math]\displaystyle{ E' \subseteq E \; }[/math] является реберным разрезом для вершин x и y, если удаление всех ребер, входящих в E', разбивает G на два графа, один из которых содержит x, а другой – y. Множество ребер [math]\displaystyle{ E' \subseteq E \; }[/math] является реберным разрезом для G, если удаление всех ребер, входящих в E', разбивает G на два графа. Реберный разрез E' графа G (для x и y, соответственно) является минимальным, если удаление любого ребра из E' восстанавливает связность G (x и y, соответственно). Мощность реберного разреза E', обозначаемая |E'|, задается числом ребер в E'. Реберный разрез E' графа G (вершин x и y, соответственно) называется реберным разрезом минимальной мощности или, вкратце, реберным разрезом связности, если не существует другого реберного разреза E" графа G (x и y, соответственно), такого, что |E"| < |E'|. Реберные разрезы связности, разумеется, являются минимальными реберными разрезами. Заметим, что G является k-реберно-связным в том и только том случае, если реберный разрез связности для G содержит не менее k ребер, а вершины x и y являются k-реберно-связными в том и только том случае, если реберный разрез связности для x и y содержит не менее k ребер. Реберный разрез связности, мощность которого равна 1, называется мостом.
Подобным же образом, множество вершин V' С V – {x, y} называется вершинным разрезом для вершин x и y, если удаление всех вершин V' разрывает связь между x и y. V' С V является вершинным разрезом для вершин графа G, если удаление всех вершин V' разбивает G.
Мощность вершинного разреза V', обозначаемая |V'|, задается числом вершин в V'. Вершинный разрез V' для x и y называется вершинным разрезом минимальной мощности или, вкратце, вершинным разрезом связности, если не существует другого вершинного разреза V" для x и y, такого, что |V"| < |V'|. Тогда x и y являются k-вершинно-связными в том и только том случае, если вершинный разрез связности для x и y содержит не менее k вершин. Граф G называется k-вершинно-связным, если все его пары вершин являются k-вершинно-связными. Вершинный разрез связности, мощность которого равна 1, называется точкой сочленения; вершинный разрез связности мощности 2 называется парой разделителей. Заметим, что для связности по вершинам уже неверно утверждение о том, что вершинный разрез связности разбивает граф G на два множества вершин.
Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким как вставка ребра, удаление ребра и обновление веса ребра. Динамический алгоритм должен быстро обрабатывать запросы о свойстве P, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм является полностью динамическим, если он поддерживает как вставку ребер, так и удаление ребер. Частично динамический алгоритм поддерживает либо вставку, либо удаление ребер; инкрементный алгоритм поддерживает только вставку ребер, декрементный – только удаление. В полностью динамической задаче k-реберной связности для планарного графа нам требуется поддержка неориентированного графа G = (V, E) и выполнение в различном порядке последовательности таких операций, как вставка ребер, удаление ребер и запросы о k-реберной связности для данного планарного графа. Аналогично, в полностью динамической задаче k-вершинной связности для планарного графа нам требуется поддержка неориентированного графа G = (V, E) и выполнение в различном порядке последовательности таких операций, как вставка ребер, удаление ребер и запросы о k-вершинной связности для данного планарного графа.
Основные результаты Алгоритмы, предложенные в работах [2] и [3], эффективно решают эти задачи для небольших значений k: Теорема 1. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнением запросов на проверку 2-реберной связности графа либо проверку принадлежности двух вершин к одной и той же 2-реберно-связной компоненте, возможно выполнить за амортизированное время O(log n) на одну вставку или запрос и O(log n) на одно удаление.
Теорема 2. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнение запросов на проверку 3-реберной и 4-реберной связности графа возможно выполнить за время O(n1/2) на одно обновление; проверку 3- или 4-реберной связности двух вершин возможно выполнить за время O(n1/2) на одно обновление или запрос.
Теорема 3. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнением запросов на проверку 3-вершинной связности графа либо проверку принадлежности двух вершин к одной и той же 3-вершинно-связной компоненте, возможно выполнить за амортизированное время O(n1/2) на один запрос или обновление.
Границы, определяемые этими теоремами, улучшены по сравнению с границами для графов общего вида, представленными в статье «Полностью динамическая связность высоких степеней».
Применение Применение динамических алгоритмов реберной и вершинной связности приведено в соответствующем разделе статьи «Полностью динамическая связность высоких степеней». Случай планарных графов особенно важен, поскольку они часто встречаются в различных приложениях.
Открытые вопросы Некоторые задачи, имеющие отношение к работе Эппстайна и коллег [2, 3], остаются нерешенными. Во-первых, можно ли улучшить время исполнения? Во-вторых, как и в случае графов общего вида, в случае планарных графов полностью динамические задачи 2-реберной связности могут быть решены за полилогарифмическое время на одно обновление, тогда как наилучшие известные границы обновления для реберной и вершинной связности более высоких степеней являются полиномиальными. Остается открытым вопрос, можно ли сократить этот разрыв – иначе говоря, можно ли разработать полилогарифмические алгоритмы хотя бы для полностью динамических задач 3-реберной и 3-вершинной связности. В третьих, можно ли в специальном случае планарных графов решить полностью динамическую задачу k-вершинной связности для любого k?
См. также ► Динамические деревья ► Полностью динамический алгоритм нахождения кратчайших путей между всеми парами ► Полностью динамическая связность ► Полностью динамическая связность высоких степеней ► Полностью динамические минимальные остовные деревья ► Полностью динамическая проверка на планарность ► Полностью динамическое транзитивное замыкание
Литература 1. Galil Z., Italiano G.F., Sarnak N.: Fully dynamic planarity testing with applications. J. ACM 48, 28-91 (1999) 2. Eppstein D., Galil Z., Italiano G.F., Spencer T.H.: Separator based sparsification I: planarity testing and minimum spanning trees. J. Comput. Syst. Sci., Special issue of STOC 93 52(1), 3-27 (1996) 3. Eppstein D., Galil Z., Italiano G.F., Spencer T.H.: Separator based sparsification II: edge and vertex connectivity. SIAM J. Comput. 28,341-381 (1999) 4. Giammarresi D., Italiano G.F.: Decremental 2- and 3-connectivity on planar graphs. Algorithmica 16(3), 263-287 (1996) 5. Hershberger J., M.R., Suri S.: Data structures for two-edge connectivity in planar graphs. Theor. Comput. Sci. 130(1), 139-161 (1994)