Изменения

Теперь докажем, что если <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>rf[u]</tex> имеет большее время окончания обработки . Предположим, что пути <tex>f[s \rightsquigarrow r]</tex> > в исходном графе нет. Тогда в инвертированном графе нет пути <tex>f[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</tex> в <tex>\rightsquigarrow s</tex>, т.е. <tex>r</tex> и <tex>s</tex> сильно связаны. Те же рассуждения доказывают, что <tex>t</tex> и <tex>r</tex> сильно связаны, из чего следует что <tex>t</tex> и <tex>s</tex> также сильно связаны.