436
правок
Изменения
м
small changes
Наверное, лучше придумать другой заголовок'''
Пользуясь идеями, изложенными в доказательстве леммы, перейдем от модифицированного поиска в ширину к ветвящемуся процессу. Этот процесс используется для генерации случайных деревьев, возможно, бесконечного размера.<br>
Рассмотрим натуральное случайное число <tex>y</tex>, обозначающее количество детей потомков у очередной исследованной вершины. Каждый раз это значение выбирается случайно и независимо.<br>Процесс построения дерева заканчивается, образуя конечное дерево, когда у каждой вершины построены все ее "дети" '''Почему сначала не в кавычках, а потом в кавычках? Дай тогда формальное определение. Общая просьба к тексту, кстати, писать чуть более научно, использовать меньше вводных слов и предложений в 3 слова'''потомки. Данный процесс может продолжаться бесконечно. <br>
Пусть <tex>y \thicksim Binomial(s = n−c_1\log n, \frac{d}{n})</tex>. Пусть <tex>p′</tex> {{---}} вероятность того, что <tex>size(cc(v)) = O(\log n)</tex> в модифицированном поиске в ширину. Пусть <tex>q</tex> {{---}} вероятность окончания процесса. Тогда <tex>q \geq p′</tex>, поскольку поиск в ширину, заканчивающийся с <tex> \le c_1\log n</tex> вершинами, приводит к окончанию построения дерева.<br>
Пусть <tex>p_i = \binom{s}{i}(\frac{d}{n})^i(1 − \frac{d}{n})^{s − i}</tex> {{---}} вероятность, что <tex>y</tex> производит <tex>i</tex> детейпотомков. Тогда:<br>
<tex>\sum_{i = 0..s}p_i = 1</tex> и <tex>\sum_{i = 0..s}ip_i = E(y) = \frac{ds}{n} > 1</tex>.<br>
Глубина дерева <tex>\geq</tex> количеству вершин. Пусть <tex>a_i</tex> {{---}} вероятность того, что процесс закончится с деревом глубины <tex>t</tex>. Имеем:<br>
