148
правок
Изменения
→Доказательство корректности алгоритма
{{Теорема
|statement=
Вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы тогда и только тогда, когда <tex>\Leftrightarrow</tex> после выполнения алгоритма они оказываются в одной [[Отношение_связности,_компоненты_связности#Сильная связность|компонентe сильной связанности]].
|proof=
Если вершины <tex>s</tex> и <tex>t</tex> были взаимно достижимы в графе <tex>G</tex>, то во время выполнения третьего шага алгоритма обе вершины окажутся в одном поддереве по свойству обхода в глубина. Следовательно они будут находится в одной компоненте сильной связности.
1) Рассмотрим корень <tex>r</tex> дерева второго обхода в глубину, в котором оказались вершины <tex>s</tex> и <tex>t</tex>. Это значит, что в графе <tex>G</tex> существует путь из <tex>r</tex> в <tex>s</tex> и в <tex>t</tex>.
