188
правок
Изменения
Нет описания правки
__TOC__
==Идея=====Описание===Дано некоторое дерево <tex>T</tex>, алгоритм ''сжатия дерева'' (англ. ''tree-contraction algorithm''), предложенный Миллером и Райфом сжимает <tex>T</tex> в одну вершину путем применения операций <tex>\mathrm{Rake-Compress}</tex> дерево и <tex>\mathrm{{---Compress}} структура данных, которая хранит [[Дерево, эквивалентные определения|лес деревьев]] и поддерживает следующие операции</tex> в несколько раундов:
* <tex>\mathrm{Rake}</tex> {{---}} все листья дерева сжимаются к своим родителям,
* <tex>\mathrm{Compress}</tex> {{---}} выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
</tr></table>
Рассмотрим, как изменяется количество вершин в дереве после применения к нему операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>.<br>Разобьём все вершины дерева на три группы:
|proof=Из леммы 2 известно, что после каждой итерации применения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> число вершин в среднем уменьшается в константное число раз. Значит, количество итераций в среднем ограничено <tex>O(\log{n})</tex>.
}}
Для конкретного применения можно предположить, что рёбра дерева имеют вес, а вершины имеют метки.
===Пример операций===
В качестве примера сжатия дерева рассмотрим следующее взвешенное дерево:
[[Файл:RC_graph_example.png|400px|center|thumb|Исходное дерево <tex>T</tex>.]]
[[Файл:RC_graph_contraction.png|350px|right|thumb|Алгоритм сжатия дерева <tex>T</tex>.]]
На каждом раунде сжатия (перечислены сверху вниз) удаляется множество вершин с использованием операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>:
* Операция <tex>\mathrm{Rake}</tex> удаляет лист и ребро, смежное с ним и сохраняет в соседях данные {{---}} метку удалённой вершины, вес удалённого ребра и данные о сжатых на предыдущих раундах вершинах.
* Операция <tex>\mathrm{Compress}</tex> удаляет вершины, имеющую ровно одного сына, и два смежных с ней ребра. Например, для вершины <tex>v</tex> c сыном <tex>w</tex> и родителем <tex>u</tex> будут удалены рёбра <tex>(u, v)</tex> и <tex>(v, w)</tex>. После этого добавляется ребро <tex>(u, w)</tex>, а данные вершины <tex>v</tex> и удалённых рёбер сохраняются в соседние вершины {{---}} метку удалённой вершины, сохранённые данные и веса удалённых рёбер.
Например, для приведённого дерева на первом раунде сжатия применяется операция <tex>\mathrm{Rake}</tex> для вершин <tex>a</tex>, <tex>d</tex>, <tex>n</tex>, <tex>k</tex> и операция <tex>\mathrm{Compress}</tex> для <tex>g</tex> и <tex>i</tex>.<br><br>
Сжатие может быть рассмотрено как рекурсивная кластеризация дерева в один кластер. Изначально вершины и рёбра составляют базовый кластер. Операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> формируют большие кластеры из нескольких меньших кластеров.<br><br>На иллюстрации примера все кластеры (кроме базового) обозначены зелёными лепестками. Каждый кластер помечен заглавной буквой метки вершины, входящей в него. Например, кластер <tex>A</tex>, полученный после сжатия вершины <tex>a</tex> содержит вершины <tex>a</tex>, <tex>b</tex> и ребро <tex>(a, b)</tex>; сжатая вершина <tex>g</tex> создает кластер <tex>G</tex>, содержащий эту вершину и рёбра <tex>(f, g)</tex> и <tex>(g, h)</tex>. Во втором раунде, после сжатия вершины <tex>b</tex> создается кластер <tex>B</tex>, содержащий кластер <tex>A</tex> и ребро <tex>(b, c)</tex>.<br>Представление сжатого дерева в виде кластеров:
[[Файл:RC_graph_clusters.png|400px|left|thumb|Кластеризованное дерево <tex>T</tex>.]]
Определим кластер как поддерево исходного дерева, порожденное множеством вершин.
{{Определение
|definition=Для кластера <tex>C</tex> скажем, что вершина <tex>v</tex> из <tex>C</tex> называется ''граничной вершиной'', если <tex>v</tex> смежная с вершинами не из <tex>C</tex>.
}}
{{Определение
|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>. Свойством алгоритмом сжатия является то, что:
* операции <tex>\mathrm{Rake}</tex> создают кластеры со степенью <tex>1</tex>,
* операции <tex>\mathrm{Compress}</tex> создают кластеры со степенью <tex>2</tex>,
* финальный кластер имеет степень <tex>0</tex>.
Процесс сжатия исходного дерева может быть представлен в виде нового дерева, называемого <tex>\mathrm{RC-tree}</tex>.<br>Пример такого дерева для рассматриваемого исходного дерева:
[[Файл:RC_graph_tree.png|500px|center|thumb|RC-tree для дерева <tex>T</tex>.]]
==Реализация==
