Деревья Эйлерова обхода — различия между версиями
Sokolova (обсуждение | вклад) |
Sokolova (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
Нужно поддерживать следующие операции | Нужно поддерживать следующие операции | ||
| − | * '''<tex>\mathrm{ | + | * '''<tex>\mathrm{isConnected(u, w)}</tex>''' {{---}} принадлежат ли вершины u и w одной компоненте связности, |
* '''<tex>\mathrm{link(u, w)}</tex>''' {{---}} добавить ребро (u, w) (при условии, что ребро u w принадлежат разным деревьям) | * '''<tex>\mathrm{link(u, w)}</tex>''' {{---}} добавить ребро (u, w) (при условии, что ребро u w принадлежат разным деревьям) | ||
* '''<tex>\mathrm{cut(u, w)}</tex>''' {{---}} разрезать ребро (u, w) (при условии, что ребро (u, w) принадлежит дереву)<tex>\mathrm{v}</tex>. | * '''<tex>\mathrm{cut(u, w)}</tex>''' {{---}} разрезать ребро (u, w) (при условии, что ребро (u, w) принадлежит дереву)<tex>\mathrm{v}</tex>. | ||
Версия 19:38, 28 ноября 2016
Введение
Динамические деревья (англ.dynamic tree) используются в двух областях:.........
Нужно поддерживать следующие операции
- — принадлежат ли вершины u и w одной компоненте связности,
- — добавить ребро (u, w) (при условии, что ребро u w принадлежат разным деревьям)
- — разрезать ребро (u, w) (при условии, что ребро (u, w) принадлежит дереву).
