Изменения
Нет описания правки
# Действительно, т.к. размер поддерева <math>s</math> каждой вершины <math>c</math> дереве <math>T</math> не превосходит <tex>\dfrac{|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> т.и т.т., когда <math>c</math> {{---}} отец вершины <math>v</math> в дереве центроидов. Т.к. вершина <math>v</math> точно принадлежит дереву <math>T</math> (свойство <math>2</math>), то она лежит на каком-то пути в дереве <math>T</math>, причем все ее родители (центроиды) ее содержат. А по свойству <math>1</math> длина любого вертикального (и даже простого) пути есть <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>.
