Отношение эквивалентности в DFS

Легче понять это, имея под рукой картинку:

В неориентированных графах две вершины связаны, если они имеют путь, соединяющий их. Как определить связность в ориентированном графе? Говорят, что вершина a сильно связана с b, если существуют два пути: один из a в b, а другой из b в a.

Автор здесь утверждает, что мы определяем сильную связность в ориентированных графах, если существует направленный путь, соединяющий вершины a с b, и направленный путь, соединяющий вершины b и a.

У однонаправленных графов нет стрелок (направления), а у направленных есть, см. ссылку ниже для справки: http://courses.cs.washington.edu/courses/cse326/00wi/handouts/lecture21/sld014.htm

Теперь давайте обратимся к изображению из предоставленной ссылки. Вершины Han и Lea сильно связаны в ориентированном графе, так как существует направленный путь из Han в Lea и из Lea в Han.

Теперь вот определение транзитивности из статьи:

Переходное свойство: Если a#b и b#c, то a#c. Давайте расширим это для сильной связности: если a ~ b и b ~ c, у нас есть четыре пути: a-b, b-a, b-c и c-b. Объединение их в пары a-b-c и c-b-a дает два пути, соединяющих a-c и c-a, поэтому a ~ c, показывая, что свойство транзитивности выполняется для сильной связности. Поскольку все три свойства верны для сильной связности, сильная связность является отношением эквивалентности.

Это расширение симметричного свойства, пожалуйста, обратитесь еще раз к ссылке для изображения. Теперь, если бы между Леей и Люком был направленный путь, Хан и Люк были бы связаны транзитивно.

Обратите внимание, что для нашего определения было важно, чтобы пути a-b и b-a перекрывались. Если бы мы сделали небольшое изменение, например, определили, что две вершины должны быть соединены, если они являются частью направленного цикла, мы не сможем конкатенировать пути и показать, что свойство транзитивности выполняется.

И, наконец, если бы в ориентированном графе была определена сильная связность, так что вершины а и b связаны, если существует только один направленный путь от а к b, без обязательного наличия формы соединения b к а, то мы никогда не смогли бы вернуться к a из c, что требуется для транзитивности.

Если вы снова посмотрите на картинку и представите, что Лея и Люк связаны (обратное направление), как только вы перейдете от Хана -> Леи -> Люка, вы не сможете вернуться к Хану — транзитивность не выполняется.

Следовательно, определение сильной связности требует наличия направленного пути в обоих направлениях между вершинами, иначе транзитивность была бы невозможна.

Поскольку все три свойства верны для сильной связности, сильная связность является отношением эквивалентности.

Свойство транзитивности должно быть действительным для сильной связности в ориентированных графах, иначе вывод, сделанный выше, был бы невозможен.

Направленный цикл обычно означает простой направленный цикл (без повторения).

Рассмотрим график
G = (V,E)
V = {A,B,C,D}
E = {(A,B),(B,D),(D,C),(C,B),(D,A)}
(нарисуйте его, это должно помочь, обратите внимание, что эти ребра являются кортежами и поэтому направлены)

Если бы связность определялась как «принадлежность к одному и тому же простому циклу», то мы могли бы сказать, что А и В связаны через ABDA. B и C соединены через BDCB.

Если бы эта связность была транзитивной, то из определения свойства транзитивности мы можем заключить, что А и С должны быть связны.

Согласно нашему (модифицированному, расплывчатому) определению связности должен существовать простой цикл, содержащий А и С.

Конечно, нет, невозможно конкатенировать циклы, сделанные для A и B, B и C, потому что ребро BD должно было бы повторяться при их соединении.