An adjacency matrix is a matrix or table that shows the possible movements between vertices on a graph.
Each row is a starting vertex, and each column an ending vertex. The nth row and jth column contains
0 if there is no edge from vertex n to vertex j
1 for each edge from n to j.
Note that the rows and columns are usually ordered alphabetically.
The following table shows a few examples of what each cell represents.
An adjacency matrix for an undirected graph is necessarily symmetric long its main diagonal, since every edge is two-way.
In this case, a self edge counts double because it contributes 1 towards both the start and finish.
We can read the degree of a vertex from an adjacency matrix by adding up the values in the relevant row / column.
Undirected graph
An undirected graph is symmetric, so we can look add up a row or column to find the degree.
In the above adjacency matrix, vertex A has degree 1+2+0=3.
Directed graph
Vertices on directed graphs have an in-degree and out-degree.
Since the rows show the source vertex, adding up a row gives the out-degree of a vertex. Adding up a column gives the in-degree of a vertex.
In the above adjacency matrix, vertex A has out-degree 1+0+0=1, and in-degree 1+1+1=3.
A walk is a sequence of valid moves on a graph, going from vertex to vertex along edges that allow movement in that direction.
The walk ACDC is shown on an undirected graph above.
The walk ABBA on a directed graph. Notice how the dashed edges are numbered to indicate the order they are in the walk.
A trail is a special type of walk where no edges are repeated.
There is no restriction on whether vertices can be repeated.
The walk above is a trail because no edge is walked more than once.
The walk above is not a trail because AE is walked twice.
A path is an even more special type of walk where no edges or vertices are repeated.
The walk above is a path.
The walk above is not a path, since A is visited twice.
A circuit is a special type of walk that starts and ends at the same vertex and does not reuse any edges.
The walk above is not a circuit, since it does not start and end at the same place.
The walk above is a circuit.
The walk above is a circuit.
Repeats DB so not a circuit.
A cycle is a special case of a circuit where no vertex, except the last one, is repeated.
Every cycle is a circuit, but not every circuit is a cycle.
The walk above is a cycle.
Vertex A repeated in the middle so not a cycle, though it is a circuit.
By raising the adjacency matrix to the power of k, we can find the number of possible walks with length k between any two vertices.
The graph on the left has the adjacency matrix
Let's consider the walks of length 5:
To count the number of length 5 walks that start at A and end at A, we look at the row for A (first row) and the column for D, where we see a 5.
The process is the same for an undirected graph, except that the adjacency matrix will be symmetric.
Nice work completing Adjacency matrices & walks, here's a quick recap of what we covered:
Exercises checked off
An adjacency matrix is a matrix or table that shows the possible movements between vertices on a graph.
Each row is a starting vertex, and each column an ending vertex. The nth row and jth column contains
0 if there is no edge from vertex n to vertex j
1 for each edge from n to j.
Note that the rows and columns are usually ordered alphabetically.
The following table shows a few examples of what each cell represents.
An adjacency matrix for an undirected graph is necessarily symmetric long its main diagonal, since every edge is two-way.
In this case, a self edge counts double because it contributes 1 towards both the start and finish.
We can read the degree of a vertex from an adjacency matrix by adding up the values in the relevant row / column.
Undirected graph
An undirected graph is symmetric, so we can look add up a row or column to find the degree.
In the above adjacency matrix, vertex A has degree 1+2+0=3.
Directed graph
Vertices on directed graphs have an in-degree and out-degree.
Since the rows show the source vertex, adding up a row gives the out-degree of a vertex. Adding up a column gives the in-degree of a vertex.
In the above adjacency matrix, vertex A has out-degree 1+0+0=1, and in-degree 1+1+1=3.
A walk is a sequence of valid moves on a graph, going from vertex to vertex along edges that allow movement in that direction.
The walk ACDC is shown on an undirected graph above.
The walk ABBA on a directed graph. Notice how the dashed edges are numbered to indicate the order they are in the walk.
A trail is a special type of walk where no edges are repeated.
There is no restriction on whether vertices can be repeated.
The walk above is a trail because no edge is walked more than once.
The walk above is not a trail because AE is walked twice.
A path is an even more special type of walk where no edges or vertices are repeated.
The walk above is a path.
The walk above is not a path, since A is visited twice.
A circuit is a special type of walk that starts and ends at the same vertex and does not reuse any edges.
The walk above is not a circuit, since it does not start and end at the same place.
The walk above is a circuit.
The walk above is a circuit.
Repeats DB so not a circuit.
A cycle is a special case of a circuit where no vertex, except the last one, is repeated.
Every cycle is a circuit, but not every circuit is a cycle.
The walk above is a cycle.
Vertex A repeated in the middle so not a cycle, though it is a circuit.
By raising the adjacency matrix to the power of k, we can find the number of possible walks with length k between any two vertices.
The graph on the left has the adjacency matrix
Let's consider the walks of length 5:
To count the number of length 5 walks that start at A and end at A, we look at the row for A (first row) and the column for D, where we see a 5.
The process is the same for an undirected graph, except that the adjacency matrix will be symmetric.
Nice work completing Adjacency matrices & walks, here's a quick recap of what we covered:
Exercises checked off