186
правок
Изменения
м
→Динамическая центроидная декомпозиция (дерево центроидной декомпозиции)
{{Определение
|definition="Деревом центроидов (или центроидной декомпозицией)" дерева <math>t</math> называют дерево <math>T</math>, построенное на вершинах дерева <math>t</math> следующим образом :
* Пусть вершина <math>сc</math> - центроид дерева <math>t</math>. Объявим его корнем нового дерева <math>T</math>.* Пусть при удалении вершины <math>c</math> из дерева <math>t</math> оно распалось на поддеревья <mathtex>t_1, t_2,..., t_k</mathtex >, а центроиды этих поддеревьев - вершины <mathtex>c_1, c_2, ..., c_k</mathtex> исходного дерева, соответственно. Проведем ребра из вершины <math>c</math> в дереве <math>T</math> ребра во все вершины <mathtex >c_1, c_2,..., c_k</mathtex>.* Рекурсивно перейдем к построению для поддеревьев <mathtex>t_1, t_2,..., t_k</mathtex>.
}}
