Counting paths with restrictions | Year 11

01 / LEARN

The idea, step by step

Start with a clear counting question

Specify the start, finish, number of steps and any repetition restriction. Branch by the first step, then list later choices in a tree or table. Systematic organisation avoids missing routes or counting the same route twice.

A direct edge uses one step regardless of its physical distance. A two-edge question is not asking for every way of eventually reaching the destination. If revisiting is forbidden, remove already used vertices from each branch.

An adjacency power counts walks

With rows as starting vertices and columns as destinations, $a_{i j}$ counts direct edges from $i$ to $j$ . Entry ${(A^{2})}_{i j}$ counts two-edge walks by summing possible intermediate vertices. Entry ${(A^{k})}_{i j}$ counts walks using exactly $k$ edges.

Matrix powers allow repeated vertices unless the network itself prevents them. They do not automatically count simple paths. A positive diagonal in $A^{2}$ can mean leaving a vertex and returning after two steps; it does not necessarily mean there is a loop.

A common trap

An entry of $A^{k}$ always counts no-repeated-vertex routes.

Instead: It counts walks; repetition requires separate checking.

02 / WORKED EXAMPLES

See the thinking

Example 1

Use the middle vertex

Rows and columns are A, B, C. For $A = (\begin{array}{cccccccccc} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array})$ , count two-edge walks from A to C.

Multiply row A $(0, 1, 1)$ by column C ${(1, 1, 0)}^{T}$ .
$0 (1) + 1 (1) + 1 (0) = 1$ .
The walk is A→B→C.

1 walk.

Example 2

Check a no-revisit rule

The edges are A→B, B→A and A→C. Is A→B→A→C a no-repeated-vertex path? Is it a three-edge walk?

A appears twice, so the path restriction fails.
All three arrows exist and walks may repeat vertices.

It is not that kind of path, but it is a three-edge walk.

Check your understanding

If ${(A^{3})}_{P Q} = 4$ , what does 4 mean?

Show answer

Four three-edge walks from P to Q.

The power states the number of edges, and the indices give start and finish.

03 / WORKSHEET

Your turn

6 questions · 12 marks · Work at your own pace.

Worksheet PDF Worked solutions

Read the questions online

Edges are A→B, A→C, B→D and C→D. List two-edge walks from A to D.
2 marks
For $A = (\begin{array}{cccccccccc} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array})$ , find ${(A^{2})}_{A A}$ .
2 marks
For $A = (\begin{array}{cccccccccc} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array})$ , find ${(A^{2})}_{B C}$ .
2 marks
A route must not revisit its start. Why might diagonal entries of $A^{2}$ be excluded from a total?
2 marks
There are two distinct ferry services A→B and three B→C services. Count A→B→C service combinations.
2 marks
Edges are A→B, A→C, B→C, B→D and C→D. List all A-to-D paths with no repeated vertices.
2 marks

Read the worked solutions

Equivalent correct methods earn the corresponding marks. Include units where asked.

Edges are A→B, A→C, B→D and C→D. List two-edge walks from A to D.
2 marks
B and C are the two possible intermediate vertices.
Each gives one permitted walk.
A→B→D and A→C→D.
For $A = (\begin{array}{cccccccccc} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array})$ , find ${(A^{2})}_{A A}$ .
2 marks
Row A times column A gives $0 (0) + 1 (0) + 1 (1) = 1$ .
The walk is A→C→A.
1.
For $A = (\begin{array}{cccccccccc} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array})$ , find ${(A^{2})}_{B C}$ .
2 marks
Row B times column C gives $0 (1) + 0 (1) + 1 (0) = 0$ .
No such two-edge walk exists.
0.
A route must not revisit its start. Why might diagonal entries of $A^{2}$ be excluded from a total?
2 marks
A diagonal entry has identical start and finish.
That violates the no-revisit condition.
They represent walks returning to their starting vertex.
There are two distinct ferry services A→B and three B→C services. Count A→B→C service combinations.
2 marks
There are 2 first-service choices.
Each has 3 second-service choices: $2 (3) = 6$ .
6.
Edges are A→B, A→C, B→C, B→D and C→D. List all A-to-D paths with no repeated vertices.
2 marks
First branch to B or C.
From B choose D or go via C; from C go to D.
A→B→D; A→C→D; A→B→C→D.

Checking saved progress…

Continue learning

Shortest/longest paths

Next lesson

Curriculum reference & lesson scope

SACE Board of South Australia

Stage 1 General Mathematics: matrices and networks. Original learning resources follow the approved Ascent Library chapter map.

Official curriculum source ↗

Back to Matrices and networks