Деревья Эйлерова обхода — различия между версиями
Sokolova (обсуждение | вклад) (→Euler Tours on Trees) |
Sokolova (обсуждение | вклад) (→Euler Tours on Trees) |
||
| Строка 13: | Строка 13: | ||
Euler Tours | Euler Tours | ||
| − | In a graph G, an Euler tour is a path through the graph that visits every edge exactly once. | + | In a graph G, an Euler tour is a path through the graph that visits every edge exactly once.<br> |
Mathematically formulates the “trace this figure without picking up your pencil or redrawing any lines” puzzles. | Mathematically formulates the “trace this figure without picking up your pencil or redrawing any lines” puzzles. | ||
Версия 22:09, 28 ноября 2016
Содержание
Введение
Динамические деревья (англ.dynamic tree) используются в двух областях:.........
Нужно поддерживать следующие операции
- — добавить ребро (u, w) (при условии, что вершины u w принадлежат разным деревьям)
- — разрезать ребро (u, w) (при условии, что ребро (u, w) принадлежит дереву),
- — принадлежат ли вершины u и w одной компоненте связности.
Euler tour tree - The data structure we'll develop can perform these operations time O(log n) each.
Euler Tours on Trees
Euler Tours
In a graph G, an Euler tour is a path through the graph that visits every edge exactly once.
Mathematically formulates the “trace this figure without picking up your pencil or redrawing any lines” puzzles.
Properties of Euler Tours
Операции
Rerooting a Tour
link(u ,v)
cut(u ,v)
Реализация структуры
Linked Lists
Balanced Trees
Сравнительная табличка
Похожие структуры
Про link-cut trees
