Topics
Adjacency matrix for a directed graph
AHL AI 3.15
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.
Adjacency matrix of undirected graph
AHL AI 3.15
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.
Degree of a vertex from adjacency matrix
AHL AI 3.15
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.
Walks
AHL AI 3.15
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.
Trails
AHL AI 3.15
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.
Paths
AHL AI 3.15
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.
Circuit
AHL AI 3.16
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.
Cycle
AHL AI 3.16
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.
Counting walks by exponentiating adjacency matrix
AHL AI 3.15
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
A=⎝⎜⎜⎛0100100110001001⎠⎟⎟⎞
Let's consider the walks of length 5:
A5=⎝⎜⎜⎛3203530521025305⎠⎟⎟⎞
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:
Skills covered
Exercises checked off
I'm Plex, here to help you understand this concept!