editor
143
правки
Изменения
→Теорема Иммермана
'''Enum'''(<tex>s, i, ri, G</tex>)
<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'''
'''reject''' //не нашли <tex>r_i</tex> вершин, не допускаем
'''Enum''' перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из <tex>s</tex>.
'''Next'''(<tex>s, i, r_i, G</tex>)
<tex>r = 1</tex> //<tex>r_{i+1}</tex> хотя бы один, так как <tex>r \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> '''if''' (<tex>u</tex> '''in''' '''Enum'''(<tex>s, i, r_i, G</tex>)) //перечисляем все вершины из <tex>R_i</tex>, если <tex>u</tex> одна из них, то <tex>v \in R_{i+1}</tex> <tex>r</tex>++ //увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата
'''break'''
'''return''' <tex>r</tex>
'''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'''
