Изменения

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