286
правок
Изменения
Нет описания правки
==Идея==
===Описание===
Пусть дано некоторое дерево <tex>T</tex>, для которого мы хотим выполнять описанные выше операции. Рассмотрим алгоритм '''сжатия дерева''' (англ. ''tree-contraction algorithm''), предложенный Миллером и Райфом. Алгоритм сжимает <tex>T</tex> в одну вершину путем применения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> в несколько раундов:
* <tex>\mathrm{Rake}</tex> {{---}} все листья дерева сжимаются к своим родителям,
* <tex>\mathrm{Compress}</tex> {{---}} выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
