11. Representing relations

Representing relations

Let $A=\{1,2,3,4\}$ and take the following relation $R$ on $A$:

$$R=\{(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,4),(3,3)\}$$

$R$ can be represented by a directed graph:

digraph G {
  1->1,2,3,4
  2->1,2,4
  3->3
}

Alternatively we can use a 0-1 matrix:

$$\begin{array}{cc}& \begin{array}{cccc}1& 2& 3& 4\end{array}\\ \begin{array}{c}1\\ 2\\ 3\\ 4\end{array}& \left[\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& 0& 1\\ 0& 0& 1& 0\\ 0& 0& 0& 0\end{array}\right]\end{array}$$