-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
    I need some kind of Hint to understand and start the problem ,2012-12-13
  • 1
    Do you know the definitions of the terms in question?2012-12-13
  • 0
    Yes , I know, But I don't understand a question completely2012-12-13
  • 0
    Then start by applying the definition of "reflexive" to $R$, to see if $R$ satisfies the definition.2012-12-13
  • 0
    For example, $R$ would be reflexive if there is a path from each node to itself $(u,u) \in R$. (If you ask me, that would require the graph to have loops. Ie, the graph adjacency matrix should contain the diagonal. Often there's an implicit switch from the graph to its reflexive closure).2012-12-13
  • 0
    @alancalvitti If you consider the points $b$ and $c$, I think the author intention was that $v$ is connected with itself with a path of length zero.2012-12-13
  • 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!