Изменения

Если вершины <tex>s</tex> и <tex>t</tex> были взаимно достижимы в графе <tex>G</tex>, то они будут взаимно достижимы и в графе <tex>H</tex>. Рассмотрим дерево обхода в глубину графа <tex>H</tex>. Поскольку вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы, то очевидно, что одна из них окажется в поддереве другой. Без потери общности скажем, что вершина <tex>t</tex> оказалась в поддереве вершины <tex>ts</tex>. Значит, время выхода из вершины <tex>t</tex> будет меньше, чем время выхода из вершины <tex>s</tex>. Соответственно, во время третьего шага алгоритма вершина <tex>s</tex> будет рассмотрена раньше, чем вершина <tex>t</tex>, а значит, вершина <tex>s</tex> снова попадет в ее поддерево, и они окажутся в одной компоненте сильной связности. ====Доказательство второго утверждения==== Рассмотрим корень <tex>r</tex> дерева второго обхода в глубину, в котором оказались вершины <tex>s</tex> и <tex>t</tex>. В графе <tex>G</tex> существует путь из <tex>r</tex> в <tex>s</tex> и в <tex>t</tex>. Рассмотрим теперь дерево обхода графа <tex>H</tex>. То, что вершина <tex>r</tex> была рассмотрена вторым обходом в глубину раньше, чем <tex>s</tex> и <tex>t</tex>, говорит нам о том, что время выхода из нее больше, чем время выхода из вершин <tex>s</tex> и <tex>t</tex>. Это может означать, что или обе эти вершины были достижимы из <tex>r</tex>, что означает их взаимную достижимость в обоих графах, или что между <tex>r</tex> и этими вершинами вообще нет пути ни в одну сторону, ни в другую. Но последнего быть не может, так как эти вершины были достижимы из <tex>r</tex> в графе <tex>G</tex>, а значит, вершина <tex>r</tex> достижима из них в графе <tex>H</tex>. Значит, вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы в обоих графах.