Let $R$ be a relation on a set $A$. Explain how to use the directed graph representing $R$ to obtain the directed graph representing the inverse relation $R^{-1}$ ($R$ inverse).
directed graph representing the inverse relation
-
0Have $y$ou tried making up a simple example to see what happens? – 2011-10-21
1 Answers
You probably mean the following graphical representation of a relation $R$ on a set $A$:
We take the graph which has elements of $A$ as nodes and $R$ is the set of edges. This is the same as saying that there is an arrow from $a$ to $b$ if and only if $(a,b)\in R$.
Recall that inverse relation is defined as $R^{-1}=\{(a,b); (b,a)\in R\}$. This means that
$(a,b)\in R^{-1} \qquad \Leftrightarrow \qquad (b,a)\in R.$
In our graphical representation this means that there is an arrow from $a$ to $b$ in the graph for $R^{-1}$ if and only if in the original graph there was an arrow from $b$ to $a$. Thus the only thing to do is to reverse the direction of arrows.
For example, let us have a look at the relation $<$ on the set $A=\{1,2,3\}$. In this case relation consists of these ordered pairs: $R=\{(1,2),(1,3),(2,3)\}$. Then $R^{-1}=\{(2,1),(3,1),(3,2)\}$. Notice that this is precisely the relation $>$ on the same set.
You can get a different graphical representation by drawing two copies of the set $A$ and drawing the arrows between $a$ in the left copy and $b$ in the right copy if $(a,b)\in R$. Note that this works for relation between different set $A$ and $B$, too. This visualization is particularly suitable if you want to find composition of two relations.