48
правок
Изменения
Нет описания правки
Чтобы показать правильность работы алгоритма необходимо показать:
*В случае недостижимости <tex>t</tex> из <tex>s</tex> недетерминированые выборы приводят алгоритм к единицедопуску.*Если <tex>t</tex> достижима из <tex>s</tex>, то вне зависимости от недетерминированых выборомвыборов, совершаемых алгоритмом, результат нольалгоритм не приходит к допуску.
Определим <tex>R_i = \{v:</tex> существует путь из <tex>s</tex> в <tex>v</tex> длиной <tex>\le i\}</tex>. Другими словами это множество всех вершин,
