4446
правок
Полностью динамическая связность высоких степеней в планарных графах: различия между версиями
Материал из WEGA
Полностью динамическая связность высоких степеней в планарных графах (посмотреть исходный код)
Версия от 17:18, 17 июля 2014
, 17 июля 2014→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Полностью динамическая реберная связность; [[полностью д…») |
Irina (обсуждение | вклад) |
||
| Строка 13: | Строка 13: | ||
Подобным же образом, множество вершин V' | Подобным же образом, множество вершин <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, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм является полностью динамическим, если он поддерживает как вставку ребер, так и удаление ребер. Частично динамический алгоритм поддерживает либо вставку, либо удаление ребер; инкрементный алгоритм поддерживает только вставку ребер, декрементный – только удаление. | Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким как вставка ребра, удаление ребра и обновление веса ребра. Динамический алгоритм должен быстро обрабатывать запросы о свойстве P, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм является полностью динамическим, если он поддерживает как вставку ребер, так и удаление ребер. Частично динамический алгоритм поддерживает либо вставку, либо удаление ребер; инкрементный алгоритм поддерживает только вставку ребер, декрементный – только удаление. | ||
