Directed Graph Representing the Inverse Relation

Directed Graph Representing the Inverse Relation
$\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).

$\endgroup$
2

1 Answer

$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Alexander Ross
Author

Alexander Ross

Alexander Ross has covered the video game industry for a decade, writing deep dives on game design, esports tournaments, VR developments, and gaming culture.