Prove that \strongly connected" is an equivalence relation on the vertex set of a directed graph

Solutions

Expert Solution

Definition:

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.

Note that we allow the two paths to share vertices or even to share edges. We will use a ~ b as shorthand for "a is strongly connected to b". We will allow very short paths, with one vertex and no edges, so that any vertex is strongly connected to itself.

Proof :

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.

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

Write an algorithm to determine if the directed graph is strongly connected or not

Let G be a simple graph. Prove that the connection relation in G is an equivalence...

Let G be a simple graph. Prove that the connection relation in G is an equivalence relation on V (G)

7. Prove that congruence modulo 10 is an equivalence relation on the set of integers. What...

7. Prove that congruence modulo 10 is an equivalence relation on the set of integers. What do the equivalence classes look like?

Prove that the equivalence classes of an equivalence relation form a partition of the domain of...

Prove that the equivalence classes of an equivalence relation form a partition of the domain of the relation. Namely, suppose ? be an equivalence relation on a set ? and define the equivalence class of an element ?∈? to be [?]?:={?∈?|???}. That is [?]?=?(?). Divide your proof into the following three peices: Prove that every partition block is nonempty and every element ? is in some block. Prove that if [?]?∩[?]?≠∅, then ???. Conclude that the sets [?]? for ?∈?...

Let X be a non-empty set and R⊆X × X be an equivalence relation. Prove that...

Let X be a non-empty set and R⊆X × X be an equivalence relation. Prove that X / R is a partition of X.

A tree is a circuit-free connected graph. A leaf is a vertex of degree 1 in...

A tree is a circuit-free connected graph. A leaf is a vertex of degree 1 in a tree. Show that every tree T = (V, E) has the following properties: (a) There is a unique path between every pair of vertices. (b) Adding any edge creates a cycle. (c) Removing any edge disconnects the graph. (d) Every tree with at least two vertices has at least two leaves. (e) | V |=| E | +1.

Question 1. Equivalence Relation 1 Define a relation R on by iff . Prove that R...

Question 1. Equivalence Relation 1 Define a relation R on by iff . Prove that R is an equivalence relation, that is, prove that it is reflexive, symmetric, and transitive. Determine the equivalence classes of this relation. What members are in the class [2]? How many members do the equivalence classes have? Do they all have the same number of members? How many equivalence classes are there? Question 2. Equivalence Relation 2 Consider the relation from last week defined as:...

Prove that cardinality is an equivalence relation. Prove for all properties (refextivity, transitivity and symmetry). Please...

Prove that cardinality is an equivalence relation. Prove for all properties (refextivity, transitivity and symmetry). Please do this problem and explain every step. The less confusing notation the better, thanks!

Determine whether the given relation is an equivalence relation on the set. Describe the partition arising...

Determine whether the given relation is an equivalence relation on the set. Describe the partition arising from each equivalence relation. (c) (x1,y1)R(x2,y2) in R×R if x1∗y2 = x2∗y1.

Given a directed graph, prove that there exists an Eulerian cycle that is also a hamiltonian...

Given a directed graph, prove that there exists an Eulerian cycle that is also a hamiltonian cycle if and only if the graph is a single cycle.

Subjects