148
правок
Изменения
→Доказательство корректности алгоритма
{{Теорема
|statement=
Вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы <tex>\Leftrightarrow</tex> после выполнения алгоритма они принадлежат одной [[Отношение_связности,_компоненты_связности#Сильная связность|компонентe сильной связанности]]одному дереву обхода в глубину.
|proof=
<tex>\Rightarrow</tex>
Если вершины <tex>s</tex> и <tex>t</tex> были взаимно достижимы в графе <tex>G</tex>, то на третьем этапе будет найден путь из одной вершины в другую, это означает, что по окончанию алгоритма обе вершины лежат в одном поддереве. Следовательно они будут находится в одной компоненте сильной связности.
<tex>\Leftarrow</tex>
1) Вершины <tex>s</tex> и <tex>t</tex> принадлежат одной компоненте связности <tex>\Rightarrow</tex> лежат в одном и том же дереве поиска в глубину на третьем этапе алгоритма. Значит, что они обе достижимы из корня <tex>r</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>t</tex>. Значит и <tex>r</tex> была не достижима из этой вершины <tex>t</tex> в инвертированном графе, так как её время выхода больше<tex>r</tex>. Но Значит между этими вершинами нет пути, но последнего быть не может, потому что эти вершины были достижимы <tex>t</tex> была достижима из <tex>r</tex> по пункту 1).
Значит, из случая а) и не существования случая б) получаем, что вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы в обоих графах.
