editor
143
правки
Изменения
→Теорема Иммермана
<tex>counter</tex> <tex>\leftarrow</tex> 0 //количество уже найденных и выведенных элементов
'''for''' <tex>v = 1..n</tex> '''do''' //перебираем все вершины графа
'''continue''' or find path //недетерминированно угадываем путь из s до v или переходим к следующей вершине
<tex>counter</tex>++
'''return''' <tex>v</tex> //выдаем вершину, до которой угадали путь
'''if''' (<tex>counter \geq r_i</tex>) //нашли <tex>r_i</tex> вершин, допускаем, завершаем работу
'''accept'''
'''NCONN'''(<tex>G, s, t</tex>)
<tex>r_n = 1</tex> //<tex>r_0 = 1</tex>
'''for''' <tex>i = 0..n - 2</tex> '''do''' //вычисляем <tex>r_{n-1}</tex>
<tex>r_n = </tex> '''Next'''(<tex>s, i, r_n, G</tex>)
'''if''' (<tex>t1</tex> '''in''' '''Enum'''(<tex>s, n - 1, r_n, G</tex>)) //перечисляем вершины из <tex>R_{n-1}</tex>, если <tex>t</tex> была перечислена, то <tex>t</tex> достижима и выдаем '''reject''', иначе '''accept'''
