Пусть хотим добавить ребро <tex>\{c, g\} \</tex>
Выберем любое вхождение вершины <tex>с</tex> в эйлеров обход В эйлеровом обходе T1Разрежем эйлеров обход T1 на 2 частиA1 - часть обхода до выбранного вхождения вершины <tex>с</tex>A2 - часть обхода после выбранного вхождения вершины <tex>с</tex>Аналогично, выберем любое вхождение вершины <tex>g</tex> в эйлеров обход T2 и разрежем его на 2 части B1 и B2Соберем результирующий эйлеров обход в порядке A1 B2 B1 A2 Чтобы быстро находить место, где разрезать эйлеровы обходы T1 и T2, будем хранить эйлеровы обходы в двоичных деревьях поиска. Ключом вершины, для построения дерева поиска, будет время посещения этой вершины эйлеровым обходом.Для каждой вершины дерева (T1, T2) будем хранить указатель на вершину в дереве поиска, которая соответствует вхождению вершины дерева в эйлеров обход. Тогда за O(1) переходим от вершины дерева к вершине дерева поиска, по которой за O(log n) можно будет разделить дерево поиска на 2 части.
===Разрезание ребра===
