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 ii, column jj is the number of edges joining vertex ii to vertex jj.

  • 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 AA, and two edges joining BB and CC.

Its adjacency matrix. The 1 in row AA, column AA is the loop; the 2s are the two edges joining BB and CC.
ABCDA1101B1021C0201D1110\begin{array}{c|cccc} & A & B & C & D \\ \hline A & 1 & 1 & 0 & 1 \\ B & 1 & 0 & 2 & 1 \\ C & 0 & 2 & 0 & 1 \\ D & 1 & 1 & 1 & 0 \end{array}

Constructing an adjacency matrix

  1. Label the rows and the columns

    Use the vertices in the same order for both.

  2. Work along each row

    For row ii, column jj, count the edges joining ii to jj. Write 0 if there are none.

  3. Enter loops on the leading diagonal

    Each loop at a vertex counts 1 in that vertex's diagonal entry.

  4. 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 PP, QQ and RR. Its edges are PQPQ, two separate edges joining PP and RR, and a loop at QQ. Construct its adjacency matrix, with rows and columns in the order PP, QQ, RR.

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

  • Simple familiar

Construct the adjacency matrix for the graph shown.

5 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Label the rows and columns with the vertices, in the same order.

  2. Each entry is the number of edges joining the row vertex to the column vertex; a loop is entered as 1.

  3. Check the matrix is symmetric and that the edge count matches the drawing.

Watch out for

  • Entering the loop as 2. The degree of AA 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 ii, column jj is the number of arcs from ii to jj: 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 QQ and SS is two-way, so it carries an arrow each way.

Rows are "from", columns are "to". The two-way street gives a 1 in row QQ, column SS and a 1 in row SS, column QQ.
PQRSP0100Q0011R0001S1100\begin{array}{c|cccc} & P & Q & R & S \\ \hline P & 0 & 1 & 0 & 0 \\ Q & 0 & 0 & 1 & 1 \\ R & 0 & 0 & 0 & 1 \\ S & 1 & 1 & 0 & 0 \end{array}

In the matrix of the one-way streets, what does the 1 in row SS, column PP mean?

Choose one answer
Interactive

One-way streets

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 ii, column jj means that many arrows from ii to jj.

Worked example

Drawing a digraph from its adjacency matrix

  • Simple familiar

Four netball teams — Kelvin Grove (KK), Mitchelton (MM), Nundah (NN) and Sandgate (SS) — played a round-robin. In the matrix, the entry in row ii, column jj is 1 if team ii beat team jj.

KMNSK0110M0011N0001S1000\begin{array}{c|cccc} & K & M & N & S \\ \hline K & 0 & 1 & 1 & 0 \\ M & 0 & 0 & 1 & 1 \\ N & 0 & 0 & 0 & 1 \\ S & 1 & 0 & 0 & 0 \end{array}

(a) Draw the digraph of the results.

(b) How many games were played?

(c) Which teams won the most games?

4 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Draw one vertex for each row label.

  2. Digraph: an entry aa in row ii, column jj means aa arrows from ii to jj.

  3. 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?

WXYZW0210X2011Y1110Z0100\begin{array}{c|cccc} & W & X & Y & Z \\ \hline W & 0 & 2 & 1 & 0 \\ X & 2 & 0 & 1 & 1 \\ Y & 1 & 1 & 1 & 0 \\ Z & 0 & 1 & 0 & 0 \end{array}

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 ii, column jj counts arcs from ii to jj, 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.

Lesson 3 of 80% read

Save your progress with a free account