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, v</math>. Выберем вершину <math>r</math>, изначально равную центроиду всего дерева <math>t</math> (т.е. корень <math>T</math>). Если из <math>r</math> в дереве <math>T</math> есть ребро в такого ребенка <math>c_r(u, v)</math>, который содержит <math>u</math> и <math>v</math> одновременно, то положим <math>r</math> равным <math>c_vc_r(u, v)</math>. Пусть в какой-то момент такого ребенка не нашлось. Значит после удаления <math>r</math> дерево <math>t</math> разделится на несколько поддеревьев, таких что вершины <math>u</math> и <math>v</math> окажутся в разных компонентах связности. А значит найдется такое ребро <math>(r, x)</math>, которое принадлежало пути из <math>u</math> в <math>v</math>, но после удаления <math>r</math> удалилось. Это доказывает то, что вершина <math>r</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>, ч.т.д.
}}
