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