|statement=
'''Свойства центроидной декомпозиции''' :
* # Глубина дерева центроидов не превосходит <tex>log(n)</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> верно ровно одно из следующих трех утверждений: a) <tex>T(v) \subset T(u)</tex>
b) <tex>T(u) \subset T(v)</tex>
c) <tex>T(u) \cap T(v) = \emptyset </tex>* # Простой путь между любой парой вершин <math>u, v</math> в дереве <math>t</math> содержит центроид <tex>c \in T(t)</tex>, такой что <tex>u, v \in T(c)</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>, ч.т.д.* # Второе свойство очевидно из построения дерева <math>T</math>, т.к. если вершина принадлежит дереву центроидов <math>T</math>, то она является центроидом, а из построения <math>T</math> мы знаем, что каждая вершина исходного дерева принадлежит и дереву <math>T</math>.* # Третье свойство {{---}} прямое следствие первых двух, т.к. вершина принадлежит любому центроиду <math>c</math> т.и т.т., когда c {{---}} отец вершины <math>v</math> в дереве центроидов. Т.к. вершина <math>v</math> точно принадлежит дереву <math>T</math> (свойство 2), то она лежит на каком-то пути в дереве <math>T</math>, причем все ее родители (центроиды) ее содержат. А по свойству 1 длина любого вертикального (и даже простого) пути есть <math>O(log(n))</math>, ч.т.д.* # Четвертое свойство очевидно из того, что <math>T</math> {{---}} дерево. Т.к. <math>T(u)</math> и <math>T(v)</math> {{---}} поддеревья различных вершин дерева <math>T</math>, то либо они не пересекаются, либо <math>u</math> {{---}} предок <math>v</math>, и значит <tex>T(v) \subset T(u)</tex>, либо <math>v</math> {{---}} предок <math>u</math>, и значит <tex>T(u) \subset T(v)</tex>.* # Для доказательства последнего свойства выберем в качестве вершины <math>c</math> <math>lca(u, v)</math> в дереве центроидов <math>T</math>. Покажем, что так выбранная вершина <math>c</math> удовлетворяет заявленным свойствам. То, что <tex>u, v \in T(c)</tex> {{---}} очевидно по определению <math>lca</math>, т.к. каждый предок любой вершины в дереве центроидов содержит эту вершину. Теперь докажем, что <math>c</math> лежит на пути между парой вершин <math>u, v</math>. Т.к. <math>c = lca(u, v)</math> в <math>T</math>, то из <math>c</math> нет ребра в такого сына, который содержит одновременно <math>u</math> и <math>v</math> в своем поддереве (в дереве <math>T</math>), значит после удаления <math>c</math> дерево <math>t</math> разделится на несколько поддеревьев, таких что вершины <math>u</math> и <math>v</math> окажутся в разных компонентах связности. А значит найдется такое ребро <math>(c, x)</math>, которое принадлежало пути из <math>u</math> в <math>v</math>, но после удаления <math>c</math> удалилось. Это доказывает то, что вершина <math>c</math> лежала на пути из <math>u</math> в <math>v</math>, ч.т.д.
}}
