Изменения

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

Rake-Compress деревья

215 байт убрано, 23:25, 2 мая 2018
Пример операций
   Определим кластер как поддерево исходного дерева, порожденное множеством вершин. {{Определение|definition=Для кластера <tex>C</tex> скажем, что вершина <tex>v</tex> из <tex>C</tex> называется '''граничной вершиной''' (англ. ''boundary vertex''), если <tex>v</tex> смежная с вершинами не из <tex>C</tex>. }}{{Определение|definition='''Граница кластера''' (англ. ''cluster boundary'') {{---}} множество граничных вершин кластера. }}{{Определение|definition=, а '''Степень степень кластера''' (англ. ''degree of cluster'') {{---}} количество граничных вершин кластера.}}
Например, для рассматриваемого дерева кластер <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
правок

Навигация