Изменения

Теперь докажем, что если <tex>s</tex> и <tex>t</tex> находятся в одном дереве поиска, то они являются сильно связанными. Пусть <tex>r</tex> - корень этого дерева. Тогда существует путь <tex>r \rightsquigarrow s</tex>, из чего следует, что в инвертированном графе есть путь <tex>s \rightsquigarrow r</tex>. Очевидно, что <tex>f[r]</tex> > <tex>f[s]</tex>, т. к. мы рассматриваем вершины в порядке убывания <tex>f[u]</tex>. Предположим, что пути <tex>s \rightsquigarrow r</tex> в исходном графе нет. Тогда в инвертированном графе нет пути <tex>r \rightsquigarrow s</tex>. Исходя из факта существования в инвертированном графе <tex>s \rightsquigarrow r</tex> и отсутствия <tex>r \rightsquigarrow s</tex>, делаем вывод, что <tex>r</tex> была посещена как потомок <tex>s</tex> в дереве поиска в глубину или <tex>r</tex> уже была обработана поиском в глубину на момент начала поиска из <tex>s</tex>. Но тогда <tex>f[s]</tex> > <tex>f[r]</tex>, что является противоречием. Значит, наше предположение об отсутсвии пути <tex>s \rightsquigarrow r</tex> было не верно. Тогда в исходном графе существуют пути как <tex>s \rightsquigarrow r</tex>, так и <tex>r \rightsquigarrow s</tex>, т.е. <tex>r</tex> и <tex>s</tex> сильно связаны. Те же рассуждения доказывают, что <tex>t</tex> и <tex>r</tex> сильно связаны, из чего следует что <tex>t</tex> и <tex>s</tex> также сильно связаны.