-1
$\begingroup$

Let $G = (V,E)$ be a simple and an undirected graph. Define a relation $R$ on the vertices of $G$ as follows: for two nodes $u$ and $v$, $(u,v) \in R$ if and only if there is a path from $u$ to $v$ in $G$.

a. Determine if $R$ is reflexive, symmetric, anti-symmetric, transitive or total.

b. Why is $R$ an equivalence relation?

c. Suppose $G$ is the graph below. What are the equivalence classes of $R$?

sample graph

  • 0
    @dtldarek, understood - that's called the reflexive closure as I mentioned (think of the adjacency matrix).2012-12-13

1 Answers 1

3

The problem you presented is a very basic one, therefore you will get only very basic and general hints.

Hints:

a.

  • Is $R$ reflexive?
  • Check definition on Wikipedia or even better Wolfram.
  • $R$ is reflexive if (by definition) $\forall v \in V.\ (v,v) \in R$.
  • $R$ is reflexive, because each vertex is connected with itself by a path of length 0 (zero).
  • proceed in similar way with symmetry, anti-symmetry, transitivity and totality.

b.

  • Is $R$ an equivalence relation?
  • Check definition here or here.
  • Answer using point (a).

c.

  • Calculate all the elements that are in relation with $a$.
  • Calculate all the elements that are in relation with $b$.
  • Calculate all the elements that are in relation with $e$.
  • Observe, analyze, argue, answer.

I hope it will help you.

P.S. Please understand, this problem is elementary and it would be best if you would solve it by yourself!