436
правок
Изменения
index fix
Данный процесс очень похож на [[Обход в ширину|поиск в ширину]], этим свойством мы воспользуемся позднее.<br>
Обозначим число активных вершин в момент времени <tex>t</tex> через <tex>Y_t</tex>, число нейтральных вершин {{---}} через <tex>N_t</tex>, а число соседей вершины, которую собираемся пометить как неактивную, {{---}} через <tex>Z_t</tex>. Тогда <tex>Y_0 = 1,Y_t = Y_t−1 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>.
