635
правок
Изменения
→Разрезание ребра
===Разрезание ребра===
Для удаления ребра <tex>\{g, j\} \</tex>:
Чтобы быстро находить места в эйлеровом обходе, которые соответствуют прохождению удаляемого ребра в дереве, будем для каждого ребра в дереве хранить ссылку на те места эйлерова обхода, где последовательно посещаем концы удаляемого ребра.
Так, для ребра (g, j) храним ссылки на узлы дерева поиска, соответствующие парам посещений концов этого ребра.
[[Файл:Link23.png |thumb|400px|center|Рис.1a Исходное дерево <br>Рис.1b Эйлеров обход исходного дерева<br> Рис.1с Двоичное дерево поиска для хранения эйлерового обхода <br> Рис.1d Эйлеровы обходы получившихся деревьев]]
===Проверка на связность===
