Definition 5

Let G be a graph. The graph whose elements are the ordered pairs $(x, y)$ such that $(y, x) \in \mathrm{G}$ is called the inverse of G and is denoted by $\overset{-1}{\mathrm{G}}$.

For every set X, $\overset{-1}{\mathrm{G}}\langle\mathrm{X}\rangle$ is called the inverse image of X under G.

¶ It is clear that the inverse of $\overset{-1}{\mathrm{G}}$ is G, and that

In particular, if X, Y are two sets, we have

A graph G is said to be symmetric if $\overset{-1}{\mathrm{G}} = \mathrm{G}$.

¶ Let $\Gamma = (\mathrm{G}, \mathrm{A}, \mathrm{B})$ be a correspondence between A and B. Since $\mathrm{pr}_1\overset{-1}{\mathrm{G}} \subset \mathrm{B}$ and $\mathrm{pr}_2\overset{-1}{\mathrm{G}} \subset \mathrm{A}$, the triple $(\overset{-1}{\mathrm{G}}, \mathrm{B}, \mathrm{A})$ is a correspondence between B and A, called the inverse of the correspondence $\Gamma$, and denoted by $\overset{-1}{\Gamma}$. For every subset Y of B, the image $\overset{-1}{\Gamma}\langle\mathrm{Y}\rangle$ of Y under $\overset{-1}{\Gamma}$ is also called the inverse image of Y under $\Gamma$. Clearly the inverse of $\overset{-1}{\Gamma}$ is $\Gamma$.