Question

a) Describe three different methods that can be used torepresent a graph.

b) Draw a simple graph with at least five vertices andeight edges. Illustrate how it can be represented using the methods you described in part (a).

Short answer

1. Adjacent lists, adjacency matrix, and incidence matrix are the three ways or methods that can be used to represent a graph.

2. The example is illustrated below

Step-by-step solution

Step 1: The methods to represent a graph

To represent a graph we can use:

Adjacency lists: Contains each vertex of the graph and a list of which other vertices each is adjacent to.

Adjacency matrix: A matrix of the form

\(({a_{ij}}) = \left\{ \begin{array}{l}1\;if\;({v_i},{v_j}) \in E\\0\;otherwise\end{array} \right.\)

Incident matrix: A matrix of the form

\(({b_{ij}}) = \left\{ \begin{array}{l}1\;if\;{e_j}\;is\;incident\;to\;{v_i}\\0\;otherwise\end{array} \right.\)

Step 2: Design and representation of a graph

We will consider \({K_5}\)

In the adjacency list, clearly, each vertex is just listed with all the other vertices (not including itself)

The adjacency matrix looks as follows

\(\left( {\begin{array}{*{20}{c}}0&1&1&1\\1&0&1&1\\1&1&0&1\\\begin{array}{l}1\\1\end{array}&\begin{array}{l}1\\1\end{array}&\begin{array}{l}1\\1\end{array}&\begin{array}{l}1\\0\end{array}\end{array}} \right)\)

The incidence matrix looks as follows

\(\left( {\begin{array}{*{20}{c}}1&1&1&1\\1&0&1&1\\1&1&0&1\\\begin{array}{l}1\\1\end{array}&\begin{array}{l}1\\1\end{array}&\begin{array}{l}1\\1\end{array}&\begin{array}{l}1\\0\end{array}\end{array}\;\;\;\begin{array}{*{20}{c}}0&0&0&0\\1&1&1&0\\0&0&1&1\\\begin{array}{l}0\\1\end{array}&\begin{array}{l}1\\0\end{array}&\begin{array}{l}0\\0\end{array}&\begin{array}{l}0\\1\end{array}\end{array}\;\;\;\;\begin{array}{*{20}{c}}\begin{array}{l}0\\0\\1\\1\\0\end{array}&\begin{array}{l}0\\0\\0\\1\\1\end{array}\end{array}} \right)\)