635
правок
Изменения
→Euler Tours on Trees
[[Файл:Simple graph.png |400px|thumb|center|Пример ]]
Euler Tours on Trees
In general, trees do not have Euler tours.
[[Файл:Simple graph.png |400px|thumb|center|Пример ]]
Technique: replace each edge {u, v} with two edges (u, v) and (v, u).<br>
Resulting graph has an Euler tour.
High-level idea: Instead of storing the trees in the forest, store their Euler tours.
Each edge insertion or deletion translates into a set of manipulations on the Euler tours of the trees in the forest.<br>
Checking whether two nodes are connected can be done by checking if they're in the same Euler tour.
==Properties of Euler Tours==
