Equivalence relation in DFS

Question

I am reading about strong connected components in below link.

https://www.ics.uci.edu/~eppstein/161/960220.html

Here author mentioned

Recall that a relation is another word for a collection of pairs of objects (if you like, you can think of a relation as being a directed graph, but not the same one we're using to define connectivity). An equivalence relation a # b is a relation that satisfies three simple properties:

• Reflexive property: For all a, a # a. Any vertex is strongly connected to itself, by definition.
• Symmetric property: If a # b, then b # a. For strong connectivity, this follows from the symmetry of the definition. The same two paths (one from a to b and another from b to a) that show that a ~ b, looked at in the other order (one from b to a and another from a to b) show that b ~ a.
• Transitive property: If a # b and b # c, then a # c. Let's expand this out for strong connectivity: if a ~ b and b ~ c, we have four paths: a-b, b-a, b-c, and c-b. Concatenating them in pairs a-b-c and c-b-a produces two paths connecting a-c and c-a, so a ~ c, showing that the transitive property holds for strong connectivity.

Since all three properties are true of strong connectivity, strong connectivity is an equivalence relation.

Note that it was critical for our definition that we allowed the paths a-b and b-a to overlap. If we made a small change such as defining two vertices to be connected if they are part of a directed cycle, we wouldn't be able to concatenate the paths and show that the transitive property holds.

My question is on last statement: what does author mean by we allowed paths a-b and b-a to overlap?

Moreover, what does author mean by: "If we made a small change such as defining two vertices to be connected if they are part of a directed cycle, we wouldn't be able to concatenate the paths and show that the transitive property holds"?

Thanks for your time

Answer 1

A directed cycle usually means a simple directed cycle (no repetition)

Consider the Graph
G = (V,E)
V = {A,B,C,D}
E = {(A,B),(B,D),(D,C),(C,B),(D,A)}
(Draw it out, it should help, note that those edges are tuples and are therefore directed)

If connectedness were defined as "belonging to the same simple cycle" then we can say that A and B are connected through ABDA. B and C are connected through BDCB.

If this connectedness were transitive then because of the definition of the transitive property we can conclude that A and C must be connected.

From our (modified, loose) definition of connectedness there must exist a simple cycle containing A and C.

Of course, there isn't, it's not possible to concatenate the cycles made for A and B, and B and C because the edge BD would have to be repeated in joining them.

Answer 2

It is easier to understand this with a picture at hand:

In undirected graphs, two vertices are connected if they have a path connecting them. How should we define connected in a directed graph? We say that a vertex a is strongly connected to b if there exist two paths, one from a to b and another from b to a.

Author here states that we define strong connectivity in directed graphs if there is directed path connecting vertex a with b and directed path connecting vertex b and a.

Unidirected graphs do not have arrows (direction) and directed ones do, see link bellow for reference: http://courses.cs.washington.edu/courses/cse326/00wi/handouts/lecture21/sld014.htm

Now let us refer to picture from the provided link. Vertices Han and Lea are strongly connected in directed graph because there exists directed path from Han to Lea and from Lea to Han.

Now here is definition of transitivity from the article:

Transitive property: If a # b and b # c, then a # c. Let's expand this out for strong connectivity: if a ~ b and b ~ c, we have four paths: a-b, b-a, b-c, and c-b. Concatenating them in pairs a-b-c and c-b-a produces two paths connecting a-c and c-a, so a ~ c, showing that the transitive property holds for strong connectivity. Since all three properties are true of strong connectivity, strong connectivity is an equivalence relation

This is expansion of symmetric property, please refer again to link for picture. Now if there was directed path between Leia and Luke, Han and Luke would be transitively connected.

Note that it was critical for our definition that we allowed the paths a-b and b-a to overlap. If we made a small change such as defining two vertices to be connected if they are part of a directed cycle, we wouldn't be able to concatenate the paths and show that the transitive property holds.

And finally, if strong connectivity was defined in directed graph such that vertices a and b are connected if there is only a single directed path from a to b, without requirement there is a connection form b to a, then we could never get back to a from c which is required for transitivity.

If you look at the picture again, and imagine that Leia and Luke are connected (reverse direction), once you get from Han -> Leia -> Luke, you cannot get back to Han - transitivity does not hold.

Therefore, definition of Strong connectivity requires there is directed path in both direction between vertices, otherwise transitivity would not be possible.

Since all three properties are true of strong connectivity, strong connectivity is an equivalence relation.

Transitivity property must be valid for Strong connectivity in directed graphs, otherwise the conclusion above would not be possible.