# Graph Theory - Finding Relation

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$?

-
I need some kind of Hint to understand and start the problem , –  Node.JS Dec 13 '12 at 16:57
Do you know the definitions of the terms in question? –  dtldarek Dec 13 '12 at 17:00
Yes , I know, But I don't understand a question completely –  Node.JS Dec 13 '12 at 17:05
Then start by applying the definition of "reflexive" to $R$, to see if $R$ satisfies the definition. –  Chris Eagle Dec 13 '12 at 17:07
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). –  alancalvitti Dec 13 '12 at 17:11

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.
• 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$.