Изменения

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

Деревья Эйлерова обхода

252 байта добавлено, 12:05, 3 декабря 2016
Представление деревьев в виде их эйлерова обхода
В основном, [[Дерево, эквивалентные определения|деревья]] не являются [[Эйлеровость графов|эйлеровыми графами]].
Technique: replace each edge Заменим каждое ребро <tex>{u, v} with two edges </tex> на два ребра <tex>(u, v) and </tex> и <tex>(v, u).<br/tex>. Resulting graph has an Euler tourПолучившийся [[Основные определения теории графов|ориентированный граф]] будет эйлеровым согласно [[Эйлеровость графов|критерию]].
High-level idea: Instead of storing the trees in the forest, store their Euler tours.
635
правок

Навигация