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

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

Пусть даны неориентированный граф G = (V, E) и целое число <math>k \ge 2</math>. Пара вершин hu; vi называется [[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, называется [[мост|мостом]].

Мощность вершинного разреза 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, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм называется [[полностью динамический алгоритм|полностью динамическим]], если он поддерживает как вставку дуг, так и удаление дуг. [[Частично динамический алгоритм]] поддерживает либо вставку, либо удаление дуг; [[инкрементный алгоритм]] поддерживает только вставку дуг, [[декрементный алгоритм|декрементный]] – только удаление.

• Insert(x, y): вставляет новую дугу между вершинами x и y.

• Delete(x,y): удаляет дугу между вершинами x и y.

• Insert(x, y): вставляет новую дугу между вершинами x и y.

• Delete(x,y): удаляет дугу между вершинами x и y.

Эппстайн и коллеги [], а также Холм и коллеги [12] поднимают интересные вопросы. Во-первых, если эффективные динамические алгоритмы вычисления k-реберной связности для общих значений k известны, то для вычисления k-вершинной связности при <math>k \ge 5 \; </math> эффективных полностью динамических алгоритмов еще не создано – более того, нет даже статических.  Во-вторых, полностью динамические задачи 2-реберной и 2-вершинной связности могут быть решены за полилогарифмическое время на одно обновление, тогда как наилучшие известные границы обновления для реберной и вершинной связности более высоких степеней являются полиномиальными. Остается открытым вопрос, можно ли сократить этот разрыв – иначе говоря, можно ли разработать полилогарифмические алгоритмы для полностью динамических задач 3-реберной и 3-вершинной связности.

* ''[[Полностью динамическое транзитивное замыкание]]