Изменения

[[Файл:Dfs_strong.png|290px|thumb|Вершины 2, 4, 5 сильносвязаны.<br>Синим цветом обозначен обод DFS по инвертированным ребрам]][[Отношение_связности,_компоненты_связности#Сильная связность|Компоненты сильной связанностисвязности]] в графе <tex>G</tex> можно найти с помощью [[Обход_в_глубину,_цвета_вершин | поиска в глубину]] в 3 этапа:

#Выполнить в <tex>H</tex> поиск в глубину и найти <tex>f[u]</tex> - — время окончания обработки вершины <tex>u</tex>

Так как компоненты сильной связности <tex>G</tex> и <tex>H</tex> графа совпадают, то первый поиск в глубину для нахождения <tex>f[u]</tex> можно выполнить на графе <tex>G</tex>, а второй - — на <tex>H</tex>.<br clear = "all">

Вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы <tex>\Leftrightarrow</tex> после выполнения алгоритма они оказываются принадлежат одному дереву обхода в одной [[Отношение_связности,_компоненты_связности#Сильная связность|компонентe сильной связанности]]глубину.

Если вершины <tex>s</tex> и <tex>t</tex> были взаимно достижимы в графе <tex>G</tex>, то во время выполнения третьего шага на третьем этапе будет найден путь из одной вершины в другую, это означает, что по окончанию алгоритма обе вершины окажутся лежат в одном поддереве по свойству обхода в глубина. Следовательно они будут находится в одной компоненте сильной связности.

1) Рассмотрим корень # Вершины <tex>s</tex> и <tex>t</tex> лежат в одном и том же дереве поиска в глубину на третьем этапе алгоритма. Значит, что они обе достижимы из корня <tex>r</tex> этого дерева второго обхода . # Вершина <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>Gs</tex> существует путь и <tex>t</tex>.##Хотя бы одна не достижима из <tex>r</tex> в инвертированном графе, например <tex>st</tex> . Значит и <tex>r</tex> была не достижима из <tex>t</tex> в инвертированном графе, так как время выхода <tex>r</tex> - больше . Значит между этими вершинами нет пути, но последнего быть не может, потому что <tex>t</tex>была достижима из <tex>r</tex> по пункту 1).

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>r</tex> в графе <tex>G</tex>, а значит, вершина <tex>r</tex> достижима из них в графе <tex>H</tex>.  Значит, из случая а) 1 и не существования случая б) 2.2 получаем, что вершины <tex>s</tex> и <tex>t</tex> взаимно достижимы в обоих графах.

#Для того, чтобы инвертировать все ребра в графе, представленном в виде списка потребуется <tex>O(V + E)</tex> действий. Для матричного представления графа ненужно не нужно выполнять никакие действия для его инвертирования.

'''dfs1function'''dfs1(<tex>v</tex>) : <tex>color[v] \leftarrow</tex> = 1 '''for''' (всех <tex>i</tex> смежных с <tex>v</tex>, u)'''in''' E '''if''' (вершина <tex>i</tex> не посещена) '''dfs1not'''visited[u] dfs1(<tex>G[v][iu]</tex>) Добавляем вершину <tex>v</tex> в конец списка <tex>ord</tex>

'''dfs2function'''dfs2(<tex>v</tex>) : <tex>component[v] \leftarrow = col</tex> '''for''' (всех <tex>i</tex> смежных с <tex>v</tex>, u)'''in''' E '''if''' (если вершина <tex>i</tex> u еще не находится ни в какой компоненте) '''dfs2'''(<tex>H[v][iu]</tex>)

'''mainfunction'''main(): считываем исходные данные, формируем массивы <tex>G</tex> и <tex>H</tex> '''for''' (по всем вершинам <tex>i</tex> графа <tex>G</tex>) u '''in''' V '''if''' (вершина <tex>i</tex> не посещена) '''dfs1not'''visited[u] dfs1(iu) <tex>col \leftarrow</tex> = 1 '''for''' (по всем вершинам <tex>i</tex> u списка <tex>ord[]</tex> в обратном порядке) '''if''' (если вершина <tex>i</tex> u не находится ни в какой компоненте) '''dfs2'''(<tex>i</tex>u) <tex>col</tex>++

==ЛитератураИсточники информации==