1632
правки
Изменения
м
rollbackEdits.php mass rollback
Определим кластер как поддерево исходного дерева, порожденное множеством вершин. {{Определение|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>. Свойством алгоритмом сжатия является то, что:
