186
правок
Изменения
→Динамическая центроидная декомпозиция (дерево центроидной декомпозиции)
* Третье свойство - прямое следствие первых двух, т.к. вершина принадлежит любому центроиду <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</math> в <math>v</math> воспользуемся свойством 4 центроидной декомпозиции.
}}
