Изменения

Перейти к: навигация, поиск

Centroid decomposition

9 байт добавлено, 16:38, 14 июня 2017
Динамическая центроидная декомпозиция (дерево центроидной декомпозиции)
* Каждая вершина дерева <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> верно ровно одно из следующих трех утверждений :
* * <tex>T(v) \subset T(u)<\tex>* * <tex>T(u) \subset T(v)<\tex>* * <tex>T(u) \cap T(v) = \emptyset <\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>, ч.т.д.
186
правок

Навигация