What is the structure of a directed graph with vertex set A which has a relation R

42 Views Asked by At

I am studying for a test and found this question in the book: Let $R$ be an equivalence relation on the set A (Non-empty). Let $D_R$ be the directed graph with vertex set $A$ and an arc from $x$ to $y$ iff $(x,y) \in R$. Describe $D$ in terms of how many components it has, and what is the structure of each component?

My solution is:

Let $R$ be an equivalence relation on A. Then $D$ could have isolated vertices, but each of these isolated vertices would have a cycle of length one, directed back toward itself. Every vertex such that $(x,y) \in R$ will have 2-directional arcs between $x$ and $y$ (one from $x$ to $y$ and the other from $y$ to $x$). All vertices will also have a cycle of length one directed back toward itself.

For every two vertices $(x,y) \in R$ and $(y,z) \in R$ there will be $(x,z) \in R$ with two directional arcs between $x$ and $z$

I think it's right, but I am not sure. Also I don't know what else I can say about the dimensions of D

1

There are 1 best solutions below

2
On

You’ve missed the main thing that the question was probably designed to elicit: $D$ has one component for each equivalence class of $R$. Beyond that you can say that if $C$ is an equivalence class of $R$, the component of $D$ corresponding to it has is the complete graph on the vertex set $C$ together with a loop at each vertex.