Изменения

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

Rake-Compress деревья

114 байт убрано, 23:25, 2 мая 2018
Пример операций
==Идея==
===Описание===
Пусть дано некоторое дерево <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> {{---}} выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
   Определим кластер как поддерево исходного дерева, порожденное множеством вершин. {{Определение|definition=Для кластера <tex>C</tex> скажем, что вершина <tex>v</tex> из <tex>C</tex> называется '''граничной вершиной''', если <tex>v</tex> смежная с вершинами не из <tex>C</tex>. }}{{Определение|definition='''Граница кластера''' {{---}} множество граничных вершин кластера. }}{{Определение|definition=, а '''Степень степень кластера''' {{---}} количество граничных вершин кластера.}}
Например, для рассматриваемого дерева кластер <tex>A</tex> имеет границу <tex>\{b\}</tex> и степень <tex>1</tex>, а кластер <tex>G</tex> имеет границу <tex>\{f, g\}</tex> и степень <tex>2</tex>. При сжатии дерева все кластеры, кроме последнего, имеют степени <tex>1</tex> и <tex>2</tex>. Свойством алгоритмом сжатия является то, что:
286
правок

Навигация