Аноним

Полностью динамическая связность высоких степеней: различия между версиями

Материал из WEGA

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

Версия от 19:14, 25 ноября 2024

1258 байт добавлено ,  25 ноябрь
→‎Литература
(Новая страница: «Ключевые слова и синонимы Полностью динамическая реберная связность; полностью динамич…»)
 
 
(не показано 14 промежуточных версий 2 участников)
Строка 1: Строка 1:
Ключевые слова и синонимы
== Ключевые слова и синонимы ==
Полностью динамическая реберная связность; полностью динамическая вершинная связность
'''Полностью динамическая связность высоких степеней''' --- ''Fully Dynamic Higher Connectivity''


Постановка задачи
Полностью динамическая реберная связность (''Fully dynamic edge connectivity''); полностью динамическая вершинная связность (''Fully dynamic vertex connectivity'')
Задача заключается в эффективной поддержке информации о реберной и вершинной связности в динамически меняющемся графе. Предварительные определения перед формальной формулировкой задачи.


Пусть даны неориентированный граф G = (V, E) и целое число к > 2. Пара вершин hu; vi называется k-реберно-связной, если при удалении любых (k — 1) ребер графа G вершины u и v остаются связанными. Нетрудно заметить, что в данном случае имеет место отношение эквивалентности: вершины графа G этим отношением разбиваются на классы эквивалентности, называемые k-реберно-связными компонентами. Граф G называется k-реберно-связным, если при удалении любых (k — 1) ребер G сохраняет связность. Согласно этим определениям, граф G является k-реберно-связным в том и только том случае, если любые две вершины G являются k-реберно-связными. Множество ребер E0 С E является реберным разрезом для вершин x и y, если удаление всех ребер, входящих в E0, разбивает G на два графа, один из которых содержит x, а другой – y. Множество ребер E0 С E является реберным разрезом для G, если удаление всех ребер, входящих в E0, разбивает G на два графа. Реберный разрез E0 графа G (для x и y, соответственно) является минимальным, если удаление любого ребра из E0 восстанавливает связность G (x и y, соответственно). Мощность реберного разреза E0, обозначаемая jE0j, задается числом ребер в E0. Реберный разрез E0 графа G (вершин x и y, соответственно) называется реберным разрезом минимальной мощности или, вкратце, реберным разрезом связности, если не существует другого реберного разреза E00 графа G (x и y, соответственно), такого, что \E"\ < jE0j. Реберные разрезы связности, разумеется, являются минимальными реберными разрезами. Заметим, что G является k-реберно-связным в том и только том случае, если реберный разрез связности для G содержит не менее k ребер, а вершины x и y являются k-реберно-связными в том и только том случае, если реберный разрез связности для x и y содержит не менее k ребер. Реберный разрез связности, мощность которого равна 1, называется мостом.
== Постановка задачи ==
Задача заключается в эффективной поддержке информации о реберной и вершинной связности в динамически меняющемся графе.
 
 
Пусть даны неориентированный граф 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, называется [[мост|мостом]].
   
   
Следующая теорема, которую предложили Форд и Фулкерсон, а также Элиас, Файнштайн и Шеннон [ ], дает еще одну характеристику k-реберной-связности.


Теорема 1 (Форд и Фулкерсон; Элиас, Файнштайн и Шеннон). Пусть даны граф G и две вершины x и y, принадлежащие G. x и y являются k-реберно-связными в том и только том случае, если между x и y имеется не менее k путей с непересекающимися ребрами.
Следующая теорема, которую предложили Форд и Фулкерсон, а также Элиас, Файнштайн и Шеннон [7], дает еще одну характеристику k-реберной-связности.
 
 
'''Теорема 1 (Форд и Фулкерсон; Элиас, Файнштайн и Шеннон). Пусть даны граф G и две вершины x и y, принадлежащие G. Вершины x и y являются k-реберно-связными в том и только том случае, если между x и y имеется не менее k путей с непересекающимися ребрами.'''
 
 
Подобным же образом, множество вершин <math>V' \subseteq V - \{ x, y \}</math> называется [[вершинный разрез|вершинным разрезом]] для вершин x и y, если удаление всех вершин V' разрывает связь между x и y. <math>V' \subseteq V \;</math> является вершинным разрезом для вершин графа G, если удаление всех вершин V' разбивает G.
 


Подобным же образом, множество вершин V0 С V — {x, yg называется вершинным разрезом для вершин x и y, если удаление всех вершин V0 разрывает связь между x и y. V0 С V является вершинным разрезом для вершин графа G, если удаление всех вершин V0 разбивает 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 на два множества вершин.


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


Следующая теорема, предложенная Менгером [7], дает еще одну характеристику k-вершинной связности.
Следующая теорема, предложенная Менгером [7], дает еще одну характеристику k-вершинной связности.


Теорема 2 (Менгер). Пусть даны граф G и две вершины x и y, принадлежащие G. x и y являются k-вершинно-связными в том и только том случае, если между x и y имеется не менее k вершинно-непересекающихся путей.


Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким как вставка дуги, удаление дуги и обновление веса дуги. Динамический алгоритм должен быстро обрабатывать запросы о свойстве T, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм является полностью динамическим, если он поддерживает как вставку дуг, так и удаление дуг. Частично динамический алгоритм поддерживает либо вставку, либо удаление дуг; инкрементный алгоритм поддерживает только вставку дуг, декрементный – только удаление. В полностью динамической задаче k-реберной связности нам требуется поддержка неориентированного графа G = (V, E) и выполнение последовательности следующих операций в различном порядке:
'''Теорема 2 (Менгер). Пусть даны граф G и две вершины x и y, принадлежащие G. Вершины x и y являются k-вершинно-связными в том и только том случае, если между x и y имеется не менее k вершинно-непересекающихся путей.'''
 
 
Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким как вставка ребра, удаление ребра и обновление веса ребра. Динамический алгоритм должен быстро обрабатывать запросы о свойстве P, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм называется [[полностью динамический алгоритм|полностью динамическим]], если он поддерживает как вставку ребер, так и удаление ребер. [[Частично динамический алгоритм]] поддерживает либо вставку, либо удаление ребер; [[инкрементный алгоритм]] поддерживает только вставку ребер, [[декрементный алгоритм|декрементный]] – только удаление.
 
 
В полностью динамической задаче k-реберной связности нам требуется поддержка неориентированного графа G = (V, E) и выполнение последовательности следующих операций в различном порядке:
 
• k-EdgeConnected(u, v): возвращает значение «истинно», если вершины u и v принадлежат к одной и той же k-реберно-связной компоненте графа, в противном случае возвращает значение «ложно».
• k-EdgeConnected(u, v): возвращает значение «истинно», если вершины u и v принадлежат к одной и той же k-реберно-связной компоненте графа, в противном случае возвращает значение «ложно».
• Insert(x, y): вставляет новую дугу между вершинами x и y.
 
• Delete(x,y): удаляет дугу между вершинами x и y.
• Insert(x, y): вставляет новое ребро между вершинами x и y.
 
• Delete(x,y): удаляет ребро между вершинами x и y.
 
 
В полностью динамической задаче k-вершинной связности нам требуется поддержка неориентированного графа G = (V, E) и выполнение последовательности следующих операций в различном порядке:
В полностью динамической задаче k-вершинной связности нам требуется поддержка неориентированного графа G = (V, E) и выполнение последовательности следующих операций в различном порядке:
• k-VertexConnected(u, v): возвращает значение «истинно», если вершины u и v принадлежат к одной и той же k-вершинно-связной компоненте графа, в противном случае возвращает значение «ложно».
• k-VertexConnected(u, v): возвращает значение «истинно», если вершины u и v принадлежат к одной и той же k-вершинно-связной компоненте графа, в противном случае возвращает значение «ложно».
• Insert(x, y): вставляет новую дугу между вершинами x и y.
• Delete(x,y): удаляет дугу между вершинами x и y.


Основные результаты
• Insert(x, y): вставляет новое ребро между вершинами x и y.
 
• Delete(x,y): удаляет ребро между вершинами x и y.
 
== Основные результаты ==
Наиболее эффективные на данный момент полностью динамические алгоритмы вычисления k-реберной и k-вершинной связности были предложены в работах [3] и [12]. Время исполнения характеризуется следующими теоремами.
Наиболее эффективные на данный момент полностью динамические алгоритмы вычисления k-реберной и k-вершинной связности были предложены в работах [3] и [12]. Время исполнения характеризуется следующими теоремами.


Теорема 3. Полностью динамическая задача k-реберной связности может быть решена за время:
Теорема 3. Полностью динамическая задача k-реберной связности может быть решена за время:
1. O(log n) на одно обновление и O(log n) на один запрос
 
для k = 2
1. <math>O(log^4 \; n)</math> на одно обновление и <math>O(log^3 \; n)</math> на один запрос для k = 2
2. O(n2/3) на одно обновление и один запрос для k = 3
 
3. O(na(n)) на одно обновление и один запрос для k = 4
2. <math>O(n^{2/3}) \; </math> на одно обновление или один запрос для k = 3
4. O(n log n) на одно обновление и один запрос для k > 5.
 
3. <math>O(n \alpha (n)) \; </math> на одно обновление или один запрос для k = 4
 
4. <math>O(n \; log \; n)</math> на одно обновление или один запрос для k > 5.
 


Теорема 4. Полностью динамическая задача k-вершинной связности может быть решена за время:
Теорема 4. Полностью динамическая задача k-вершинной связности может быть решена за время:
1. O(log  n) на одно обновление и O(log  n) на один запрос
для k = 2
2. O(n) на одно обновление и один запрос для k = 3
3. O(na(n)) на одно обновление и один запрос для k = 4.


Применение
1. <math>O(log^4 \; n)</math> на одно обновление и <math>O(log^3 \; n)</math> на один запрос для k = 2
 
2. <math>O(n) \; </math> на одно обновление или один запрос для k = 3
 
3. <math>O(n \alpha (n)) \; </math> на одно обновление или один запрос для k = 4.
 
== Применение ==
Задачи вершинной и реберной связности часто возникают в вопросах, связанных с надежностью и живучестью сетей. В компьютерных сетях вершинная связность графов, лежащих в их основе, соответствует наименьшему числу узлов, падение которых еще не приведет к потере связности всей сети. Подобным же образом, реберная связность графов соответствует наименьшему числу связей, падение которых еще не вызовет потери связности всей сети. Аналогично, если две вершины являются k-вершинно-связными, они останутся связанными даже при отказе до (k – 1) других вершин, а если они являются k-реберно-связными, они «переживут» отказ до (k – 1) связей. Важно изучать динамические версии этих задач в контекстах, где сети динамически меняются – например, в случаях, когда связи могут нарушаться и восстанавливаться из-за отказов и ремонтов.
Задачи вершинной и реберной связности часто возникают в вопросах, связанных с надежностью и живучестью сетей. В компьютерных сетях вершинная связность графов, лежащих в их основе, соответствует наименьшему числу узлов, падение которых еще не приведет к потере связности всей сети. Подобным же образом, реберная связность графов соответствует наименьшему числу связей, падение которых еще не вызовет потери связности всей сети. Аналогично, если две вершины являются k-вершинно-связными, они останутся связанными даже при отказе до (k – 1) других вершин, а если они являются k-реберно-связными, они «переживут» отказ до (k – 1) связей. Важно изучать динамические версии этих задач в контекстах, где сети динамически меняются – например, в случаях, когда связи могут нарушаться и восстанавливаться из-за отказов и ремонтов.
   
   
Открытые вопросы
== Открытые вопросы ==
Эппстайн и коллеги [], а также Холм и коллеги [12] поднимают интересные вопросы. Во-первых, если эффективные динамические алгоритмы вычисления k-реберной связности для общих значений k известны, то для вычисления k-вершинной связности при k > 5 эффективных полностью динамических алгоритмов еще не создано – более того, нет даже статических.  Во-вторых, полностью динамические задачи 2-реберной и 2-вершинной связности могут быть решены за полилогарифмическое время на одно обновление, тогда как наилучшие известные границы обновления для реберной и вершинной связности более высоких степеней являются полиномиальными. Остается открытым вопрос, можно ли сократить этот разрыв – иначе говоря, можно ли разработать полилогарифмические алгоритмы для полностью динамических задач 3-реберной и 3-вершинной связности.
Эпстайн и коллеги [3], а также Холм и коллеги [12] поднимают интересные вопросы. Во-первых, если эффективные динамические алгоритмы вычисления k-реберной связности для общих значений k известны, то для вычисления k-вершинной связности при <math>k \ge 5 \; </math> эффективных полностью динамических алгоритмов еще не создано – более того, нет даже статических.  Во-вторых, полностью динамические задачи 2-реберной и 2-вершинной связности могут быть решены за полилогарифмическое время на одно обновление, тогда как наилучшие известные границы обновления для реберной и вершинной связности более высоких степеней являются полиномиальными. Остается открытым вопрос, можно ли сократить этот разрыв – иначе говоря, можно ли разработать полилогарифмические алгоритмы для полностью динамических задач 3-реберной и 3-вершинной связности.


См. также
== См. также ==
► Динамические деревья
* ''[[Динамические деревья]]
► Полностью динамический алгоритм нахождения кратчайших путей между всеми парами
* ''[[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]]
► Полностью динамическая связность
* ''[[Полностью динамическая связность]]
► Полностью динамическая высокая связность в планарных графах
* ''[[Полностью динамическая высокая связность в планарных графах]]
► Полностью динамические минимальные остовные деревья
* ''[[Полностью динамические минимальные остовные деревья]]
► Полностью динамическая проверка на планарность
* ''[[Полностью динамическая проверка на планарность]]
► Полностью динамическое транзитивное замыкание
* ''[[Полностью динамический алгоритм транзитивного замыкания]]


Литература
== Литература ==
1. Dinitz, E.A.: Maintaining the 4-edge-connected components of a graph on-line. In: Proc. 2nd Israel Symp. Theory of Computing and Systems, 1993, pp. 88-99
1. Dinitz, E.A.: Maintaining the 4-edge-connected components of a graph on-line. In: Proc. 2nd Israel Symp. Theory of Computing and Systems, 1993, pp. 88-99
2. Dinitz, E.A., Karzanov A.V., Lomonosov M.V.: On the structure of the system of minimal edge cuts in a graph. In: Fridman, A.A. (ed) Studies in Discrete Optimization, pp. 290-306. Nauka, Moscow (1990). In Russian
2. Dinitz, E.A., Karzanov A.V., Lomonosov M.V.: On the structure of the system of minimal edge cuts in a graph. In: Fridman, A.A. (ed) Studies in Discrete Optimization, pp. 290-306. Nauka, Moscow (1990). In Russian
3. Eppstein, D., Galil Z., Italiano G.F., Nissenzweig A.: Sparsification - a technique for speeding up dynamic graph algorithms. J. Assoc. Comput. Mach. 44(5), 669-696 (1997)
3. Eppstein, D., Galil Z., Italiano G.F., Nissenzweig A.: Sparsification - a technique for speeding up dynamic graph algorithms. J. Assoc. Comput. Mach. 44(5), 669-696 (1997)
4. Frederickson, G.N.: Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SIAM J. Comput. 26(2), 484-538 (1997)
4. Frederickson, G.N.: Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SIAM J. Comput. 26(2), 484-538 (1997)
5. Galil, Z., Italiano, G. F.: Fully dynamic algorithms for 2-edge-connectivity. SIAM J. Comput. 21,1047-1069 (1992)
5. Galil, Z., Italiano, G. F.: Fully dynamic algorithms for 2-edge-connectivity. SIAM J. Comput. 21,1047-1069 (1992)
6. Galil, Z., Italiano, G.F.: Maintaining the 3-edge-connected components of a graph on-line. SIAM J. Comput. 22,11 -28 (1993) Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)
 
7. Henzinger, M.R.: Fully dynamic biconnectivity in graphs. Algorithmica 13(6), 503-538 (1995)
6. Galil, Z., Italiano, G.F.: Maintaining the 3-edge-connected components of a graph on-line. SIAM J. Comput. 22,11-28 (1993) Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)
8. Henzinger, M.R.: Improved data structures for fully dynamic biconnectivity. SIAM J. Comput. 29(6), 1761 -1815 (2000)
 
7. Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)
 
8. Henzinger, M.R.: Fully dynamic biconnectivity in graphs. Algorithmica 13(6), 503-538 (1995)
 
9. Henzinger, M.R.: Improved data structures for fully dynamic biconnectivity. SIAM J. Comput. 29(6), 1761–1815 (2000)


10. Henzinger, M., King V.: Fully dynamic biconnectivity and transitive closure. In: Proc. 36th IEEE Symposium on Foundations of Computer Science (FOCS'95), 1995, pp. 664-672
10. Henzinger, M., King V.: Fully dynamic biconnectivity and transitive closure. In: Proc. 36th IEEE Symposium on Foundations of Computer Science (FOCS'95), 1995, pp. 664-672
11. Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46(4),502-516(1999)
11. Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46(4),502-516(1999)
12. Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48,723-760 (2001)
12. Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48,723-760 (2001)
13. Karzanov, A.V., Timofeev, E. A.: Efficient algorithm for finding all minimal edge cuts of a nonoriented graph. Cybernetics 22, 156-162(1986)
13. Karzanov, A.V., Timofeev, E. A.: Efficient algorithm for finding all minimal edge cuts of a nonoriented graph. Cybernetics 22, 156-162(1986)
14. La Poutre, J.A.: Maintenance of triconnected components of graphs. In: Proc. 19th Int. Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 623, pp. 354-365. Springer, Berlin (1992)
14. La Poutre, J.A.: Maintenance of triconnected components of graphs. In: Proc. 19th Int. Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 623, pp. 354-365. Springer, Berlin (1992)
15. La Poutre, J.A.: Maintenance of 2- and 3-edge-connected components of graphs II. SIAM J. Comput. 29(5), 1521 -1549 (2000)
15. La Poutre, J.A.: Maintenance of 2- and 3-edge-connected components of graphs II. SIAM J. Comput. 29(5), 1521 -1549 (2000)
16. La Poutre, J.A., van Leeuwen, J., Overmars, M.H.: Maintenance of 2- and 3-connected components of graphs, part I: 2- and 3-edge-connected components. Discret. Math. 114, 329-359 (1993)
16. La Poutre, J.A., van Leeuwen, J., Overmars, M.H.: Maintenance of 2- and 3-connected components of graphs, part I: 2- and 3-edge-connected components. Discret. Math. 114, 329-359 (1993)
17. La Poutre, J.A., Westbrook, J.: Dynamic two-connectivity with backtracking. In: Proc. 5th ACM-SIAM Symp. Discrete Algorithms, 1994, pp. 204-212
17. La Poutre, J.A., Westbrook, J.: Dynamic two-connectivity with backtracking. In: Proc. 5th ACM-SIAM Symp. Discrete Algorithms, 1994, pp. 204-212
18. Westbrook, J., Tarjan, R.E.: Maintaining bridge-connected and biconnected components on-line. Algorithmica 7, 433-464 (1992)
18. Westbrook, J., Tarjan, R.E.: Maintaining bridge-connected and biconnected components on-line. Algorithmica 7, 433-464 (1992)
[[Категория: Совместное определение связанных терминов]]
Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/10671...15667