211
правок
Изменения
м
→Теорема Иммермана
| proof =
Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти.
'''Enum'''(<tex>s, i, rir_i, G</tex>)
<tex>counter</tex> <tex>\leftarrow</tex> 0 //количество уже найденных и выведенных элементов
'''for''' <tex>v = 1..n</tex> '''do''' //перебираем все вершины графа
'''Next'''(<tex>s, i, r_i, G</tex>)
<tex>r = 1</tex> //<tex>r_{i+1}</tex> хотя бы один, так как <tex>r s \in R_{i+1}</tex>
'''for''' <tex>v = 1..n</tex>; <tex>v \ne s</tex> '''do''' //перебираем все вершины графа, кроме <tex>s</tex> — это кандидаты на попадание в <tex>R_{i+1}</tex>
'''for''' <tex>u : (u, v) \in E</tex> '''do''' //перебираем все ребра, входящие в <tex>v</tex>
