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

Мощность вершинного разреза 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.