Изменения

===Доказательствокорректности алгоритма=={{Теорема|statement=Докажем два утверждения:* если вершины Вершины <tex>s</tex> и <tex>t</tex> взаимно достижимытогда и только тогда, то они когда после работы выполнения алгоритма окажутся оказываются в одной компоненте [[Отношение_связности,_компоненты_связности#Сильная связность|компонентe сильной связностисвязанности]].* если вершины <tex>s</tex> и <tex>t</tex> после работы алгоритма оказались в одной компоненте сильной связности, то они взаимно достижимы|proof=

====Доказательство первого утверждения=необходимости условия===

Если вершины <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>s</tex>. Значит, время выхода из вершины <tex>t</tex> будет меньше, чем время выхода из вершины <tex>s</tex>. Соответственно, во время выполнения третьего шага алгоритма вершина <tex>s</tex> будет рассмотрена раньше, чем вершина <tex>t</tex>, а значит, вершина <tex>t</tex> снова попадет обе вершины окажутся в одном поддереве по свойству обхода в ее поддерево, и глубина. Следовательно они окажутся будут находится в одной компоненте сильной связности.

====Доказательство второго утверждения=достаточности условия===

1) Рассмотрим корень <tex>r</tex> дерева второго обхода в глубину, в котором оказались вершины <tex>s</tex> и <tex>t</tex>. В Это значит, что в графе <tex>G</tex> существует путь из <tex>r</tex> в <tex>s</tex> и в <tex>t</tex>. Рассмотрим теперь дерево обхода графа <tex>H</tex>. То, что вершина  2) Вершина <tex>r</tex> была рассмотрена вторым обходом в глубину раньше, чем <tex>s</tex> и <tex>t</tex>, говорит нам о том, что значит время выхода из нее при первом обходе в глубину больше, чем время выхода из вершин <tex>s</tex> и <tex>t</tex>. Это может означать, что или обе Из этого мы получаем 2 случая: а) Обе эти вершины были достижимы из <tex>r</tex>, что в инвертированном графе. А это означает их взаимную достижимость в обоих графах, или что между вершин <tex>s</tex> и <tex>r</tex> и взаимную достижимость вершин <tex>r</tex> и <tex>t</tex>. А складывая пути мы получаем взаимную достижимость вершин <tex>s</tex> и <tex>t</tex>. б) Между <tex>r</tex> и этими вершинами вообще нет пути ни в одну сторону, ни в другуюпри первом обходе в инверитированном графе. Но последнего быть не может, так как эти вершины были достижимы из <tex>r</tex> в графе <tex>G</tex>, а значит, вершина <tex>r</tex> достижима из них в графе <tex>H</tex>.  Значит, из случая а) и не существования случая б) получаем, что вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы в обоих графах.}}