Центроидная декомпозиция

Центроидная декомпозиция

Введение в центроидную декомпозицию

Центроидная декомпозиция — это техника, используемая для разложения дерева на набор поддеревьев путём многократного удаления центроидных вершин.

Определение центроида

Центроид в дереве — это вершина, которая после удаления разбивает дерево на поддеревья так, что ни одно поддерево не содержит более половины общего числа вершин исходного дерева.

Формально, вершина $v$ является центроидом, если каждое поддерево, образованное удалением $v$, имеет не более $\frac{N}{2}$ вершин, где $N$ — общее число вершин в дереве.