3
$\begingroup$

I have encountered a problem while doing exercises in my text book.

The question is to write down the Adjacency list and the adjacency matrix for the directed cycle with 4 vertices and directed wheel with 5 vertices in total

If you could give me some help, it would be greatly appreciated :)

  • 1
    This should be easy, *if* you know the definitions of those types of graph and of the adjacency matrix. Where do you have problems / what concept do you not understand?2012-08-12

1 Answers 1

4

This is the directed cycle with $4$ vertices:

Directed cycle with <span class=4 vertices">

This is the directed wheel with $5$ vertices in total:

Directed wheel with <span class=5 vertices">

[I'm assuming the definition here. There might be other definitions, but the process is still the same.]

To write down an adjacency list or adjacency matrix, we need to give the vertices labels. The labels are arbitrary, but it's usually easier to choose labels such as $1,2,\ldots,n$. So let's label the vertices as follows:

Directed cycle with <span class=4 labelled vertices">

and

Directed wheel with <span class=5 labelled vertices">

An adjacency list is simply a list of the edges in the graph. We can just read these from the above drawings:

  • The adjacency list for directed cycle with $4$ vertices has adjacency list is $(1,2),(2,3),(3,4),(4,1)$.
  • The adjacency list for directed wheel with $5$ vertices has adjacency list is $(1,2),(2,3),(3,4),(4,1),(5,1),(5,2),(5,3),(5,4)$.

Note: these are directed edges, so e.g. $(5,1)$ is different to $(1,5)$.

The adjacency matrix of a directed graph $G$ is a $(0,1)$-matrix with a $1$ in cell $(i,j)$ whenever $(i,j)$ is an edge in $G$ (and $0$ otherwise).

  • The adjacency matrix for directed cycle with $4$ vertices is

$\begin{array}{|cccc|} \hline 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ \hline \end{array}.$

  • The adjacency matrix for directed wheel with $5$ vertices is

$\begin{array}{|ccccc|} \hline 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 \\ \hline \end{array}.$

One caveat: the adjacency list and adjacency matrix will change depending on which way you label the vertices.