436
правок
Изменения
м
→Обход случайного графа
== Обход случайного графа ==
Приведем ряд утверждений, которые будут использованы а дальнейшем. Доказательство опустим ради лаконичиностилаконичности, их, а также более детальный рассказ можно найти в [4].
{{Утверждение
|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=Главная идея доказательства, которую мы будем использовать в дальнейшем {{---}} изменение алгоритма БФС таким образом, чтобы только что открытые вершины были выбраны из множества фиксированного размера. Такая модификация превращает БФС поиск в ширину в [[Ветвящийся процесс|ветвящийся процесс]].
}}
{{Теорема
