Изменения

Перейти к: навигация, поиск

Теорема Иммермана

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

Навигация