436
правок
Изменения
м
Нет описания правки
Пусть:
* <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>
