148
правок
Изменения
→Доказательство корректности алгоритма
<tex>\Leftarrow</tex>
1) Вершины <tex>s</tex> и <tex>t</tex> принадлежат одной компоненте связности, т.е. <tex>\Rightarrow</tex> лежат в одном и том же дереве поиска в глубину на третьем этапе алгоритма. Значит, что они обе достижимы из корня <tex>r</tex> этого дерева.
2) Вершина <tex>r</tex> была рассмотрена вторым обходом в глубину раньше, чем <tex>s</tex> и <tex>t</tex>, значит время выхода из нее при первом обходе в глубину больше, чем время выхода из вершин <tex>s</tex> и <tex>t</tex>. Из этого мы получаем 2 случая:
