0
$\begingroup$

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).

  • 0
    Have $y$ou tried making up a simple example to see what happens?2011-10-21

1 Answers 1

1

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.

R a R^-1

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.

R a R^-1