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

Разработка структуры данных для неориентированного графа с фиксированным числом вершин, способной обрабатывать запросы вида «Являются ли вершины i и j связанными?» и поддерживать обновления вида «Вставить ребро {i, j}» и «Удалить ребро {i, j}». Задача состоит в минимизации времени выполнения обновления и запроса для наихудшей последовательности запросов и обновлений. Алгоритмы для решения этой задачи называются «полностью динамическими», поскольку, в отличие от «частично динамических" алгоритмов, выполняют как вставку, так и удаление ребер.