Просмотр кода страницы Полностью динамическая связность высоких степеней в планарных графах

== Ключевые слова и синонимы ==
[[Полностью динамическая реберная связность]]; [[полностью динамическая вершинная связность]]


== Постановка задачи ==
Здесь будет рассмотрена задача поддержки динамического планарного графа, в котором выполняются операции вставки и удаления ребер, сохраняющие планарность, но способные изменить укладку. Более конкретно, задача заключается в эффективной поддержке информации о реберной и вершинной связности в подобном динамически меняющемся планарном графе. Алгоритмы, решающие эту задачу, должны поддерживать операции вставки, при которых граф сохраняет планарность, независимо от конкретной укладки графа. Подробнее об этом в статье «[[Полностью динамическая проверка на планарность]]», в которой описываются эффективные процедуры проверки, выясняющие, остается ли граф планарным после вставки и удаления ребер (независимо от конкретной укладки).


Предварительные определения перед формальным изложением задачи.
 

Пусть даны неориентированный граф G = (V, E) и целое число <math>k \ge 2</math>. Пара вершин {u, v} называется [[k-реберная связность|k-реберно-связной]], если при удалении любых (k — 1) ребер графа G вершины u и v остаются связанными. Нетрудно заметить, что в данном случае имеет место отношение эквивалентности: вершины графа G этим отношением разбиваются на классы эквивалентности, называемые k-реберно-связными компонентами. Граф G называется k-реберно-связным, если при удалении любых (k — 1) ребер G сохраняет связность. Согласно этим определениям, граф G является k-реберно-связным в том и только том случае, если любые две вершины G являются k-реберно-связными. Множество ребер <math>E' \subseteq E \; </math> является [[реберный разрез|реберным разрезом]] для вершин x и y, если удаление всех ребер, входящих в E', разбивает G на два графа, один из которых содержит x, а другой – y. Множество ребер <math>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, называется [[мост|мостом]].


Подобным же образом, множество вершин <math>V' \subseteq V - \{ x, y \}</math> называется [[вершинный разрез|вершинным разрезом]] для вершин x и y, если удаление всех вершин V' разрывает связь между x и y. <math>V' \subseteq V \;</math> является вершинным разрезом для вершин графа G, если удаление всех вершин V' разбивает G.


Мощность вершинного разреза V', обозначаемая |V'|, задается числом ребер в V'. Вершинный разрез V' для x и y называется вершинным разрезом минимальной мощности или, вкратце, [[вершинный разрез связности|вершинным разрезом связности]], если не существует другого вершинного разреза V" для x и y, такого, что |V"| < |V'|. Тогда x и y являются k-вершинно-связными в том и только том случае, если вершинный разрез связности для x и y содержит не менее k вершин. Граф G называется [[k-вершинная связность|k-вершинно-связным]], если все его пары вершин являются k-вершинно-связными. Вершинный разрез связности, мощность которого равна 1, называется [[точка сочленения|точкой сочленения]]; вершинный разрез связности мощности 2 называется [[пара разделителей|парой разделителей]]. Заметим, что для связности по вершинам уже неверно утверждение о том, что вершинный разрез связности разбивает граф G на два множества вершин.


Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким как вставка ребра, удаление ребра и обновление веса ребра. Динамический алгоритм должен быстро обрабатывать запросы о свойстве P, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм является полностью динамическим, если он поддерживает как вставку ребер, так и удаление ребер. Частично динамический алгоритм поддерживает либо вставку, либо удаление ребер; инкрементный алгоритм поддерживает только вставку ребер, декрементный – только удаление.

В полностью динамической задаче k-реберной связности для планарного графа нам требуется поддержка неориентированного графа G = (V, E) и выполнение в различном порядке последовательности таких операций, как вставка ребер, удаление ребер и запросы о k-реберной связности для данного планарного графа. Аналогично, в полностью динамической задаче k-вершинной связности для планарного графа нам требуется поддержка неориентированного графа G = (V, E) и выполнение в различном порядке последовательности таких операций, как вставка ребер, удаление ребер и запросы о k-вершинной связности для данного планарного графа.


== Основные результаты ==
Алгоритмы, предложенные в работах [2] и [3], эффективно решают эти задачи для небольших значений k:


'''Теорема 1. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнением запросов на проверку 2-реберной связности графа либо проверку принадлежности двух вершин к одной и той же 2-реберно-связной компоненте, возможно выполнить за амортизированное время <math>O(log \; n)</math> на одну вставку или запрос и <math>O(log^2 \; n)</math> на одно удаление.'''


'''Теорема 2. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнение запросов на проверку 3-реберной и 4-реберной связности графа возможно выполнить за время <math>O(n^{1/2}) \; </math> на одно обновление; проверку 3- или 4-реберной связности двух вершин возможно выполнить за время <math>O(n^{1/2} \; )</math> на одно обновление или запрос.'''


'''Теорема 3. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнением запросов на проверку 3-вершинной связности графа либо проверку принадлежности двух вершин к одной и той же 3-вершинно-связной компоненте, возможно выполнить за амортизированное время <math>O(n^{1/2}) \; </math> на один запрос или обновление.'''


Границы, определяемые этими теоремами, улучшены по сравнению с границами для графов общего вида, представленными в статье «[[Полностью динамическая связность высоких степеней]]».

== Применение ==
Применение динамических алгоритмов реберной и вершинной связности приведено в соответствующем разделе статьи «[[Полностью динамическая связность высоких степеней]]». Случай планарных графов особенно важен, поскольку они часто встречаются в различных приложениях.


== Открытые вопросы ==
Некоторые задачи, имеющие отношение к работе Эппстайна и коллег [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)