48
правок
Изменения
Нет описания правки
Другими словами это множество всех вершин, достижимых из <tex>s</tex> не более чем за <tex>i</tex> шагов.
Обозначим <tex>|R_i|</tex> за <tex>r_i</tex>.
Заметим, что если <tex>t \notin R_{n-1}</tex>, где <tex>n = |V|</tex>, то не существует путь <tex>s</tex> в <tex>t</tex> в графе <tex>G</tex>, то есть <tex><G, s, t></tex>&nbsnbsp;∈&nbsnbsp;'''STNONCON'''.
'''Лемма''': Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти.
Теперь напишем алгоритм, который будет недетерминированно решать задачу '''STNONCON''' на логарифмической памяти.
Он будет состоять из двух частей: вычисление <tex>r_{n-1}</tex> и перечисление всех вершин из <tex>R_{n - 1}</tex>.
Вычисление <tex>r_{n-1}</tex> происходит путем вызова <code>Next</code> (<tex>n - 1</tex>) раз, при этом каждый раз в качестве <tex>r_i</tex> подставляется новое полученное значение.
<code>
