436
правок
Изменения
м
small changes
== Вывод ==
Используя результаты, полученные в предыдущей части, сделаем вывод о вероятности окончания работы поиска в ширину на случайном графе <tex>G(n, \frac{d}{n})</tex>. Рассчитав <tex>p_0</tex> и <tex>p_1</tex>, можно сделать следующие выводы:<br>
# <tex>d < 1</tex> <tex>||</tex> <tex>d = 1</tex> <tex>\&</tex> <tex>p_1 < 1</tex> {{---}} вероятность завершения<tex> = 1</tex>процесс завершится с вероятностью один;<br># <tex>d = 1</tex> <tex>\&</tex> <tex>p_1 = 1</tex> {{---}} вероятность завершения '''напиши словами и это и выше и ниже'''<tex> = 0</tex>процесс будет протекать бесконечно;<br># <tex>d > 1</tex> {{---}} вероятность исчезновения <tex> < 1</tex>меньше единицы, но, если <tex>p_0 = 0</tex>, процесс не завершится, так как у каждой вершины найдется по крайней мере один потомок;<br>
== См. также ==
