436
правок
Изменения
м
Пусть <tex>p_i = \binom{s}{i}(\frac{d}{n})^i(1 − \frac{d}{n})^{s − i}</tex> {{---}} вероятность, что <tex>y</tex> производит <tex>i</tex> потомков. Тогда, а значит:<br>
Minor changes
Рассмотрим натуральное случайное число <tex>y</tex>, обозначающее количество потомков у очередной исследованной вершины. Каждый раз это значение выбирается случайно и независимо.<br>
Процесс построения дерева заканчивается, образуя конечное дерево, когда у каждой вершины построены все ее потомки. Данный процесс может продолжаться бесконечно. <br>
Пусть :* <tex>y \thicksim Binomial(s = n−c_1\log n, \frac{d}{n})</tex>. <br>* Пусть <tex>p′</tex> {{---}} вероятность того, что <tex>size(cc(v)) = O(\log n)</tex> в модифицированном поиске в ширину.<br>Пусть * <tex>q</tex> {{---}} вероятность окончания процесса. <br>Тогда <tex>q \geq p′</tex>, поскольку поиск в ширину, заканчивающийся с <tex> \le c_1\log n</tex> вершинами, приводит к окончанию построения дерева.<br>
<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>
<br>
