436
правок
Изменения
м
small changes
Снова зафиксируем какую-нибудь активную вершину <tex>v_2</tex>, и повторим процесс. Не меняем статус остальных уже активных вершин.
Продолжая этот ветвящийся процесс, мы в конце концов получим лишь неактивные (образующие компоненту, содержащую <tex>v_1</tex>) и нейтральные вершины. '''Стоит добавить<br>Заметим, что это похоже данный процесс очень похож на бфс'''[[Обход в ширину|поиск в ширину]], данным свойством мы воспользуемся позднее.<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 + Z_t − 1</tex>. Все введенные величины зависят от графа <tex>G</tex> и от последовательности выбираемых вершин <tex>v_1,\dotsc</tex>.
