693
правки
Изменения
→Обобщение задачи для произвольных графов
Введём функцию <tex>l(e):e{\rightarrow}[0;\mathrm{\log} n]</tex> и назовём её ''уровнем ребра'' <tex>e</tex>. Будем рассматривать графы <tex>G_i=\langle V, E\rangle: {E|l(E) \geqslant i}</tex>. Очевидно, что <tex>G_{\mathrm{\log}n} \subseteq G_{\mathrm{\log}n-1} \subseteq ... \subseteq G_1 \subseteq G_0</tex>. Выделим в них остовные леса таким образом, чтобы <tex>F_{\mathrm{\log}n} \subseteq F_{\mathrm{\log}n-1} \subseteq ... \subseteq F_1 \subseteq F_0</tex>, где <tex>F_i</tex> {{---}} остовный лес графа <tex>G_i</tex>.
При удалении возможны случаи:* '''Удаляемое ребро является мостом'''. В этом случае дерево распадается на две части, и задача решается как для дерева за <tex>O(\mathrm{\log}n)<!--При выполнении операции add что/tex>.* '''Удаляемое ребро не является мостом'''. Тогда существует другое ребро, соединяющее две части исходной компоненты (под частями подразумевается какое-то хорошееразбиение множества вершин на два, а с удалением не всё так простопри этом вершины <tex>u</tex> и <tex>v</tex> лежат в разных частях.--Если <tex>uv</tex>принадлежало нашему лесу, то передаём эту "функцию" новому ребру. Осталось узнать, как проверить, является ли ребро мостом. <!-- === Псевдокод === xz я лошара) -->
<!--== Алгоритм ==
=== Время работы === // i think i'll tell it
