Reachability and dominance/ranking applications | Year 12

01 / LEARN

The idea, step by step

Reachability asks whether any route exists

For a finite $n$ -vertex network, any reachable different vertex can be reached without repeats in at most $n - 1$ steps. Repeated cycles can be removed from a route without changing its endpoints. Positive off-diagonal entries in $A + A^{2} + \dots + A^{n - 1}$ therefore identify reachability.

This is a yes/no question, not a shortest distance or journey-time result. If zero-step self-reachability is included, use the identity matrix too. State this convention when interpreting diagonal entries.

A dominance score follows a chosen rule

A dominance matrix can record wins: $d_{i j} = 1$ if team $i$ defeated team $j$ . Row sums count direct wins. A rule based on row sums of $D + 0.5 D^{2}$ gives half credit for defeating a team that defeated another team. The chosen weighting changes the model.

A cycle A beats B, B beats C, C beats A need not produce a unique ranking. State how ties, repeat matches and indirect wins are handled, and do not claim that the score proves permanent superiority. A model is useful when its rule matches the decision being made.

A common trap

Treating a selected dominance score as an objective law.

Instead: Explain the weighting, available evidence and treatment of ties.

02 / WORKED EXAMPLES

See the thinking

Example 1

An indirect connection

A network is the chain A→B→C→D. Which power first records A reaching D?

No one- or two-step walk reaches D from A.
A→B→C→D uses three edges.

The first positive entry is

{(A^{3})}_{A D} = 1

Example 2

A direct-plus-indirect score

A beats B and C, B beats C, C beats nobody. Use row sums of $D + D^{2}$ .

Direct scores are (2,1,0).
A→B→C is the only two-step dominance walk, giving extra scores (1,0,0).

Combined scores (3,1,0): A, then B, then C.

Check your understanding

If ${(A + A^{2})}_{P Q} = 0$ in a four-vertex network, can P still reach Q?

Show answer

Yes.

A three-step route may exist.

03 / WORKSHEET

Your turn

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

Worksheet PDF Worked solutions

Read the questions online

List reachable ordered pairs of different vertices in A→B→C.
3 marks
Dominance rows are (0,1,1),(0,0,1),(0,0,0). Find direct scores and scores from $D + D^{2}$ .
3 marks
A beats B, B beats C and C beats A. Find direct scores and explain the tie.
3 marks
For the same cycle, use row sums of $D + 0.5 D^{2}$ . Find all scores.
3 marks
Which adjacency powers suffice to test reachability between different vertices in a five-vertex network?
3 marks
Club A gets 40 votes from 100 eligible voters; B gets 30 from 50.
4 marks
1. (a)
  Find each support percentage.
  2 marks
2. (b)
  Explain why a ranking rule must name its denominator.
  2 marks

Read the worked solutions

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

List reachable ordered pairs of different vertices in A→B→C.
3 marks
The first and last are direct; A→B→C supplies the indirect connection.
(A,B), (A,C), (B,C).
Dominance rows are (0,1,1),(0,0,1),(0,0,0). Find direct scores and scores from $D + D^{2}$ .
3 marks
Row sums of $D$ give direct wins.
Only A has one two-step win, via B to C.
Direct (2,1,0); combined (3,1,0).
A beats B, B beats C and C beats A. Find direct scores and explain the tie.
3 marks
Each row contains one direct win.
Each team scores 1; the results form a cycle.
For the same cycle, use row sums of $D + 0.5 D^{2}$ . Find all scores.
3 marks
Each team has one direct win and one two-step dominance walk.
All are 1.5.
Which adjacency powers suffice to test reachability between different vertices in a five-vertex network?
3 marks
A route with no repeated vertices has at most four edges.
Any longer reachable route can have cycles removed.
$A, A^{2}, A^{3}, A^{4}$ .
Club A gets 40 votes from 100 eligible voters; B gets 30 from 50.
4 marks
a) Calculate $40 / 100$ and $30 / 50$ .
b) Different criteria answer different questions.
1. (a)
  Find each support percentage.
  2 marks
  Calculate $40 / 100$ and $30 / 50$ .
  A: 40%; B: 60%.
2. (b)
  Explain why a ranking rule must name its denominator.
  2 marks
  Different criteria answer different questions.
  A wins by vote count, but B wins by support rate.
a) A: 40%; B: 60%.; b) A wins by vote count, but B wins by support rate.

Checking saved progress…

Continue learning

Transition matrices and state vectors

Next lesson

Curriculum reference & lesson scope

SACE Board of South Australia

Stage 2 General Mathematics matrix-models option. This is the offered fifth-topic option, alongside the four compulsory topics; a school-designed Open Topic is an alternative, not prescribed content in this chapter.

Official curriculum source ↗

Back to Matrix models