693
правки
Изменения
→remove(u,v)
}}
Чтобы найти <tex>xy</tex>, выберем из поддеревьев <tex>T_u</tex> и <tex>T_v</tex> наименьшее. Не умаляя общности, будем считать, что <tex>|T(u)|\leqslant|T_v|</tex>. <!--ежу понятно--> Так как хотя бы одно из двух слагаемых всегда не превосходит половины их суммы, имеем важное свойство: <tex>|T(u)|\leqslant\dfrac{|T_u|+|T_v|}{2}=\dfrac{|T|}{2}</tex>. Также нам известно, что <tex>T \subseteq F_i</tex>, а значит, <tex>|T|\leqslant\dfrac{n}{2^i}</tex>. Отсюда <tex>|T(u)|\leqslant\dfrac{n}{2^{i+1}}</tex>. Это неравенство позволит нам увеличивать уровни рёбер при необходимости.
Попробуем найти подходящую вершину <tex>x</tex> в <tex>T_u</tex> следующим образом:
# Если исходящее ребро ведёт в <tex>T_v</tex>, то добавляем ребро <tex>xy</tex> в остовные леса <tex>F_i</tex>, для которых <tex>i\leqslant l(xy)</tex> и выходим из цикла;
# Если исходящее ребро ведёт в другую вершину поддерева <tex>T_u</tex>, увеличиваем его уровень;
# Если есть непроверенные рёбра, переходим к пункту 1;
# Если таких рёбер не осталось, уменьшаем уровень на единицу и переходим к пункту 1;
# Если все рёбра просканированы, то <tex>xy</tex> является мостом.
<!----При удалении возможны случаи:
