48
правок
Изменения
Нет описания правки
Определим ''R<sub>i</sub>'' = {''v'': существует путь из ''s'' в ''v'' длиной ≤ ''i''}. Другими словами это множество всех вершин,
достижимых из ''s'' не более чем за ''i'' шагов. Обозначим |''R<sub>i</sub>''| за ''r<sub>i</sub>''.
Заметим, что если ''t''<tex>$\notin$<\tex>''R''<sub>''n''−1</sub>, где ''n'' = |''V''|, то не существует путь ''s'' в ''t'' в графе ''G'', то есть <math>\langle G,s,t\rangle</math> ∈ STNONCON.
