186
правок
Изменения
→Динамическая центроидная декомпозиция (дерево центроидной декомпозиции)
{{Определение
|definition=
'''Деревом центроидов (или центроидной декомпозицией)''' дерева <math>t</math> называют дерево <math>T(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>, а центроиды этих поддеревьев - тогда детьми вершины c объявим <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_2T(t_t),..., T(t_k)</tex>.
}}
* Каждая вершина <math>v</math> дерева <math>t</math> является центроидом одного из поддеревьев дерева <math>T</math>
* Каждая вершина дерева <math>t</math> принадлежит <math>O(log(n))</math> поддеревьям дерева <math>T</math> (еще говорят, что вершина принадлежит <math>O(log(n))</math> центроидам дерева <math>t</math>, или что эти центроиды содержат вершину)
* Для любых вершин <tex>u, v \in T (u \neq v)</tex> верно ровно одно из следующих трех утверждений :
** <tex>T(v) \subset T(u)<\tex>
** <tex>T(u) \subset T(v)<\tex>
** <tex>T(u) \cap T(v) = \emptyset <\tex>
|proof=
Действительно, т.к. размер поддерева <math>s</math> каждой вершины <math>c</math> дереве <math>T</math> не превосходит <tex>\frac{|subtree(c)|}{2}</tex>, то при спуске в каждую следующую вершину на пути к любому листу в дереве <math>T</math> размер поддерева вершины, в которой мы сейчас находимся, уменьшается как минимум на <math>2</math>. Значит длина всего пути до листа не превосходит <math>log(n)</math>, ч.т.д.
{{Лемма
|statement=
|proof=
}}
