Изменения

Если <tex>t \notin R_{n-1}</tex>, где <tex>n = |V|</tex>, то не существует путь из <tex>s</tex> в <tex>t</tex> в графе <tex>G</tex>, то есть <tex><\langle G, s, t> \rangle \in </tex> NCONN.{{Лемма| statement = Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти.| proof = Можно построить недетерминированный алгоритм, который будет допускать <tex>r_i</tex> и при этом будет перечислять все вершины из <tex>R_i</tex> на <tex>O(\log |G|)</tex> памяти. '''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>.Под угадыванием пути подразумевается последовательность недетерминированных выборов следующей вершины пути из <tex>s</tex> в <tex>v</tex>.Для угадывания пути необходимо <tex>O(\log |G|)</tex> памяти, так как необходимо лишь хранить текущую и следующую угадываемую вершины угадываемого пути. '''Enum''' является недетерминированым алгоритмом, и если существует порядок его исполнения достигающий '''accept''', то происходит допуск.}}