436
правок
Изменения
м
Нет описания правки
{{Утверждение
|statement=Пусть <tex>d > 1</tex>. Тогда вероятность <tex>p</tex>, что <tex>size(cc(v)) = O(\log n)</tex> (<tex>cc</tex> {{---}} компонента связности, содержащая <tex>v</tex>): <tex>p < 1</tex> {{---}} константа.
|proof=Главная идея доказательства, которую мы будем использовать в дальнейшем {{---}} изменение алгоритма поиска в ширину таким образом, чтобы только что открытые вершины были выбраны из множества фиксированного размера. Такая модификация превращает поиск в ширину в [[Ветвящийся процесс|ветвящийся процесс]].
}}
{{Теорема
