693
правки
Изменения
→remove(u,v)
[[Файл:Another_edge.jpg|200px|thumb|right]]
{{Утверждение
|statement=Если ребро, которое мы хотим удалить, не принадлежит остовному лесу, то связность между любой парой вершин сохранится.
|proof=Допустим, что это не так. Понятно, что при разрезании ребра нового пути между вершинами не появится.
Предположим, что нарушилась связность для каких-то двух вершин. Значит, мы убрали мост. А любой мост принадлежит всем остовным деревьям его компоненты. Противоречие.
}}
<!----При удалении возможны случаи:
* '''Удаляемое ребро является мостом'''. В этом случае дерево распадается на две части (назовём их <tex>T(u)</tex> и <tex>T(v)</tex>), и задача решается как для дерева за <tex>O(\log n)</tex>.
