Изменения

Перейти к: навигация, поиск

Задача о динамической связности

14 байт добавлено, 22:31, 14 января 2018
remove(u,v)
{{Утверждение
|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> (либо непосредственно ребром<tex>xy</tex>, либо каким-то другим путём). Но <tex>F_j \subseteq F_i</tex>. Значит, в <tex>F_i</tex> между <tex>x</tex> и <tex>y</tex> сохранился путь из рёбер уровня не меньше <tex>j</tex> и появился другой путь через <tex>uv</tex>. Приходим к противоречию, так как в <tex>F_i</tex> все компоненты должны быть деревьями.
}}
693
правки

Навигация