Walks & Adjacency Matrices (DP IB Maths: AI HL)

Adjacency matrices are another way to represent graphs and connections between the different vertices.

What is an adjacency matrix?

• An adjacency matrix is a square matrix where all of the vertices in the graph are listed as the headings for both the rows () and columns ()
• An adjacency matrix can be used to show the number of direct connections between two vertices
• An entry of 0 in the matrix means that there is no direct connection between that pair of vertices
• In a simple graph the only entries are either 0 or 1
• A loop is indicated in an adjacency matrix with a value in the leading diagonal (the line from top left to bottom right)
• In an undirected matrix the value in the leading diagonal will be 2 because you can use the loop to travel out of and into the vertex in two different directions
• In a directed matrix, if the loop has been given a direction, the value in the leading diagonal will be 1 as you can only travel along the loop out of and back into the vertex in one direction
• For a graph with no loops every entry in the leading diagonal will be 0
• An undirected graph will be symmetrical in the leading diagonal
• The sum of the entries in a row is the in degree of that vertex
• The sum of the entries in a column is the out degree of that vertex

What is a walk?

• A walk is a sequence of vertices that are visited when moving through a graph along its edges
• Both edges and vertices can be revisited in a walk
• The length of a walk is the total number of edges that are traversed in the walk

How do you find the number of walks in a graph?

• Let M denote the adjacency matrix of a graph. The (i, j) entry in the matrix M^k will give the number of walks of length k from vertex i to vertex j
• If there is an entry of 2 in the leading diagonal of the matrix, this should be changed to a 1 before the matrix is raised to a power
• The number of walks, between vertex i and vertex j, of length n or less can be given by the matrix Sⁿ, where Sⁿ = M¹ + M² +…+…Mⁿ
• If all of the entries in a single row of Sⁿ are non-zero values then the graph is connected

A weighted adjacency table gives more detailed information about the connection between different vertices in a weighted graph.

What is a weighted adjacency table?

• A weighted adjacency table is different to an adjacency matrix as the value in each cell is the weight of the edge connecting that pair of vertices
• Weight could be cost, distance, time etc.
• An empty cell can be used to indicate that there is no connection between a pair of vertices
• A directed graph is not symmetrical along the leading diagonal (the line from top left to bottom right)
• When drawing a graph from its adjacency table be careful when labelling the edges
• For an un-directed graph the two cells between a specific pair of vertices will be the same so connect the vertices with one edge labelled with the relevant weight
• For a directed graph if the two cells between a specific pair of vertices have different values draw two lines between the vertices and label each with the correct weight and direction
• A weighted adjacency table can be used to work out the weight of different walks in the graph