Adjacency Matrices

Stage 23 of 23 Strand 2 of 5 3 lessons

3 illustrated lessons, each teaching the why before the how.

Jump to a lesson

The Adjacency Matrix #

A square of ones and zeros for the edges.

An adjacency matrix holds, in row i and column j, the number of edges joining those vertices

Every pair of vertices is either joined or not, and that is all a graph records.

Write 1 where a pair is joined and 0 where it is not: the adjacency table.

Row A, column B holds 1 because the edge from A to B is there.

Take the labels off and the numbers stand alone: the adjacency matrix.

The matrix is symmetric across the main diagonal, because an edge joins both ways at once.

Row C adds to 3, and 3 is the degree of C. A row total is always a degree.

Now you

What is the degree of vertex C?

What goes in row A, column B of the adjacency matrix?

The nth power counts the walks of length n.

Row i, column j of the nth power of an adjacency matrix counts the walks of length n

One walk of length 2 runs from A to D: A to C, then C to D.

The adjacency matrix counts the walks of length 1, which are the edges themselves.

Multiply the matrix by itself. Row A, column D holds 1: one walk of length 2.

Row C, column C holds 3, because you can go out to A, B or D and straight back.

Row C, column D holds 0: the only neighbor of D is C, and there is no edge from C to C.

Adding the two matrices counts walks of length 2 or less: C to D gives 1.

Now you

What does row B, column C of the cube of this matrix count?

What does row D, column B of the cube of this matrix count?

The weight sits where the one used to.

A weighted graph carries a number on each edge, and its table stores that number in place of a 1

Each edge carries a weight: a distance, a cost, or a time.

The table holds the weight where an edge exists, and a dash where none does.

Row B, column D holds 6, so the edge from B to D costs 6.

Row D, column B holds 6 as well: the same edge has the same weight from either end.

A route costs the sum of the weights along it, so A to B to D costs 4 + 6 = 10.

Now you

What does the route A to C to D cost?

Which route from A to E is cheaper?