Изменения

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

Навигация