Question

(a) Draw the directed graph representing the relation \(\left( {\begin{array}{*{20}{l}}1&0&1\\0&1&0\\1&0&1\end{array}} \right)\).

(b) Draw the directed graph representing the relation \(\left( {\begin{array}{*{20}{l}}0&1&0\\0&1&0\\0&1&0\end{array}} \right)\).

(c) Draw the directed graph representing the relation \(\left( {\begin{array}{*{20}{l}}1&1&1\\1&0&1\\1&1&1\end{array}} \right)\).

Short answer

(a) The graph represented by the relation \(\left( {\begin{array}{*{20}{l}}1&0&1\\0&1&0\\1&0&1\end{array}} \right)\) is

(b) The graph represented by the relation \(\left( {\begin{array}{*{20}{l}}0&1&0\\0&1&0\\0&1&0\end{array}} \right)\) is

(c) The graph represented by the relation \(\left( {\begin{array}{*{20}{l}}1&1&1\\1&0&1\\1&1&1\end{array}} \right)\) is

Step-by-step solution

Given data

The given relations are \(\left( {\begin{array}{*{20}{l}}1&0&1\\0&1&0\\1&0&1\end{array}} \right)\), \(\left( {\begin{array}{*{20}{l}}0&1&0\\0&1&0\\0&1&0\end{array}} \right)\) and \(\left( {\begin{array}{*{20}{l}}1&1&1\\1&0&1\\1&1&1\end{array}} \right)\).

Concept used

A relation\({\rm{R}}\)from\(A = \left\{ {{a_1},{a_2}, \ldots ,{a_m}} \right\}\)to\(B = \left\{ {{b_1},{b_2}, \ldots ,{b_n}} \right\}\)can be represented by the matrix\({M_R} = \left( {{m_{ij}}} \right)\), where\({m_{ij}} = \left\{ {\begin{array}{*{20}{l}}{1{\rm{ if }}\left( {{a_i},{b_j}} \right) \in R}\\{0{\rm{ if }}\left( {{a_i},{b_j}} \right) \notin R}\end{array}} \right.\)

The relation\({\rm{R}}\)on a set\({\rm{A}}\)can be represented by a directed graph which has the elements of\({\rm{A}}\)as its vertices and the ordered pairs\((a,b)\), where\((a,b) \in R\), as edges.

Draw the directed graph represented by the relation \(\left( {\begin{array}{*{20}{l}}1&0&1\\0&1&0\\1&0&1\end{array}} \right)\)

(a)

The given matrix is \(\left( {\begin{array}{*{20}{l}}1&0&1\\0&1&0\\1&0&1\end{array}} \right)\).

The relation is on the set \(\{ 1,2,3\} \), thus draw three points (one point for 1, one point for 2, one point for 3).

All elements on the main diagonal are 1, which means that draw a loop at each point.

The only other nonzero elements are \({a_{13}}\) and \({a_{31}}\) which means that draw an arrow from point 1 to point 3 and an arrow from point 3 to point 1 in figure 1 as follows:

Figure 1

Draw the directed graph represented by the relation \(\left( {\begin{array}{*{20}{l}}0&1&0\\0&1&0\\0&1&0\end{array}} \right)\)

(b)

The given matrix is \(\left( {\begin{array}{*{20}{l}}0&1&0\\0&1&0\\0&1&0\end{array}} \right)\).

The relation is on the set \(\{ 1,2,3\} \), thus draw three points (one point for 1, one point for 2, one point for 3).

The only nonzero element on the main diagonal is \({a_{22}}\), which means that draw a loop at point 2.

The other nonzero elements are \({a_{12}}\) and \({a_{32}}\) which means that draw an arrow from point 1 to point 2 and an arrow from point 3 to point 2 in figure 2 as follows:

Figure 2

Draw the directed graph represented by the relation \(\left( {\begin{array}{*{20}{l}}1&1&1\\1&0&1\\1&1&1\end{array}} \right)\)

(c)

The given matrix is \(\left( {\begin{array}{*{20}{l}}1&1&1\\1&0&1\\1&1&1\end{array}} \right)\).

The relation is on the set \(\{ 1,2,3\} \), thus draw three points (one point for 1, one point for 2, one point for 3).

The only non-zero element on the main diagonal are \({a_{11}}\) and \({a_{33}}\), which means that draw a loop at point 1 and at point 3.

The other nonzero elements are \({a_{12}},{a_{13}},{a_{21}},{a_{23}},{a_{31}},{a_{32}}\).

For each of the non-zero elements \({a_{ij}}\), draw an arrow from point \(i\) to point \(j\) in figure 3 as follows:

Figure 3