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