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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 6: Строка 6:
 
* '''<tex>\mathrm{cut(u, w)}</tex>''' {{---}} разрезать ребро (u, w) (при условии, что ребро (u, w) принадлежит дереву),
 
* '''<tex>\mathrm{cut(u, w)}</tex>''' {{---}} разрезать ребро (u, w) (при условии, что ребро (u, w) принадлежит дереву),
 
* '''<tex>\mathrm{isConnected(u, w)}</tex>''' {{---}} принадлежат ли вершины u и w одной компоненте связности.
 
* '''<tex>\mathrm{isConnected(u, w)}</tex>''' {{---}} принадлежат ли вершины u и w одной компоненте связности.
 +
 +
''' Euler tour tree''' - The data structure we'll develop can perform these operations time O(log n) each.
 +
 +
==Euler Tours on Trees==

Версия 19:42, 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