436
правок
Изменения
м
links semi-fix
== Обход случайного графа ==
Приведем ряд утверждений, которые будут использованы а дальнейшем. Доказательство опустим ради лаконичности, их, а также более детальный рассказ можно найти в <refname="chap4">Blum A. Random Graphs // CS 598 Topics in Algorithms (UIUC), 2015. URL: https://www.cs.cmu.edu/~avrim/598/chap4only.pdf</ref> [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> {{---}} константа.
# <tex>m = 1</tex> <tex>\&</tex> <tex>p_1 = 1</tex> {{---}} вероятность исчезновения <tex> = 0</tex>;<br>
# <tex>m > 1</tex> {{---}} вероятность исчезновения <tex> < 1</tex>, но, если <tex>p_0 = 0</tex>, процесс не завершится, так как у каждой вершины найдется по крайней мере один потомок;<br>
Подробное описание доказательств данного факта, а также самих утверждений можно найти в <ref>Blum A. Random Graphs name="chap4" // CS 598 Topics in Algorithms (UIUC), 2015. URL: https://www.cs.cmu.edu/~avrim/598/chap4only.pdf</ref>[4].
== Вывод ==
