148
правок
Изменения
→Доказательство корректности алгоритма
а) Обе эти вершины были достижимы из <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>r</tex> была не достижима из этой вершины в одну сторонуинвертированном графе, ни в другую при первом обходе в инверитированном графетак как её время выхода больше. Но последнего быть не может, так как потому что эти вершины были достижимы из <tex>r</tex> по пункту 1).
Значит, из случая а) и не существования случая б) получаем, что вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы в обоих графах.
