693
правки
Изменения
→remove(u,v)
{{Утверждение
|statement=Если ребро, которое мы хотим удалить, не принадлежит остовному лесу, то связность между любой парой вершин сохранится.
|proof=Докажем от противного. Допустим, что это не так. Понятно, что при разрезании ребра нового пути между вершинами не появится.
Предположим, что нарушилась связность для каких-то двух вершин. Значит, мы убрали мост. А любой мост принадлежит всем остовным деревьям его компоненты. Противоречие.
}}
Рассмотрим случаи, когда мы берём ребро из леса. Тогда необходимо выяснить, не является ли данное ребро мостом в графе, и выполнить соответствующие действия.
Проверим, является ли ребромостом. У ребра <tex>uv</tex> известен уровень, пусть он равен <tex>i</tex>. Попробуем найти другое ребро (<tex>xy</tex>), соединяющее поддеревья <tex>T_u</tex> и <tex>T_v</tex>, на которые распалось остовное дерево исследуемой компоненты. {{Утверждение|statement=<tex>l(xy)\leqslant i</tex>|proof=От противного. Пусть <tex>l(xy)=j</tex> и <tex>j\geqslant i</tex>. Тогда вершины <tex>x</tex> и <tex>y</tex> каким-то образом связаны в <tex>F_j</tex> (либо непосредственно ребром, либо каким-то другим путём. }}
