186
правок
Изменения
→Свойства центроидной декомпозиции
c) <tex>T(u) \cap T(v) = \emptyset </tex>
* Любой простой Простой путь из вершины между любой парой вершин <math>v</math> в вершину <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>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>r</math>c = lca(u, изначально равную центроиду всего дерева <math>tv)</math> (т.е. корень в <math>T</math>). Если , то из <math>rc</math> в дереве <math>T</math> есть ребро нет ребра в такого ребенка <math>c_r(u, v)</math>сына, который содержит одновременно <math>u</math> и <math>v</math> одновременно, то положим в своем поддереве (в дереве <math>rT</math> равным <math>c_r(u), v)</math>. Пусть в какой-то момент такого ребенка не нашлось. Значит значит после удаления <math>rc</math> дерево <math>t</math> разделится на несколько поддеревьев, таких что вершины <math>u</math> и <math>v</math> окажутся в разных компонентах связности. А значит найдется такое ребро <math>(rc, x)</math>, которое принадлежало пути из <math>u</math> в <math>v</math>, но после удаления <math>rc</math> удалилось. Это доказывает то, что вершина <math>rc</math> лежала на пути из <math>u</math> в <math>v</math>. Также из алгоритма нахождения вершины <math>r</math > следует, что <math>r</math> есть <math>lca(u, v)</math> в дереве <math>T</math>, а значит <math>r</math> совпадает с <math>c</math>, ч.т.д.
}}
