Деревья Эйлерова обхода — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Euler Tours on Trees)
(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) используются в двух областях:.........

Нужно поддерживать следующие операции

  • [math]\mathrm{link(u, w)}[/math] — добавить ребро (u, w) (при условии, что вершины u w принадлежат разным деревьям)
  • [math]\mathrm{cut(u, w)}[/math] — разрезать ребро (u, w) (при условии, что ребро (u, w) принадлежит дереву),
  • [math]\mathrm{isConnected(u, w)}[/math] — принадлежат ли вершины 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