Maths with David

    IBDP. AI. HL. Graph Theory. Adjacency Matrices

    An adjacency matrix is a matrix which shows how the nodes of a network are connected. We will consider the graph below:

    In this graph, the vertices A, B, C, D and E represent road intersections, with the edges representing roads that are either one-way or two-way.

    The adjacency table below shows the number of 1-step routes between the vertices:

    The adjacency matrix for this graph is therefore: \bold{A} = \begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \end{pmatrix}

    Worked Example 1

    Find the adjacency matrix for each of the below graphs:

    Multi-Step Routes – Investigation

    Let’s consider again the graph below, which has adjacency matrix \bold{A} = \begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \end{pmatrix} :

    Consider a table for the 2-step routes between vertices. There are two 2-step routes from A to D (i.e. A -> B -> D or A -> E -> D), so we put a 2 in the table below:

    1. Find the 2-step routes from E to A and hence find the value of the entry shaded pink above.
    2. Complete the rest of the table.
    3. Find the matrix A2
    4. Predict the meaning of A3 and A4. Check your prediction by finding appropriate routes on the graph.

    We conclude the investigation by summarising that if a graph has 1-step adjacency matrix A, then:

    • A2 is the adjacency matrix for the 2-step routes
    • A3 is the adjacency matrix for the 3-step routes
    • An is the adjacency matrix for the n-step routes.

    Worked Example

    Consider the graph below:

    1. Find the adjacency matrix A.
    2. Find A + A2
    3. Explain the significance of A + A2
    4. For this graph, how many steps do you need, to be able to travel from any vertex to any other vertex? Explain your answer.

    Exercise

    Answers