Reachability and dominance/ranking applications | Year 12

01 / LEARN

Understand the idea.

Reachability asks whether any route exists

Reachability asks whether some directed route exists, rather than how many walks have one specified length. In a network with $n$ vertices, any reachable different destination has a route without repeated vertices and at most $n - 1$ steps.

Cycles can be removed from a route without changing its endpoints. Thus positive off-diagonal entries of $A + A^{2} + \dots + A^{n - 1}$ identify reachable pairs. Add the identity if zero-step self-reachability is included; the sum alone does not measure shortest journey time.

A dominance score follows a chosen rule

A dominance matrix can record $d_{i j} = 1$ when team $i$ defeats team $j$ . Row sums count direct wins; row sums of $D + w D^{2}$ also credit two-step win chains with a chosen weight $w$ . State that rule before ranking.

An indirect win is evidence used by the scoring model, not proof of a match outcome. Cycles and ties can prevent a unique ranking. Explain the weighting, repeat-match treatment and available evidence when recommending how to use a score.

02 / WORKED EXAMPLES

See the method in action.

EXAMPLE 01

An indirect connection

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

Worked solution

1
Follow the forced first and second moves.
$A_{A D} = 0, {(A^{2})}_{A D} = 0$
From A, one step reaches B and two steps reach C; neither reaches D.
2
Identify the first route to D.
A to B to C to D uses three directed edges, and the chain provides no alternative three-step route.
3
State the first positive power entry.
${(A^{3})}_{A D} = 1$
The first reachability evidence for this pair occurs at length three, with one such walk.

Answer

The first positive entry is ${(A^{3})}_{A D} = 1$ .

EXAMPLE 02

A direct-plus-indirect score

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

Worked solution

1
Record the direct-win matrix.
$D = (\begin{array}{cccccccccc} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{array})$
In A, B, C order, A has two direct wins, B has one and C has none.
2
Find the two-step win chains.
$D^{2} = (\begin{array}{cccccccccc} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array})$
A to B to C is the only two-step dominance walk.
3
Add the direct and indirect matrices.
$D + D^{2} = (\begin{array}{cccccccccc} 0 & 1 & 2 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{array})$
The given rule gives one point to each direct win and one to each two-step chain.
4
Sum the rows and rank.
$(\begin{array}{cccccccccc} 3 \\ 1 \\ 0 \end{array})$
The scores rank A first, B second and C third under this particular rule.

Answer

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

03 / YOUR TURN

Try it yourself.

Check your understanding

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

Show answer & reasoning

Yes.

Yes. A four-vertex chain can have a three-step route from P to Q while having no one-step or two-step walk between them. The given zero excludes only the lengths included in $A + A^{2}$ .

Keep practising

6 worksheet questions · 19 marks

Open worksheet Worked solutions

Read the questions online

List reachable ordered pairs of different vertices in A→B→C.
3 marks
Dominance rows are $(\begin{array}{cccccccccc} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{array})$ . 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 $(\begin{array}{cccccccccc} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{array})$ . 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 $\frac{40}{100}$ and $\frac{30}{50}$ .
b) Different criteria answer different questions.
1. (a)
  Find each support percentage.
  2 marks
  Calculate $\frac{40}{100}$ and $\frac{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…

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 ↗

In this lesson

Understand the idea.

Reachability asks whether any route exists

A dominance score follows a chosen rule

See the method in action.

An indirect connection

Follow the forced first and second moves.

Identify the first route to D.

State the first positive power entry.

A direct-plus-indirect score

Record the direct-win matrix.

Find the two-step win chains.

Add the direct and indirect matrices.

Sum the rows and rank.

Try it yourself.

Check your understanding

Keep practising