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> оно распалось на поддеревья <tex>t_1, t_2,..., t_k</tex >, а центроиды этих поддеревьев - вершины < tex>c_1, c_2, ..., c_k</tex> исходного дерева, соответственно. Проведем ребра из вершины <math>c</math> в дереве <math>T</math> ребра во все вершины < tex >c_1, c_2,..., c_k</tex>.
* Рекурсивно перейдем к построению для поддеревьев <tex>t_1, t_2,..., t_k</tex>.
}}
