436
правок
Изменения
м
Minor changes
<tex>Y_0 = 1, Y_i = Y_{i - 1} + Z_i - 1</tex>.
}}
Представлять себе описанный только что процесс можно так. В начальный момент времени есть одна частица. Затем она приносит <tex>Z_1</tex> потомков и умирает. Заметим, что она может умереть, даже не принеся потомстваоставив потомков, так как величина <tex>Z_1</tex> равна нулю с положительной вероятностью. На следующем шаге все повторяется: какая-то частица (порядок роли не играет) порождает <tex>Z_2</tex> новых частиц, а сама гибнет. И так далее. Популяция может выродиться, а может и жить вечно.
{{Теорема
|id = th1
Продолжая этот ветвящийся процесс, мы в конце концов получим лишь «мертвые» (образующие компоненту, содержащую <tex>v_1</tex>) и нейтральные вершины.
Обозначим число «живых» вершин в момент времени <tex>t</tex> через <tex>Y_t</tex>, число нейтральных вершин {{---}} через <tex>N_t</tex>, а число потомков очередной «живой» вершины, «отправляющейся в последний путь»объявляющейся «мертвой», {{---}} через <tex>Z_t</tex>. Тогда, очевидно, <tex>Y_0 = 1,Y_t = Y_t−1 + Z_t − 1</tex>. Разумеется, все Все введенные величины зависят от графа <tex>G</tex> и от последовательности выбираемых вершин <tex>v_1,\dotsc</tex>.
Если <tex>G</tex> посчитать случайным, то при любом выборе вершин <tex>v_1,\dotsc</tex> получатся случайные величины <tex>Y_t, N_t, Z_t</tex> на пространстве <tex>G(n, p)</tex>.
Таким образом, критическое значение <tex>\alpha</tex>, вплоть до которого есть именно стремление к нулю, {{---}} это решение уравнения <tex>\alpha = 1 - e^{-c\alpha}</tex> или, что равносильно, <tex>1 - \alpha = e^{-c\alpha}</tex>. А это и есть уравнение из [[th2| предыдущей теоремы]], если заменить <tex>\lambda</tex> на <tex>c</tex>.
}}
== Обход случайного графа ==
== Литература ==
