Q4

Let us define the relation \(\sim\) over \(V\) in a graph \(G = (V, E)\), such that \(u \sim v\), if there is a path from \(u\) to \(v\). (Note that there always exists a path of length zero for each node)
  1. Show that \(\sim\) is an equivalence relation.
  2. Describe in your own words the equivalence classes of \(\sim\) (see e.g. Def. 17.1 in Antonsen's book).

Answer

Show that the relation  \(\sim\) is an equivalence relation

Equivalence relations are reflexive, symmetric and transitive.
  1. The relation  \(\sim\) is reflexive, because there will always exist a \(u \sim u\) of value 0. A node will always have a path of length 0 from itself to itself.
  2. The relation  \(\sim\) is symmetric, because paths are undirected. If there is a path from \(u\) to \(v\), there is also a path from \(v\) to \(u\).
  3. The relation  \(\sim\) is transitive, because if there is a path from \(a\) to \(b\), and from \(b\) to \(c\), there will also be a path from \(a\) to \(c\), through \(b\).
The relation  \(\sim\) is an equivalence relation because it is reflexive, symmetric and transitive.

The equivalence classes of \(\sim\)

The equivalence classes of \(\sim\) are:
  1. The set of elements in \(V\) that are related to the element \(v\) in \(V\). The element \(v\) exists in \(V\), and the set \(u\) is an element of \(V\) and is related to \(u\).