Lesson 3 of 8 · 16 min
Adjacency matrices
Store a graph or digraph as an adjacency matrix, read degrees and edge counts from the matrix, and draw the graph that a matrix describes.
What you will be able to do
- Construct the adjacency matrix of a graph, including loops and multiple edges.
- Construct the adjacency matrix of a digraph, reading rows as "from" and columns as "to".
- Draw the graph or digraph that an adjacency matrix describes.
- Use an adjacency matrix to find degrees and to count edges.
A drawing of a network is easy for people to read but no use to a computer. A navigation app stores its road network as a table of numbers instead: for each pair of places, how many direct connections there are.
That table is an adjacency matrix — the kind of matrix you used in Unit 2 to store links in a social or road network.
Definition
Adjacency matrix
The adjacency matrix of a graph is a square matrix with one row and one column for each vertex, in the same order. The entry in row , column is the number of edges joining vertex to vertex .
- A loop is one edge joining a vertex to itself, so it is entered as 1 on the leading diagonal.
- Two vertices with no edge between them get a 0.
A loop at , and two edges joining and .
Constructing an adjacency matrix
Label the rows and the columns
Use the vertices in the same order for both.
Work along each row
For row , column , count the edges joining to . Write 0 if there are none.
Enter loops on the leading diagonal
Each loop at a vertex counts 1 in that vertex's diagonal entry.
Check
A graph without arrows gives a symmetric matrix. The entries above the leading diagonal plus the diagonal entries should add to the number of edges.
A graph has vertices , and . Its edges are , two separate edges joining and , and a loop at . Construct its adjacency matrix, with rows and columns in the order , , .
Key idea
Reading a graph from its matrix
- The matrix of a graph without arrows is symmetric about the leading diagonal.
- A simple graph's matrix has only 0s and 1s, with 0s down the leading diagonal.
- Number of edges = the entries above the leading diagonal + the diagonal entries (the loops).
- Degree of a vertex = its row sum, plus 1 for each loop — a loop adds 2 to the degree but only 1 to the row.
Worked example
Constructing an adjacency matrix
Construct the adjacency matrix for the graph shown.
Step 1: Label the rows and the columns
Use the same order for both: . The entry in row , column is the number of edges joining vertex to vertex .
Step 2: Fill in row A
to : one loop, so enter 1. to : 1. to : 0. to : 1. Row is .
A loop is one edge joining to itself, so it is entered as 1. (QCAA marks a loop entered as 1.)
Step 3: Fill in rows B, C and D
Row : , because two edges join and . Row : . Row : .
Step 4: Write the matrix and check its symmetry
The matrix is symmetric about the leading diagonal, as it must be for a graph without arrows.
An edge joining and also joins and , so the entry in row , column equals the entry in row , column .
Step 5: Check the number of edges
Entries above the leading diagonal: edges between different vertices. The diagonal adds 1 loop. That makes 7 edges, matching the drawing. ✓
Try it yourself first, then check the working one step at a time.
Answer
Method
Label the rows and columns with the vertices, in the same order.
Each entry is the number of edges joining the row vertex to the column vertex; a loop is entered as 1.
Check the matrix is symmetric and that the edge count matches the drawing.
Watch out for
Entering the loop as 2. The degree of counts the loop twice, but the matrix counts edges, so the entry is 1.
Entering 1 for the pair of edges between B and C instead of 2.
Definition
The adjacency matrix of a digraph
For a digraph, the entry in row , column is the number of arcs from to : rows are "from" and columns are "to". The matrix is usually not symmetric, and the sum of all its entries is the number of arcs.
One-way streets around a block. The street between and is two-way, so it carries an arrow each way.
In the matrix of the one-way streets, what does the 1 in row , column mean?
Each arrow is a 1 in the matrix: its row is where the arrow starts and its column is where it ends.
From a matrix back to a graph. Draw one vertex for each row.
- For a graph without arrows, read only the entries on and above the leading diagonal. An entry of 2 above the diagonal means two edges; a diagonal entry means that many loops.
- For a digraph, read every entry: an entry in row , column means that many arrows from to .
Worked example
Drawing a digraph from its adjacency matrix
Four netball teams — Kelvin Grove (), Mitchelton (), Nundah () and Sandgate () — played a round-robin. In the matrix, the entry in row , column is 1 if team beat team .
(a) Draw the digraph of the results.
(b) How many games were played?
(c) Which teams won the most games?
Step 1: Draw the vertices
One vertex for each team: , , and .
Step 2: Turn each 1 into an arrow from the row team to the column team
Row gives arrows and . Row gives and . Row gives . Row gives .
Rows are "from" and columns are "to". A 1 in row , column means beat , so the arrow points from to .
Step 3: Count the games
Each 1 is one game: games. Check: a round-robin of 4 teams has games. ✓
Step 4: Find the most wins
The row sums are the wins: 2, 2, 1, 1. Kelvin Grove and Mitchelton each won 2 games.
Try it yourself first, then check the working one step at a time.
Answer
(a) Arrows , , , , and . (b) 6 games. (c) Kelvin Grove and Mitchelton, with 2 wins each.
Method
Draw one vertex for each row label.
Digraph: an entry in row , column means arrows from to .
Graph without arrows: read the entries on and above the leading diagonal; each is that many edges, and a diagonal entry is a loop.
Watch out for
Drawing the arrows from the column team to the row team, which reverses every result.
Putting arrowheads at both ends — that would mean each team beat the other.
The digraph for the worked example. Each arrow points from the winner to the loser.
The adjacency matrix of a graph is shown. How many edges does the graph have?
Common mistake
Three matrix slips
- Entering a loop as 2. The matrix counts edges, and a loop is one edge, so enter 1. (Its contribution to the degree is 2.)
- Reading a digraph's matrix the wrong way round. Rows are "from", columns are "to". Check one arrow against the drawing.
- Adding every entry to count edges. For a graph without arrows that counts each edge twice; use the entries on and above the leading diagonal.
Exam tip
Label the rows and the columns, in the same order — QCAA marking guides reward a matrix "with same horizontal and vertical labels". For a digraph, state how you read it: "rows: from, columns: to".
Summary
The adjacency matrix has one row and one column per vertex, in the same order; each entry is the number of edges joining the row vertex to the column vertex.
A loop is entered as 1 on the leading diagonal; multiple edges give entries of 2 or more.
A graph without arrows has a symmetric matrix. Edges = entries above the diagonal + diagonal entries; degree = row sum + 1 for each loop.
For a digraph, row , column counts arcs from to , and the sum of all entries is the number of arcs.
To draw a graph from its matrix, turn each entry into that many edges, loops or arrows.
Finished the lesson?
Try the 3 quick checks above and the lesson completes itself, or mark it complete now.