==Описание==

{{Определение
|definition=
'''Граф Майхилла <tex>G</tex> (над алфавитом <tex>\Sigma</tex>)''' (англ. ''Myhill graph'') {{---}} [[Основные определения теории графов | ориентированный граф]], удовлетворяющий свойствам:
# Для каждой упорядоченной пары вершин <tex>v</tex> и <tex>u</tex> существует только одно ребро из <tex>v</tex> в <tex>u</tex>.
# Некоторые вершины обозначены начальными, а некоторые {{---}} конечными. Ребро может одновременно быть начальным и конечным.
# Вершины обозначены различными символами из конечного алфавита <tex>\Sigma</tex>, то есть мы можем обращаться к вершине по ее символу.
}}

Пусть <tex>G</tex> {{---}} граф Майхилла над алфавитом <tex>\Sigma</tex>.

Символ <tex>c \in \Sigma</tex> назовем разрешенным, если им помечена вершина, являющая одновременно начальной и конечной.

Не пустая строка <tex>c_1c_2...c_n</tex> из <tex>\Sigma^*</tex> длиной не менее двух символов, называется разрешенной, если символом <tex>c_1</tex> отмечена стартовая вершина, а символом <tex>c_n</tex> {{---}} конечная, и для всех <tex>1 \leqslant i \leqslant n - 1</tex> в <tex>G</tex> существует ребро <tex>(c_i, c_{i+1})</tex>.

Язык <tex>L(G)</tex>, распознаваемый графом Майхилла, состоит из всех разрешенных строк из <tex>\Sigma^+</tex>.

Покажем, что графы Майхилла могут быть представлены в виде автоматов.
Пусть <tex>A = (S, \Sigma, i, \delta, T)</tex> {{---}} [[Детерминированные_конечные_автоматы | ДКА]].

{{Определение
|definition= Автомат <tex>A</tex> называется '''локальным''' (англ. ''local automation''), если для любого <tex>c</tex> из <tex>\Sigma</tex> множество <tex>\{\delta(s, c) \mid s \in S\}</tex> содержит не более одного элемента.
}}

{{Определение
|definition= Автомат <tex>A</tex> называется '''стандартным локальным''' автоматом (англ. ''standard local automation''), если в нем нет перехода в начальное состояние.
}}

Таким образом, автомат является локальным, если для каждого <tex>c</tex> из <tex>\Sigma</tex> нет переходов, отмеченных <tex>c</tex>, или если все они ведут в одно состояние.

Покажем, что граф Майхилла может быть преобразован в стандартный локальный автомат таким образом, что распознаваемый им язык не изменится.

{{Теорема
|id=th1
|statement=
Язык распознается графом Майхилла тогда и только тогда, когда он распознается стандартным локальным автоматом, стартовое состояние которого не является терминальным.
|proof=
<tex>\Rightarrow</tex>

Пусть <tex>G</tex> {{---}} граф Майхилла.
Построим автомат <tex>A</tex> следующим образом:
* Добавим вершину <tex>\Diamond</tex> в <tex>G</tex> с ребрами от <tex>\Diamond</tex> к каждой стартовой вершине <tex>G</tex>; отметим вершину <tex>\Diamond</tex> как стартовое состояние.
* Отметим конечные вершины как терминальные состояния.
* Отметим каждое ребро результирующего ориентированного графа символом, стоящим в вершине, на которою оно указывает.
Переходы преобразуются следующим образом: [[Файл:Myhill1.png|150px]]

По построению стартовое состояние не является терминальным.

Покажем, что полученный автомат конечен.
Ребра, выходящие из стартового состояния обозначены различными символами, потому что они указывают на вершины, которые, по свойству 3, были отмечены различными символами в исходном автомате.
Если мы рассмотрим любое другое состояние <tex>s</tex>, то два перехода из <tex>s</tex> могут иметь одинаковые метки только в том случае, если в <tex>G</tex> оба ориентированных ребра идут в одну и ту же вершину. Но этого не может быть по свойтсву 1.
То есть <tex>A</tex> {{---}} [[Детерминированные_конечные_автоматы | ДКА]]. По построению он является стандартным локальным автоматом.
Теперь просто проверить, что <tex>L(A) = L(G)</tex>.

<tex>\Leftarrow</tex>

Пусть <tex>A = (S, \Sigma, i, \delta, T)</tex> {{---}} стандартный локальный автомат, стартовое состояние которого не является терминальным.
Построим по нему граф Майхилла следующим образом:
* Отметим все состояния <tex>A</tex>, кроме стартового, <tex>input</tex> символами, стоящими на ребрах, входящих в эти состояния.
* Сотрем все метки на ребрах <tex>A</tex>.
* Отметим все состояния <tex>s</tex> как начальные вершины, если существует переход из <tex>i</tex> в <tex>s</tex>
* Отметим все терминальные состояния как конечные вершины.
* Удалим вершину <tex>i</tex> и все ребра, исходящие из нее.
Назовем полученный граф <tex>G</tex> {{---}} он будет графом Майхилла по построению. Легко проверить, что <tex>L(G) = L(A)</tex>.
}}

==Пример==
{| cellpadding="3" style="margin-left: auto; margin-right: auto;"
| [[Файл:Myhill2.png|300px|thumb|right|Рисунок 1]]
| [[Файл:Myhill3.png|200px|thumb|right|Рисунок 2]]
|}

Граф, изображенный на рисунке 1 может быть использован для распознавания строк над алфавитом <tex>\Sigma = \{a, b\}</tex>. По определению, язык, распознаваемый данным графом, состоит из непустых строк, начинающихся и заканчивающихся на <tex>a</tex>.

Рассмотрим детерменированный конечный автомат, представленный на рисунке 2.
Не сложно проверить, что он распознает тот же язык, что и граф на рисунке 1.

==Локальный язык==
Рассмотрим язык, распознаваемый стандартным локальным автоматом.
{{Определение
|definition=Язык <tex>L \subseteq A^*</tex> называется '''локальным языком''' (англ. ''local language''), если <tex>L \setminus \varepsilon</tex> может быть описан следующим образом: 
<tex>\exists P, S \subseteq A, N \subseteq A^2: L \setminus \varepsilon = (P A^* \cap A^* S) \setminus A^* N A^*</tex>.
}}

Другими словами, непустое слово принадлежит локальному языку, если оно начинается с символа из <tex>P</tex>, оканчивается на символ из <tex>S</tex> и не содержит пары символов из множества <tex>N</tex>.

Пусть <tex>L = (P A^* \cap A^* S) \setminus A^* N A^*</tex> {{---}} локальный язык. Определим автомат <tex>\mathcal{A}</tex> следующим образом:
* набор состояний <tex>Q = A \cup \{ \varepsilon \}</tex>,
* начальное состояние <tex>\varepsilon</tex>,
* терминальные состояния <tex>S</tex>,
* <tex>\delta(\varepsilon, a) = a</tex> если <tex>a \in P</tex> и <tex>\delta(a, b) = b</tex> если <tex>ab \not\in N</tex>.
Если <tex>L</tex> содержит пустую строку, то множество терминальных состояний <tex>\mathcal{A}</tex> {{---}} <tex>S \cup \{ \varepsilon \}</tex>.

{{Утверждение
|statement=Автомат <tex>\mathcal{A}</tex> – стандартный локальный автомат, распознающий <tex>L</tex>.
}}

{{Утверждение
|statement=Язык, распознаваемый локальным автоматом, является локальным.
}}

==Алгоритм Глушкова==
===Описание===
Дано регулярное выражение <tex>e</tex>. Алгоритм Глушкова строит недетерминированный автомат, который распознает язык <tex>L(e)</tex>, распознаваемый <tex>e</tex>. Построение происходит в несколько шагов:
# Линеаризация регулярного выражения. Каждый символ из алфавита, содержащийся в регулярном выражении, переименовывается таким образом, что каждый символ содержится в новом регулярном выражении не более одного раза. Пусть <tex>A</tex> {{---}} исходный алфавит, <tex>B</tex> {{---}} новый алфавит.
# Вычисление множеств <tex>P(e'), S(e'), N(e')</tex>, где <tex>e'</tex> {{---}} линеаризованное регулярное выражение. <tex>P(e')</tex> {{---}} множество символов, с которых начинается слово из <tex>L(e')</tex>. <tex>S(e')</tex> {{---}} множество символов, на которые оканчивается слово из <tex>L(e')</tex> и <tex>N(e')</tex> {{---}} множество пар символов, которые встречаются в слове из <tex>L(e')</tex>. Более формально: <tex>P(e')=\{a\in B\mid aB^*\cap L(e')\ne\emptyset\}</tex>, <tex>S(e')=\{a\in B\mid B^*a\cap L(e')\ne\emptyset\}</tex>, <tex>N(e')=\{u\in B^2\mid B^*uB^*\cap L(e')\ne\emptyset\}</tex>.
# Вычисление множества <tex>\Lambda(e')</tex> такого что <tex>\Lambda(e')=\{\varepsilon\}\cap L(e')</tex>.
# Вычисление локального языка с заданными множествами и построение по нему автомата.
# Делинеаризация, переименование каждого символа из <tex>B</tex> в соответствующий ему символ из <tex>A</tex>.
===Пример работы===
[[Файл:Glushkov_lin_automata.jpg|frame|right|Автомат, построенный в ходе работы алгоритма Глушкова]]

Рассмотрим регулярное выражение <tex>e = (a(ab)^*)^* + (ba)^*</tex>.

1. Линеаризуем его путем добавления индекса к каждому символу:
:<tex>e'=(a_1(a_2b_3)^*)^*+(b_4a_5)^*</tex>.

2. Составим множества <tex>P</tex>, <tex>S</tex>, и <tex>N</tex>:
:<tex>P(e')=\{a_1,b_4\}</tex>, 
:<tex>S(e')=\{a_1,b_3,a_5\}</tex>, 
:<tex>N(e')=\{a_1a_2, a_1a_1, a_2b_3, b_3a_1,b_3a_2,b_4a_5,a_5b_4\}</tex>.

Так как пустое слово принадлежит языку, то <math>\Lambda(e')=\{\varepsilon\}</math>.

3. Автомат локального языка <tex>L'=P'B^*\cap B^*S'\setminus B^*(B^2\setminus N')B^*</tex> содержит начальное состояние, обозначенное как <tex>1</tex>, и состояния для каждого из пяти символов алфавита <tex>B=\{a_1, a_2, b_3, b_4, a_5\}</tex>. 
В построенном автомате существует переход из <tex>1</tex> (соответствующего пустой строке) в два состояния из <tex>P'</tex>, переход из <tex>a</tex> в <tex>b</tex> если <tex>ab \in N'</tex>, три состояния <math>S'</math> терминальные (как и состояние <tex>1</tex>).

4. Получим автомат для <tex>L(e)</tex>, удалив индексы, добавленные на первом этапе.

== См. также ==
* [[Контексты и синтаксические моноиды]]

== Источники информации ==
* Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} М.:Издательский дом «Вильямс», 2002.
* Mark V. Lawson Finite Automata, стр 132.

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Файл:Glushkov lin automata.jpg

2017-01-13T22:57:54Z

Kiryukhinv: загружена новая версия «Файл:Glushkov lin automata.jpg»

Файл:Glushkov lin automata.jpg

2017-01-13T22:51:53Z

Kiryukhinv: загружена новая версия «Файл:Glushkov lin automata.jpg»

2017-01-13T21:24:35Z

Kiryukhinv:

2016-10-28T21:37:00Z

Kiryukhinv:

{{Задача
|definition =
Пусть дан [[Детерминированные_конечные_автоматы|автомат]] <tex>\mathcal{A}</tex>. Требуется построить автомат <tex>\mathcal{A}_{min}</tex> с наименьшим количеством состояний, распознающий тот же язык, что и <tex>\mathcal{A}</tex>.
}}

==Описание==
Пусть <tex>q</tex> {{---}} состояние автомата <tex>\mathcal{A} = \langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle</tex>.
{{Определение
|definition=
'''Правым языком''' (англ. ''right language'') {{---}} называется язык <tex>L_d(q)</tex>, принимаемый автоматом <tex>\mathcal{A}_{d}(q) = \langle \Sigma , Q , q , T , \delta \rangle</tex>, полученным из <tex>\mathcal{A}</tex> путём добавления уникального начального состояния <tex>q</tex>.
}}
{{Определение
|definition=
'''Левым языком''' (англ. ''left language'') {{---}} называется язык <tex>L_g(q)</tex>, принимаемый автоматом <tex>\mathcal{A}_{g}(q) = \langle \Sigma , Q , q , T , \delta \rangle</tex>, полученным из <tex>\mathcal{A}</tex> путём добавления уникального терминального состояния <tex>q</tex>.
}}

{{Утверждение
|about=1
|statement=
Автомат является детерминированным тогда и только тогда, когда левые языки его состояний попарно не пересекаются.
}}

{{Определение
|definition=
'''Обратное слово''' <tex>r(u)</tex> для слова <tex>u</tex> определяется следующим образом: <tex>r(\varepsilon) = \varepsilon</tex> и если <tex>u = u_1 u_2 u_3 \dotsc u_p</tex>, тогда <tex>r(u) = v_1 v_2 v_3 \dotsc v_p</tex>, где <tex>v_i = u_{p - i + 1}</tex>.
}}

{{Определение
|definition=
'''Обратный язык''' для языка <tex>L</tex> {{---}} язык <tex>r(L) = \{ u \mid r(u) \in L \}</tex>.
}}

{{Определение
|definition=
'''Обратный автомат''' для автомата <tex>\mathcal{A} = \langle \Sigma , Q , S , T , \delta \rangle</tex> {{---}} автомат <tex>r(\mathcal{A}) = \langle \Sigma , Q , T , I , r(\delta) \rangle</tex>, полученный из <tex>\mathcal{A}</tex> сменой местами начальных и конечных состояний и сменой направлений переходов.
}}

{{Утверждение
|about=2
|statement=
Если <tex>\mathcal{A}</tex> распознает язык <tex>L</tex>, то <tex>r(\mathcal{A})</tex> распознает <tex>r(L)</tex>.
}}

{{Утверждение
|about=3
|statement=
Если левый язык состояния <tex>q</tex> в <tex>\mathcal{A}</tex> {{---}} <tex>L_g(q)</tex>, тогда его левый язык в <tex>r(A)</tex> {{---}} <tex>L_d(q)</tex>. Аналогично для правого языка <tex>q</tex>.
}}

Пусть <tex>\mathcal{A} = \langle \Sigma , Q , I , T , \delta \rangle</tex> {{---}} [[Недетерминированные_конечные_автоматы|НКА]]. Тогда детерминированный автомат <tex>d(\mathcal{A}) = \langle \Sigma , Q' , \{ i' \} , T' , \delta' \rangle</tex> определяется следующим образом:
* Детерминированному состоянию соответствует множество недетерминированных состояний: для каждого <tex>q' \in Q'</tex> имеем <tex>q' \subseteq Q</tex>,
* Начальное состояние в <tex>d(\mathcal{A})</tex> {{---}} множество из <tex>I</tex> начальных состояний автомата <tex>\mathcal{A}</tex>,
* Состояние в детерминированном автомате является терминальным тогда и только тогда, когда оно содержится хотя бы в одном недетерминированном состоянии,
* Пусть <tex>q'</tex> {{---}} состояние детерминированного автомата и <tex>a</tex> – символ из <tex>\Sigma</tex>. Если переход из <tex>q'</tex> по символу <tex>a</tex> определен, тогда, по построению: <tex>\delta'(q', a) = \bigcup\limits_{q \in q'}{ \delta(q, a)}</tex>.

{{Утверждение
|about=4
|statement=
Правый язык состояния <tex>q'</tex> <tex>d(\mathcal{A})</tex> эквивалентен объединению правых языков состояний <tex>q \mathcal{A}</tex>, принадлежащих множеству <tex>q'</tex>.
}}

==Алгоритм==
===Описание===
Алгоритм минимизации конечных [[Детерминированные конечные автоматы|автоматов]] Бржозовского (Janusz A. (John) Brzozowski) выделяется, по крайней мере, следующими качествами:

* Он элегантен и весьма оригинален.
* Он эффективен.
* Он работает даже с [[Недетерминированные конечные автоматы|недетерминированными конечными автоматами]].

Обладая обычными процедурами обращения <tex>\operatorname{rev}</tex> и детерминизации <tex>\operatorname{det}</tex> конечного [[Детерминированные конечные автоматы|автомата]], мы, с помощью идеи Бржозовского, можем немедленно приступить к минимизации заданного [[Детерминированные конечные автоматы|автомата]]. Для этого надо дважды провести его через обе вышеуказанные процедуры:

<tex>mFA = \operatorname {det}(\operatorname{rev}(\operatorname{det}(\operatorname{rev}(FA))))</tex>, где

* <tex>FA</tex> это исходный КА,
* <tex>\operatorname{rev}</tex> это процедура обращения КА,
* <tex>\operatorname{det}</tex> это процедура детерминизации КА,
* <tex>mFA</tex> это минимизированный КА.

===Корректность===
Корректность алгоритма доказана в работе<ref>[http://www.researchgate.net/publication/255626373_Split_and_join_for_minimizing__Brzozowski's_algorithm Split and join for minimizing : Brzozowski's algorithm]</ref>

==Пример работы==
# Исходный [[Недетерминированные конечные автоматы|НКА]] (<tex>FA</tex>): [[Файл:Fa.png|Исходный НКА]]
# Первый шаг алгоритма (<tex>\operatorname{rev}(FA)</tex>): [[Файл:Rfa.png|Первый шаг]]
# Второй шаг алгоритма (<tex>\operatorname{det}(\operatorname{rev}(FA))</tex>): [[Файл:Drfa.png|Второй шаг]] <tex>\operatorname{det}</tex> переименовывает состояния, после этого <tex>0</tex> всегда является начальным состоянием
# Третий шаг алгоритма (<tex>\operatorname{rev}(\operatorname{det}(\operatorname{rev}(FA)))</tex>): [[Файл:Rdrfa.png|Третий шаг]] После выполнения этого шага алгоритма оба состояния <tex>2</tex> и <tex>3</tex> являются начальными.
# Заключительный шаг алгоритма (<tex>\operatorname{det}(\operatorname{rev}(\operatorname{det}(\operatorname{rev}(FA))))</tex>): [[Файл:Drdrfa.png|Заключительный шаг]]

== Заключение ==
Самым эффективным алгоритмом минимизации принято считать [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))|алгоритм Хопкрофта]], который, как и прочие традиционные алгоритмы, работает только с [[Детерминированные_конечные_автоматы|ДКА]]. Его асимптотическое время выполнения зависит от логарифма исходных данных. С другой стороны очевидно, что алгоритм Бржозовского в худшем случае будет обладать экспоненциальным временем выполнения, ведь этого требует процедура детерминизации, выполняемая дважды. На практике же наблюдается парадокс, алгоритм Бржозовского во многих случаях опережает прочие подходы к минимизации, включая и [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))|алгоритм Хопкрофта]]. В работе<ref>[http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=A511A421C93DF66BDCC32A0E133D1F99?doi=10.1.1.59.8276&rep=rep1&type=pdf Deian Tabakov, Moshe Y. Vardi. Experimental evaluation of classical automata constructions]</ref>, сравнивающей оба алгоритма, показано, что алгоритм Бржозовского оказывается эффективнее [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))|алгоритма Хопкрофта]] для автоматов с большим числом переходов.

== См. также ==
*[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]
*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]

==Примечания==
<references/>
==Источники информации==
* [http://sovietov.com/txt/minfa/minfa.html Алгоритм Бржозовского для минимизации конечного автомата]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Алгоритм Бржозовского

2016-10-16T15:34:08Z

Kiryukhinv:

Алгоритм Бржозовского

2016-10-16T15:08:04Z

Kiryukhinv:

Rake-Compress деревья

2016-05-22T17:33:42Z

Kiryukhinv:

Задача, которая решается с помощью [[Link-Cut Tree|динамических деревьев]], формулируется следующим образом. Необходимо поддерживать лес деревьев и выполнять на нем следующие операции:
* <tex>\mathrm{link(u, v)}</tex> {{---}} добавить ребро <tex>(u, v)</tex>. Вершина <tex>u</tex> должна быть корнем некоторого дерева. Вершины <tex>u</tex> и <tex>v</tex> должны находиться в разных деревьях,
* <tex>\mathrm{cut(u, v)}</tex> {{---}} удалить ребро <tex>(u, v)</tex>. Ребро <tex>(u, v)</tex> должно присутствовать в графе,
* <tex>\mathrm{query()}</tex> {{---}} некоторый запрос относительно структуры дерева.

__TOC__
==Идея==
===Описание===
Пусть дано некоторое дерево <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> {{---}} выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
<table align="center"><tr>
<td>[[Файл:Rctree-rake.png|x180px|thumb|Операция <tex>\mathrm{Rake}</tex>]]</td>
<td>[[Файл:Rctree-compress.png|x180px|thumb|Операция <tex>\mathrm{Compress}</tex>]]</td>
</tr></table>

Сжатие дерева требует линейного времени и логарифмическое число раундов. 
Для выбора вершин, которые будут удалены во время операции <tex>\mathrm{Compress}</tex>, применяется следующий метод: для каждой вершины генерируется рандомный бит и вершина добавляется в множество удаляемых только в том случае, когда она имеет одного ребёнка, бит для неё равен <tex>0</tex>, а для родителя и ребёнка равен <tex>1</tex>. 
Рассмотрим, как изменяется количество вершин в дереве после применения к нему операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>. Разобьём все вершины дерева на три группы:
* <tex>T_0</tex> {{---}} входящая степень равна нулю,
* <tex>T_1</tex> {{---}} входящая степень равна одному,
* <tex>T_2</tex> {{---}} входящая степень больше одного.

{{Лемма
|about=1
|statement=<tex>T_2 \leqslant T_0 - 1</tex>.
|proof=
Докажем по индукции по высоте дерева. 
* '''База
*: Для дерева из одной вершины утверждение верно.
* '''Переход
*: Пусть утверждение доказано для деревьев высоты меньше <tex>h</tex>. Докажем для дерева высоты ровно <tex>h</tex>. Рассмотрим степень корня: 
*:: Если корень имеет ровно одного ребенка, то переходим к случаю дерева высоты <tex>h - 1</tex>. Если у дерева несколько поддеревьев, то имеем: <tex>T_2 = 1 + \sum\limits_{u \in *: children(root)}T_2(u) \leqslant 1 + \sum\limits_{u \in children(root)}(T_0(u) - 1)</tex>  <tex> \leqslant -1 + \sum\limits_{u \in children}T_0(u) \leqslant -1 + T_0 = T_0 - 1</tex>.
}}
Заметим, что для леса деревьев лемма также справедлива.

{{Лемма
|about=2
|statement=После применения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> к лесу, математическое ожидание количества вершин в нём не превосходит <tex>\dfrac{7}{8}</tex> от их исходного числа.
|proof=Все листья будут удалены после операции <tex>\mathrm{Rake}</tex>, а каждая вершина, у которой ровно один сын, будет удалена с вероятностью <tex>\dfrac{1}{8}</tex> после операции <tex>\mathrm{Compress}</tex> (так как мы рассматриваем три бита при выборе вершин и добавляем вершину в множество удаляемых только когда эти биты для родителя, вершины и ребёнка соответственно равны <tex>1</tex>, <tex>0</tex> и <tex>1</tex>). 
Таким образом математическое ожидание количества удаленных вершин <tex>\mathrm{deleted} = T_0 + \dfrac{T_1}{8}</tex>. Из предыдущей леммы получаем: 
<tex>\mathrm{deleted} = \dfrac{1}{2} (T_0 + T_2) + \dfrac{1}{8} T_1 \geqslant \dfrac{1}{8} (T_0 + T_1 + T_2)</tex>.
}}

{{Теорема
|statement=Математическое ожидание количества операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>, которые будут выполнены до полного сжатия дерева, равно <tex>O(\log{n})</tex>, где <tex>n</tex> {{---}} общее количество вершин.
|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>. 
Сжатие может быть рассмотрено как рекурсивная кластеризация дерева в один '''кластер'''. Изначально вершины и рёбра составляют базовый кластер. Операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> формируют большие кластеры из нескольких меньших кластеров. На иллюстрации примера все кластеры (кроме базового) обозначены зелёными лепестками. Каждый кластер помечен заглавной буквой метки вершины, входящей в него. Например, кластер <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>. Представление сжатого дерева в виде кластеров:
[[Файл: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='''Граница кластера''' {{---}} множество граничных вершин кластера.
}}
{{Определение
|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>. Пример такого дерева для рассматриваемого исходного дерева:
[[Файл:RC_graph_tree.png|500px|center|thumb|RC-tree для дерева <tex>T</tex>.]]

Поскольку матожидание количества раундов {{---}} логарифм, то такое дерево будет сбалансированным. 
<tex>\mathrm{RC}</tex> дерево можно использовать для ответа на динамические запросы для статического дерева. Для этого в <tex>\mathrm{RC}</tex> дереве сохраним требуемую информацию (необходимо модифицировать для пересчёта информации операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>) и используем обход для ответа на запросы. Поскольку дерево с большой вероятностью является сбалансированным, обход дерева также можно осуществить за логарифм. 
Для динамических деревьев, например, если доступны операции добавления/удаления ребра (операции <tex>\mathrm{link}</tex> и <tex>\mathrm{cut}</tex>), нужно эффективно перестраивать отдельные кластеры, пересчитывая данные. Для этого можно обновлять данные начиная с листа дерева, соответствующего обновляемой вершине в исходном дереве, и подниматься вверх.

==Реализация==
===Хранение===
Для того, чтобы отвечать на запросы относительно структуры леса необходимо сохранить информацию о том, как происходил процесс сжатия леса. Для этого будем хранить таблицу, в каждой строке которой записана информация о структуре леса после выполнения операций. Каждая клетка таблицы будет хранить информацию о вершине после выполнения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>. Из информации будем сохранять родителя вершины, множество детей и метку, сжата ли вершина. 
Пример таблицы для следующей последовательности операций:
[[Файл:RC_tree_example.png|x200px|thumb|Пример выполнения операций.]]
{| class="wikitable"
|-
! Шаг
! align="center" | Операция
! <tex>1</tex>
! <tex>2</tex>
! <tex>3</tex>
! <tex>4</tex>
|-
| align="center" | 4
| align="center" | <tex>\mathrm{Rake}</tex>
| Родитель: {{---}} Дети: <tex>\emptyset</tex>
| align="center" | {{---}}
| align="center" | {{---}}
| align="center" | {{---}}
|-
| align="center" | 3
| align="center" | <tex>\mathrm{Compress}</tex>
| Родитель: {{---}} Дети: <tex>\{3\}</tex>
| align="center" | {{---}}
| Родитель: <tex>1</tex> Дети: <tex>\emptyset</tex>
| align="center" | {{---}}
|-
| align="center" | 2
| align="center" | <tex>\mathrm{Rake}</tex>
| Родитель: {{---}} Дети: <tex>\{2\}</tex>
| Родитель: <tex>1</tex> Дети: <tex>\{3\}</tex>
| Родитель: <tex>2</tex> Дети: <tex>\emptyset</tex>
| align="center" | {{---}}
|-
| align="center" | 1
|
| Родитель: {{---}} Дети: <tex>\{2\}</tex>
| Родитель: <tex>1</tex> Дети: <tex>\{3\}</tex>
| Родитель: <tex>2</tex> Дети: <tex>\{4\}</tex>
| Родитель: <tex>3</tex> Дети: <tex>\emptyset</tex>
|}
 
Для того, чтобы выбирать множество вершин для применения операции <tex>\mathrm{Compress}</tex> будем использовать следующий метод: для каждой вершины с помощью генератора псевдослучайных чисел выберем случайный бит. Вершина добавляется в множество, если у нее ровно один ребенок, она не является корнем и биты, которые были сгенерированы для нее, ребенка и родителя равны <tex>0</tex>, <tex>1</tex> и <tex>1</tex> соответственно.

Рассмотрим более подробно, как необходимо хранить клетки таблицы <tex>\mathrm{Rake-Compress}</tex> дерева. Для вершины необходимо сохранить ее родителя, а также множество детей. Для того, чтобы обрабатывать каждую клетку таблицы за <tex>O(\log{n})</tex>, нужно производить операции с множеством детей за <tex>O(1)</tex>. Рассмотрим, в каких случаях можно сжать вершину:
* если детей у вершины больше одного, то ее точно нельзя сжать,
* если у неё нет детей, то ее можно сжать только во время операции <tex>\mathrm{Rake}</tex>
* если у вершины один ребёнок, то её возможно сжать во время операции <tex>\mathrm{Compress}</tex>.
Чтобы определить, можно ли применить операцию <tex>\mathrm{Compress}</tex> к вершине, в том случае, когда у нее один ребёнок, нужно узнать, какой бит был сгенерирован на текущей итерации для ребёнка (один из трёх битов, генерируемых при операции <tex>\mathrm{Compress}</tex>). Для этого необходимо знать номер вершины-ребёнка. Значит, нам нужно определять, какие элементы находятся в множестве детей только в том случае, когда размер множества равен <tex>1</tex>. Поэтому, всю информацию о множестве можно хранить с помощью двух величин {{---}} хранить количество элементов в множестве и сумму их номеров. Поддерживая сумму номеров детей и их количество, можно эффективно узнавать номер вершины-ребёнка, когда это необходимо. Данная оптимизация позволяет за <tex>O(1)</tex> получать номер ребёнка и за <tex>O(1)</tex> обновлять множество детей. 
Если вершина является корнем, то в качестве ее родителя будем хранить ее номер. Кроме того необходимо хранить изменения, которые произойдут с клеткой при переходе к следующему слою: будем хранить, кто должен стать новым родителем, на сколько изменится количество детей, а также как изменится сумма их номеров. Все это необходимо для того, чтобы обрабатывать каждую изменившуюся клетку за <tex>O(1)</tex>. 

Псевдокод хранения клетки таблицы:
* <tex>\mathrm{id}</tex> {{---}} номер вершины,
* <tex>\mathrm{parent}</tex> {{---}} родитель вершины,
* <tex>\mathrm{cntChild}</tex> {{---}} количество детей вершины,
* <tex>\mathrm{sumChild}</tex> {{---}} сумма номеров детей,
* <tex>\mathrm{newParent}</tex> {{---}} новый родитель вершины после изменений,
* <tex>\mathrm{diffCntChild}</tex> и <tex>\mathrm{diffSumChild}</tex> {{---}} изменения, произведенные с полями <tex>\mathrm{cntChild}</tex> и <tex>\mathrm{sumChild}</tex> соответственно.

'''struct''' Cell''':'''
'''int''' id, parent, cntChild, sumChild
'''int''' newParent, diffCntChild, diffSumChild

'''func''' applyChanges()''':'''
parent = newParent
sumChild += diffSumChild
cntChild += diffCntChild
diffCntChild = diffSumChild = 0

'''func''' addChild(v: '''int''')''':'''
diffCntChild++
diffSumChild += v

'''func''' removeChild(v: '''int''')''':'''
diffCntChild--
diffSumChild -= v

Для хранения <tex>\mathrm{Rake-Compress}</tex> дерева будем использовать следующие данные:
* <tex>\mathrm{cells[]}</tex> {{---}} список клеток, которые ей соответствуют, для каждой вершины,
* <tex>\mathrm{rand}</tex> {{---}} генератор псевдослучайных чисел,
* <tex>\mathrm{time}</tex> {{---}} счётчик количества примененных операций по изменению структуры леса,
* <tex>\mathrm{lastUpdateTime[]}</tex> {{---}} массив, в котором для каждой вершины запишем номер последней операции, при обработки которой была изменена хотя бы одна клетка, которая соответствуют вершине: это позволит эффективно узнавать, была ли вершина уже помечена как поменявшаяся или нет.

'''struct''' RCTree(n: '''int''')''':'''
'''RndGen''' rand = RandBitsGenerator()
'''int''' time = 0
'''for''' i = 0 '''to''' n
lastUpdateTime[i] = 0
cells[i] = []

Кроме запросов о структуре леса, <tex>\mathrm{Rake-Compress}</tex> деревья можно использовать для подсчета значений некоторых функций. Например, каждой вершине можно сопоставить некоторое значение и узнавать, чему равна сумма значений всех вершин, которые находятся в поддереве.
Для этого в клетках таблицы <tex>\mathrm{Rake-Compress}</tex> дерева необходимо хранить не только состояние вершины, но и значение функции, посчитанной на части дерева, которое уже было сжато в вершину. Если функция является аддитивной, то ее пересчет аналогичен пересчету множества детей вершины. Так, если некоторая вершина сжимается к родителю, то в соответствующей родителю клетке необходимо обновить значение функции. При добавлении и удалении ребер необходимо в изменившихся клетках пересчитывать значение функции.

===Построение===
Рассмотрим, как работает алгоритм построения <tex>\mathrm{Rake-Compress}</tex> дерева. Будем строить таблицу по строкам. В каждый момент будем хранить множество вершин, которые еще не были сжаты, и перестраивать следующий слой. Также будем делать операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> одновременно. Чтобы определить, нужно ли сжимать вершину, воспользуемся следующим алгоритмом:
'''bool''' shouldRemoveVertex(c: '''Cell''', rand, layer: '''int''')''':'''
'''if''' c.cntChild == 0
'''return''' ''true''
'''if''' c.cntChild > 1 '''or''' c.parent == c.id
'''return''' ''false''
'''if''' getCellForVertex(c.sumChild).cntChild == 0
'''return''' ''false''
'''if''' rand.getBit(c.id, layer) == 0 '''and''' rand.getBit(c.sumChild, layer) == 1 '''and''' rand.getBit(c.parent, layer) == 1:
'''return''' ''true''
'''return''' ''false''

Таким образом, алгоритм построения дерева выглядит следующим образом:
'''func''' build(parent: '''int[n]''')''':'''
alive = <tex>\{0 \dots n - 1\}</tex>
'''int''' layer = 0
'''for''' i = 0 '''to''' n // заполним таблицу вершинами изначального дерева
cells[i].add(Cell(parent[i]))
'''while''' <tex>\mathrm{alive} \neq \emptyset</tex>
nextAlive = <tex>\emptyset</tex>
'''for''' <tex>v \in \mathrm{alive}</tex>
'''Cell''' c = getCellForVertex(v) // получить клетку таблицы, соответствующую вершине
'''if''' shouldRemoveVertex(c, rand, layer)
'''if''' c.cntChild == 1
getCellForVertex(c.sumChild).newParent = c.parent
getCellForVertex(c.parent).addChild(c.sumChild)
'''if''' c.parent <tex>\neq</tex> v
getCellForVertex(c.parent).remove(v)
'''else'''
nextAlive.add(v)
alive = nextAlive
'''for''' <tex>v \in \mathrm{alive}</tex>
'''Cell''' newCell = getCellForVertex(v).clone().applyChanges()
cells[v].add(newCell)
layer++
===Операции удаления и добавления ребра===
Как только некоторая вершина помечается как изменившаяся, отменим её действие на таблицу:
# Найдем момент времени, когда вершина сжимается к родителю.
# Рассмотрим, какие вершины поменяются при сжатии данной: это ее родитель (если он есть), а также сын (если он есть). Для каждой из этих вершин поменяем значения изменений, которые необходимо применить к состоянию.
# Пометим, что эти вершины поменялись на этом слое. Для этого на каждом слое будем хранить список вершин, которые на нем поменялись. А перед тем как обрабатывать очередной слой будем добавлять в множество изменившихся вершин вершины из соответствующего списка.
# Кроме удаления эффекта от изменившихся вершин также необходимо и добавить правильный эффект. Для этого будем для каждой из изменившихся вершин определять, как ее состояние меняется при переходе к следующему слою. Если вершина сжимается к ее родителю, то пометим родителя и ребенка (если он есть) и поменяем изменение, которое хранится в соответствующих клетках. А для пересчета состояния клеток воспользуемся значениями изменений, которые сохранены в клетках. 
Рассмотрим, что происходит с таблицей при изменении одного ребра. Основная идея заключается в том, чтобы научится пересчитывать все изменения таблицы за время пропорциональное их количеству. Для этого будем эффективно поддерживать множество изменившихся клеток. В момент, когда вершина помечается, как изменившаяся, найдем, как она влияет на таблицу и отменим это влияние. Для начала необходимо найти момент времени, когда вершина сжимается. В этот момент она влияет на не более чем две вершины. Изменим значения <tex>\mathrm{cntChild}</tex>, <tex>\mathrm{sumChild}</tex> и <tex>\mathrm{newParent}</tex> нужным образом. Также необходимо добавить эти вершины в множество изменившихся (в момент, когда будет обработан соответствующий слой). Поэтому, для каждого слоя еще будем хранить список вершин, которые должны быть помечены перед обработкой слоя. Алгоритм обновления дерева:
'''func''' changeTree(<tex>(u, v)</tex>: '''Edge''')''':'''
time = time + 1
affected = <tex>\emptyset</tex>
markAffected(u) // пусть из дерева было удалено ребро <tex>(u, v)</tex>
markAffected(v)
cells[u].parent = u
cells[v].cntChild--
cells[v].sumChild -= u
'''int''' layer = 0
'''while''' <tex>\mathrm{affected} \neq \emptyset</tex>
'''for''' <tex>v \in \mathrm{affectedOnLayer}</tex>
markAffected(v)
'''for''' <tex>v \in \mathrm{affected}</tex>
'''Cell''' c = getCellForVertex(v)
'''if''' shouldRemoveVertex(v)
cells[v].size = layer + 1
'''if''' c.cntChild == 1
getCellForVertex(c.sumChild).newParent = c.parent
getCellForVertex(c.parent).addChild(c.sumChild)
markAffected(c.sumChild)
'''if''' c.parent <tex>\neq</tex> v
getCellForVertex(c.parent).removeChild(v)
markAffected(c.parent)
affected.remove(v)
'''for''' <tex>v \in \mathrm{affected}</tex>
'''Cell''' newCell = getCellForVertex(v).clone().applyChanges()
cells[v][layer + 1] = newCell
layer++

'''func''' markAffected(v: '''int''')''':''' // пометить вершину как изменившуюся
'''if''' lastUpdateTime[v] == time
'''return''' // вершина уже помечена
lastUpdateTime[v] = time
affected.add(v)
removeEffectOfVertex(v)

'''func''' removeEffectOfVertex(v: '''int''')''':''' // удалить отметку о том, что вершина была помечена изменившийся
'''int''' layer = cells[v].size
'''Cell''' c = cells[v][layer]
'''if''' c.parent == v
'''return'''
cells[c].parent.removeChild(v)
'''if''' c.cntChild == 1
cells[c.parent].addChild(c.sumChild)
cells[c.sumChild].newParent = v

==Сравнение с Link-Cut Tree==
Для Link-Cut деревьев (основанных на [[Splay-дерево|splay-деревьях]]), как и для <tex>\mathrm{Rake-Compress}</tex> деревьев, время работы операций <tex>\mathrm{link}</tex> и <tex>\mathrm{cut}</tex> {{---}} <tex>O(\log{n})</tex>. В реальности <tex>\mathrm{RC}</tex> деревья оказываются медленнее, чем <tex>\mathrm{LC}</tex> деревья. 
Отличительной особенностью <tex>\mathrm{RC}</tex> деревьев является возможность параллельного построения: операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> можно выполнять параллельно для всех вершин. Если предположить, что множество детей можно пересчитывать за <tex>O(1)</tex>, то <tex>\mathrm{Rake-Compress}</tex> дерево можно построить за <tex>O(\log{n})</tex> в модели PRAM<ref>[https://en.wikipedia.org/wiki/Parallel_random-access_machine Wikipedia {{---}} Parallel random-access machine]</ref> в случае наличия <tex>\Omega(n)</tex> процессоров. 
Кроме этого, <tex>\mathrm{Rake-Compress}</tex> деревья могут оказаться полезными, если необходимо пересчитывать значения не на путях, а на поддеревьях.

==См. также==
* [[Link-Cut Tree]]

==Примечания==
<references/>

==Источники информации==
* [https://en.wikipedia.org/wiki/Parallel_Tree_Contraction Wikipedia {{---}} Parallel Tree Contraction]
* [https://github.com/BorysMinaiev/bachelor/blob/master/thesis_v2.pdf Б. Ю. Минаев {{---}} Реализация динамических Rake-Compress деревьев в случае отсутствия ограничения на степени вершин]
* [http://www.cs.cmu.edu/~jvittes/rc-trees Acar, Blelloch, and Vittes {{---}} RC-Tree implementation]
* [http://www.cs.princeton.edu/~rwerneck/papers/Wer06-dissertation.pdf R. Werneck {{---}} Design and Analysis of Data Structures for Dynamic Trees]
* G. L. Miller, J. H. Reif {{---}} Parallel Tree Contraction, Journal of Advances in Computer Research Volume 5, 1989
* Umit A. Acar, Guy E. Blelloch, Jorge L. Vittes {{---}} An Experimental Analysis of Change Propagation in Dynamic Trees, 1-2005

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]

Rake-Compress деревья

2016-05-22T17:10:09Z

Kiryukhinv:

Задача, которая решается с помощью [[Link-Cut Tree|динамических деревьев]], формулируется следующим образом. Необходимо поддерживать лес деревьев и выполнять на нем следующие операции:
* <tex>\mathrm{link(u, v)}</tex> {{---}} добавить ребро <tex>(u, v)</tex>. Вершина <tex>u</tex> должна быть корнем некоторого дерева. Вершины <tex>u</tex> и <tex>v</tex> должны находиться в разных деревьях,
* <tex>\mathrm{cut(u, v)}</tex> {{---}} удалить ребро <tex>(u, v)</tex>. Ребро <tex>(u, v)</tex> должно присутствовать в графе,
* <tex>\mathrm{query()}</tex> {{---}} некоторый запрос относительно структуры дерева.

__TOC__
==Идея==
===Описание===
Пусть дано некоторое дерево <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> {{---}} выбирается и объединяется некоторое множество несмежных друг с другом вершин, имеющих ровно одного сына.
<table align="center"><tr>
<td>[[Файл:Rctree-rake.png|x180px|thumb|Операция <tex>\mathrm{Rake}</tex>]]</td>
<td>[[Файл:Rctree-compress.png|x180px|thumb|Операция <tex>\mathrm{Compress}</tex>]]</td>
</tr></table>

Сжатие дерева требует линейного времени и логарифмическое число раундов.

Рассмотрим, как изменяется количество вершин в дереве после применения к нему операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>. Разобьём все вершины дерева на три группы:
* <tex>T_0</tex> {{---}} входящая степень равна нулю,
* <tex>T_1</tex> {{---}} входящая степень равна одному,
* <tex>T_2</tex> {{---}} входящая степень больше одного.

{{Лемма
|about=1
|statement=<tex>T_2 \leqslant T_0 - 1</tex>.
|proof=
Докажем по индукции по высоте дерева. 
* '''База
*: Для дерева из одной вершины утверждение верно.
* '''Переход
*: Пусть утверждение доказано для деревьев высоты меньше <tex>h</tex>. Докажем для дерева высоты ровно <tex>h</tex>. Рассмотрим степень корня: 
*:: Если корень имеет ровно одного ребенка, то переходим к случаю дерева высоты <tex>h - 1</tex>. Если у дерева несколько поддеревьев, то имеем: <tex>T_2 = 1 + \sum\limits_{u \in *: children(root)}T_2(u) \leqslant 1 + \sum\limits_{u \in children(root)}(T_0(u) - 1)</tex>  <tex> \leqslant -1 + \sum\limits_{u \in children}T_0(u) \leqslant -1 + T_0 = T_0 - 1</tex>.
}}
Заметим, что для леса деревьев лемма также справедлива.

{{Лемма
|about=2
|statement=После применения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> к лесу, математическое ожидание количества вершин в нём не превосходит <tex>\dfrac{7}{8}</tex> от их исходного числа.
|proof=Математическое ожидание количества удаленных вершин <tex>\mathrm{deleted} = T_0 + \dfrac{T_1}{8}</tex> (так как все листья будут удалены после операции <tex>\mathrm{Rake}</tex>, а каждая вершина, у которой ровно один сын, будет удалена с вероятностью <tex>\dfrac{1}{8}</tex> после операции <tex>\mathrm{Compress}</tex>). Из предыдущей леммы получаем: 
<tex>\mathrm{deleted} = \dfrac{1}{2} (T_0 + T_2) + \dfrac{1}{8} T_1 \geqslant \dfrac{1}{8} (T_0 + T_1 + T_2)</tex>.
}}

{{Теорема
|statement=Математическое ожидание количества операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>, которые будут выполнены до полного сжатия дерева, равно <tex>O(\log{n})</tex>, где <tex>n</tex> {{---}} общее количество вершин.
|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>. 
Сжатие может быть рассмотрено как рекурсивная кластеризация дерева в один '''кластер'''. Изначально вершины и рёбра составляют базовый кластер. Операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> формируют большие кластеры из нескольких меньших кластеров. На иллюстрации примера все кластеры (кроме базового) обозначены зелёными лепестками. Каждый кластер помечен заглавной буквой метки вершины, входящей в него. Например, кластер <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>. Представление сжатого дерева в виде кластеров:
[[Файл: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='''Граница кластера''' {{---}} множество граничных вершин кластера.
}}
{{Определение
|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>. Пример такого дерева для рассматриваемого исходного дерева:
[[Файл:RC_graph_tree.png|500px|center|thumb|RC-tree для дерева <tex>T</tex>.]]

Поскольку матожидание количества раундов {{---}} логарифм, то такое дерево будет сбалансированным. 
<tex>\mathrm{RC}</tex> дерево можно использовать для ответа на динамические запросы для статического дерева. Для этого в <tex>\mathrm{RC}</tex> дереве сохраним требуемую информацию (необходимо модифицировать для пересчёта информации операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>) и используем обход для ответа на запросы. Поскольку дерево с большой вероятностью является сбалансированным, обход дерева также можно осуществить за логарифм. 
Для динамических деревьев, например, если доступны операции добавления/удаления ребра (операции <tex>\mathrm{link}</tex> и <tex>\mathrm{cut}</tex>), нужно эффективно перестраивать отдельные кластеры, пересчитывая данные. Для этого можно обновлять данные начиная с листа дерева, соответствующего обновляемой вершине в исходном дереве, и подниматься вверх.

==Реализация==
===Хранение===
Для того, чтобы отвечать на запросы относительно структуры леса необходимо сохранить информацию о том, как происходил процесс сжатия леса. Для этого будем хранить таблицу, в каждой строке которой записана информация о структуре леса после выполнения операций. Каждая клетка таблицы будет хранить информацию о вершине после выполнения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>. Из информации будем сохранять родителя вершины, множество детей и метку, сжата ли вершина. 
Пример таблицы для следующей последовательности операций:
[[Файл:RC_tree_example.png|x200px|thumb|Пример выполнения операций.]]
{| class="wikitable"
|-
! Шаг
! align="center" | Операция
! <tex>1</tex>
! <tex>2</tex>
! <tex>3</tex>
! <tex>4</tex>
|-
| align="center" | 4
| align="center" | <tex>\mathrm{Rake}</tex>
| Родитель: {{---}} Дети: <tex>\emptyset</tex>
| align="center" | {{---}}
| align="center" | {{---}}
| align="center" | {{---}}
|-
| align="center" | 3
| align="center" | <tex>\mathrm{Compress}</tex>
| Родитель: {{---}} Дети: <tex>\{3\}</tex>
| align="center" | {{---}}
| Родитель: <tex>1</tex> Дети: <tex>\emptyset</tex>
| align="center" | {{---}}
|-
| align="center" | 2
| align="center" | <tex>\mathrm{Rake}</tex>
| Родитель: {{---}} Дети: <tex>\{2\}</tex>
| Родитель: <tex>1</tex> Дети: <tex>\{3\}</tex>
| Родитель: <tex>2</tex> Дети: <tex>\emptyset</tex>
| align="center" | {{---}}
|-
| align="center" | 1
|
| Родитель: {{---}} Дети: <tex>\{2\}</tex>
| Родитель: <tex>1</tex> Дети: <tex>\{3\}</tex>
| Родитель: <tex>2</tex> Дети: <tex>\{4\}</tex>
| Родитель: <tex>3</tex> Дети: <tex>\emptyset</tex>
|}
 
Для того, чтобы выбирать множество вершин для применения операции <tex>\mathrm{Compress}</tex> будем использовать следующий метод: для каждой вершины с помощью генератора псевдослучайных чисел выберем случайный бит. Вершина добавляется в множество, если у нее ровно один ребенок, она не является корнем и биты, которые были сгенерированы для нее, ребенка и родителя равны <tex>0</tex>, <tex>1</tex> и <tex>1</tex> соответственно.

Рассмотрим более подробно, как необходимо хранить клетки таблицы <tex>\mathrm{Rake-Compress}</tex> дерева. Для вершины необходимо сохранить ее родителя, а также множество детей. Для того, чтобы обрабатывать каждую клетку таблицы за <tex>O(\log{n})</tex>, нужно производить операции с множеством детей за <tex>O(1)</tex>. Рассмотрим, в каких случаях можно сжать вершину:
* если детей у вершины больше одного, то ее точно нельзя сжать,
* если у неё нет детей, то ее можно сжать только во время операции <tex>\mathrm{Rake}</tex>
* если у вершины один ребёнок, то её возможно сжать во время операции <tex>\mathrm{Compress}</tex>.
Чтобы определить, можно ли применить операцию <tex>\mathrm{Compress}</tex> к вершине, в том случае, когда у нее один ребёнок, нужно узнать, какой бит был сгенерирован на текущей итерации для ребёнка (один из трёх битов, генерируемых при операции <tex>\mathrm{Compress}</tex>). Для этого необходимо знать номер вершины-ребёнка. Значит, нам нужно определять, какие элементы находятся в множестве детей только в том случае, когда размер множества равен <tex>1</tex>. Поэтому, всю информацию о множестве можно хранить с помощью двух величин {{---}} хранить количество элементов в множестве и сумму их номеров. Поддерживая сумму номеров детей и их количество, можно эффективно узнавать номер вершины-ребёнка, когда это необходимо. Данная оптимизация позволяет за <tex>O(1)</tex> получать номер ребёнка и за <tex>O(1)</tex> обновлять множество детей. 
Если вершина является корнем, то в качестве ее родителя будем хранить ее номер. Кроме того необходимо хранить изменения, которые произойдут с клеткой при переходе к следующему слою: будем хранить, кто должен стать новым родителем, на сколько изменится количество детей, а также как изменится сумма их номеров. Все это необходимо для того, чтобы обрабатывать каждую изменившуюся клетку за <tex>O(1)</tex>. 

Псевдокод хранения клетки таблицы:
* <tex>\mathrm{id}</tex> {{---}} номер вершины,
* <tex>\mathrm{parent}</tex> {{---}} родитель вершины,
* <tex>\mathrm{cntChild}</tex> {{---}} количество детей вершины,
* <tex>\mathrm{sumChild}</tex> {{---}} сумма номеров детей,
* <tex>\mathrm{newParent}</tex> {{---}} новый родитель вершины после изменений,
* <tex>\mathrm{diffCntChild}</tex> и <tex>\mathrm{diffSumChild}</tex> {{---}} изменения, произведенные с полями <tex>\mathrm{cntChild}</tex> и <tex>\mathrm{sumChild}</tex> соответственно.

'''struct''' Cell''':'''
'''int''' id, parent, cntChild, sumChild
'''int''' newParent, diffCntChild, diffSumChild

'''func''' applyChanges()''':'''
parent = newParent
sumChild += diffSumChild
cntChild += diffCntChild
diffCntChild = diffSumChild = 0

'''func''' addChild(v: '''int''')''':'''
diffCntChild++
diffSumChild += v

'''func''' removeChild(v: '''int''')''':'''
diffCntChild--
diffSumChild -= v

Для хранения <tex>\mathrm{Rake-Compress}</tex> дерева будем использовать следующие данные:
* <tex>\mathrm{cells[]}</tex> {{---}} список клеток, которые ей соответствуют, для каждой вершины,
* <tex>\mathrm{rand}</tex> {{---}} генератор псевдослучайных чисел,
* <tex>\mathrm{time}</tex> {{---}} счётчик количества примененных операций по изменению структуры леса,
* <tex>\mathrm{lastUpdateTime[]}</tex> {{---}} массив, в котором для каждой вершины запишем номер последней операции, при обработки которой была изменена хотя бы одна клетка, которая соответствуют вершине: это позволит эффективно узнавать, была ли вершина уже помечена как поменявшаяся или нет.

'''struct''' RCTree(n: '''int''')''':'''
'''RndGen''' rand = RandBitsGenerator()
'''int''' time = 0
'''for''' i = 0 '''to''' n
lastUpdateTime[i] = 0
cells[i] = []

Кроме запросов о структуре леса, <tex>\mathrm{Rake-Compress}</tex> деревья можно использовать для подсчета значений некоторых функций. Например, каждой вершине можно сопоставить некоторое значение и узнавать, чему равна сумма значений всех вершин, которые находятся в поддереве.
Для этого в клетках таблицы <tex>\mathrm{Rake-Compress}</tex> дерева необходимо хранить не только состояние вершины, но и значение функции, посчитанной на части дерева, которое уже было сжато в вершину. Если функция является аддитивной, то ее пересчет аналогичен пересчету множества детей вершины. Так, если некоторая вершина сжимается к родителю, то в соответствующей родителю клетке необходимо обновить значение функции. При добавлении и удалении ребер необходимо в изменившихся клетках пересчитывать значение функции.

===Построение===
Рассмотрим, как работает алгоритм построения <tex>\mathrm{Rake-Compress}</tex> дерева. Будем строить таблицу по строкам. В каждый момент будем хранить множество вершин, которые еще не были сжаты, и перестраивать следующий слой. Также будем делать операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> одновременно. Чтобы определить, нужно ли сжимать вершину, воспользуемся следующим алгоритмом:
'''bool''' shouldRemoveVertex(c: '''Cell''', rand, layer: '''int''')''':'''
'''if''' c.cntChild == 0
'''return''' ''true''
'''if''' c.cntChild > 1 '''or''' c.parent == c.id
'''return''' ''false''
'''if''' getCellForVertex(c.sumChild).cntChild == 0
'''return''' ''false''
'''if''' rand.getBit(c.id, layer) == 0 '''and''' rand.getBit(c.sumChild, layer) == 1 '''and''' rand.getBit(c.parent, layer) == 1:
'''return''' ''true''
'''return''' ''false''

Таким образом, алгоритм построения дерева выглядит следующим образом:
'''func''' build(parent: '''int[n]''')''':'''
alive = <tex>\{0 \dots n - 1\}</tex>
'''int''' layer = 0
'''for''' i = 0 '''to''' n // заполним таблицу вершинами изначального дерева
cells[i].add(Cell(parent[i]))
'''while''' <tex>\mathrm{alive} \neq \emptyset</tex>
nextAlive = <tex>\emptyset</tex>
'''for''' <tex>v \in \mathrm{alive}</tex>
'''Cell''' c = getCellForVertex(v) // получить клетку таблицы, соответствующую вершине
'''if''' shouldRemoveVertex(c, rand, layer)
'''if''' c.cntChild == 1
getCellForVertex(c.sumChild).newParent = c.parent
getCellForVertex(c.parent).addChild(c.sumChild)
'''if''' c.parent <tex>\neq</tex> v
getCellForVertex(c.parent).remove(v)
'''else'''
nextAlive.add(v)
alive = nextAlive
'''for''' <tex>v \in \mathrm{alive}</tex>
'''Cell''' newCell = getCellForVertex(v).clone().applyChanges()
cells[v].add(newCell)
layer++
===Операции удаления и добавления ребра===
Как только некоторая вершина помечается как изменившаяся, отменим её действие на таблицу:
# Найдем момент времени, когда вершина сжимается к родителю.
# Рассмотрим, какие вершины поменяются при сжатии данной: это ее родитель (если он есть), а также сын (если он есть). Для каждой из этих вершин поменяем значения изменений, которые необходимо применить к состоянию.
# Пометим, что эти вершины поменялись на этом слое. Для этого на каждом слое будем хранить список вершин, которые на нем поменялись. А перед тем как обрабатывать очередной слой будем добавлять в множество изменившихся вершин вершины из соответствующего списка.
# Кроме удаления эффекта от изменившихся вершин также необходимо и добавить правильный эффект. Для этого будем для каждой из изменившихся вершин определять, как ее состояние меняется при переходе к следующему слою. Если вершина сжимается к ее родителю, то пометим родителя и ребенка (если он есть) и поменяем изменение, которое хранится в соответствующих клетках. А для пересчета состояния клеток воспользуемся значениями изменений, которые сохранены в клетках. 
Рассмотрим, что происходит с таблицей при изменении одного ребра. Основная идея заключается в том, чтобы научится пересчитывать все изменения таблицы за время пропорциональное их количеству. Для этого будем эффективно поддерживать множество изменившихся клеток. В момент, когда вершина помечается, как изменившаяся, найдем, как она влияет на таблицу и отменим это влияние. Для начала необходимо найти момент времени, когда вершина сжимается. В этот момент она влияет на не более чем две вершины. Изменим значения <tex>\mathrm{cntChild}</tex>, <tex>\mathrm{sumChild}</tex> и <tex>\mathrm{newParent}</tex> нужным образом. Также необходимо добавить эти вершины в множество изменившихся (в момент, когда будет обработан соответствующий слой). Поэтому, для каждого слоя еще будем хранить список вершин, которые должны быть помечены перед обработкой слоя. Алгоритм обновления дерева:
'''func''' changeTree(<tex>(u, v)</tex>: '''Edge''')''':'''
time = time + 1
affected = <tex>\emptyset</tex>
markAffected(u) // пусть из дерева было удалено ребро <tex>(u, v)</tex>
markAffected(v)
cells[u].parent = u
cells[v].cntChild--
cells[v].sumChild -= u
'''int''' layer = 0
'''while''' <tex>\mathrm{affected} \neq \emptyset</tex>
'''for''' <tex>v \in \mathrm{affectedOnLayer}</tex>
markAffected(v)
'''for''' <tex>v \in \mathrm{affected}</tex>
'''Cell''' c = getCellForVertex(v)
'''if''' shouldRemoveVertex(v)
cells[v].size = layer + 1
'''if''' c.cntChild == 1
getCellForVertex(c.sumChild).newParent = c.parent
getCellForVertex(c.parent).addChild(c.sumChild)
markAffected(c.sumChild)
'''if''' c.parent <tex>\neq</tex> v
getCellForVertex(c.parent).removeChild(v)
markAffected(c.parent)
affected.remove(v)
'''for''' <tex>v \in \mathrm{affected}</tex>
'''Cell''' newCell = getCellForVertex(v).clone().applyChanges()
cells[v][layer + 1] = newCell
layer++

'''func''' markAffected(v: '''int''')''':''' // пометить вершину как изменившуюся
'''if''' lastUpdateTime[v] == time
'''return''' // вершина уже помечена
lastUpdateTime[v] = time
affected.add(v)
removeEffectOfVertex(v)

'''func''' removeEffectOfVertex(v: '''int''')''':''' // удалить отметку о том, что вершина была помечена изменившийся
'''int''' layer = cells[v].size
'''Cell''' c = cells[v][layer]
'''if''' c.parent == v
'''return'''
cells[c].parent.removeChild(v)
'''if''' c.cntChild == 1
cells[c.parent].addChild(c.sumChild)
cells[c.sumChild].newParent = v

==Сравнение с Link-Cut Tree==
Для Link-Cut деревьев (основанных на [[Splay-дерево|splay-деревьях]]), как и для <tex>\mathrm{Rake-Compress}</tex> деревьев, время работы операций <tex>\mathrm{link}</tex> и <tex>\mathrm{cut}</tex> {{---}} <tex>O(\log{n})</tex>. В реальности <tex>\mathrm{RC}</tex> деревья оказываются медленнее, чем <tex>\mathrm{LC}</tex> деревья. 
Отличительной особенностью <tex>\mathrm{RC}</tex> деревьев является возможность параллельного построения: операции <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex> можно выполнять параллельно для всех вершин. Если предположить, что множество детей можно пересчитывать за <tex>O(1)</tex>, то <tex>\mathrm{Rake-Compress}</tex> дерево можно построить за <tex>O(\log{n})</tex> в модели PRAM<ref>[https://en.wikipedia.org/wiki/Parallel_random-access_machine Wikipedia {{---}} Parallel random-access machine]</ref> в случае наличия <tex>\Omega(n)</tex> процессоров. 
Кроме этого, <tex>\mathrm{Rake-Compress}</tex> деревья могут оказаться полезными, если необходимо пересчитывать значения не на путях, а на поддеревьях.

==См. также==
* [[Link-Cut Tree]]

==Примечания==
<references/>

==Источники информации==
* [https://en.wikipedia.org/wiki/Parallel_Tree_Contraction Wikipedia {{---}} Parallel Tree Contraction]
* [https://github.com/BorysMinaiev/bachelor/blob/master/thesis_v2.pdf Б. Ю. Минаев {{---}} Реализация динамических Rake-Compress деревьев в случае отсутствия ограничения на степени вершин]
* [http://www.cs.cmu.edu/~jvittes/rc-trees Acar, Blelloch, and Vittes {{---}} RC-Tree implementation]
* [http://www.cs.princeton.edu/~rwerneck/papers/Wer06-dissertation.pdf R. Werneck {{---}} Design and Analysis of Data Structures for Dynamic Trees]
* G. L. Miller, J. H. Reif {{---}} Parallel Tree Contraction, Journal of Advances in Computer Research Volume 5, 1989
* Umit A. Acar, Guy E. Blelloch, Jorge L. Vittes {{---}} An Experimental Analysis of Change Propagation in Dynamic Trees, 1-2005

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]