Walks & Adjacency Matrices
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
Worked example
Let G be the graph below.
Write down the adjacency matrix for G.