Изменения

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

Centroid decomposition

3 байта убрано, 00:42, 15 июня 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> верно ровно одно из следующих трех утверждений:
a) <tex>T(v) \subset T(u)</tex>
b) <tex>T(u) \subset T(v)</tex>
c) <tex>T(u) \cap T(v) = \emptyset </tex>
# Простой путь между любой парой вершин <math>u, v</math> в дереве <math>t</math> содержит центроид <tex>c \in T(t)</tex>, такой что <tex>u, v \in T(c)</tex>.
|proof=
Анонимный участник

Навигация