186
правок
Изменения
→Свойства центроидной декомпозиции
'''Свойства центроидной декомпозиции''' :
* Глубина дерева центроидов не превосходит <tex>log(n)</tex>.
* Каждая вершина <math>v</math> дерева <math>t</math> является центроидом одного из поддеревьев дерева <math>Tt</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> верно ровно одно из следующих трех утверждений :
