§-Syllabus dot point

WAMathematics ApplicationsSyllabus dot point

How can diagrams of dots and lines model and solve real connection problems?

Represent situations with graphs and networks, use terminology and matrices, and solve shortest path, minimum spanning tree and connection problems.

How to read and draw graphs and networks, use vertices, edges and adjacency matrices, trace Euler and Hamilton paths, and find minimum spanning trees and shortest paths.

Generated by Claude Opus 4.89 min answerUpdated 2026-06-02

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section

What this dot point is asking
Graphs and networks
Choosing the right tool
Minimum spanning trees
Counting walks with matrix powers
Traversal versus connection versus journey

What this dot point is asking

You must model with graphs, use terminology and matrices, and solve connection, shortest-path and traversal problems.

Graphs and networks

A graph is a set of vertices joined by edges; a network is a weighted graph, where each edge has a number attached. Networks model road systems, pipelines, project schedules and communication links.

The adjacency matrix records connections; for a weighted network a separate weighted matrix can store the edge weights, with entries left blank or marked for non-adjacent vertices.

Choosing the right tool

The single most examined skill is matching the question to the algorithm.

Connect every site at least total cost: find a minimum spanning tree (Prim's or Kruskal's method).
Travel from one vertex to another at least cost: find a shortest path.
Traverse every edge exactly once: look for an Eulerian trail or circuit (odd-vertex rule).
Visit every vertex exactly once: look for a Hamiltonian path or cycle.

Minimum spanning trees

A spanning tree connects all $n$ vertices using exactly $n - 1$ edges and no cycles. The minimum spanning tree has the least total weight. Build it by repeatedly adding the shortest available edge that does not create a cycle, stopping at $n - 1$ edges.

Worked example

Finding a minimum spanning tree

Six offices must be linked by cable. The possible links (cost in $\$$ thousands) are $AB=4$ , $AC=3$ , $BC=2$ , $BD=5$ , $CE=6$ , $DE=4$ , $DF=7$ , $EF=3$ .

Step 1: Sort the edges by weight

Kruskal's algorithm always considers the cheapest available edge next, so sorting the full list at the start avoids missing a shorter option later. $BC=2$ , $AC=3$ , $EF=3$ , $AB=4$ , $DE=4$ , $BD=5$ , $CE=6$ , $DF=7$ .

Step 2: Add shortest edges, skipping any that form a cycle

Adding an edge that connects two already-connected vertices would create a cycle, which a spanning tree must not contain, so any such edge is skipped. Add $BC(2)$ . Add $AC(3)$ , joining $A$ . Add $EF(3)$ . Add $AB(4)$ ? That would form a cycle $A$ - $B$ - $C$ , so skip it. Add $DE(4)$ , joining $D$ and $E$ . So far edges $BC$ , $AC$ , $EF$ , $DE$ connect $\{A,B,C\}$ and $\{D,E,F\}$ as two groups. Add $BD(5)$ to join the groups.

Step 3: Count the edges and total the cost

A spanning tree on $n$ vertices uses exactly $n - 1$ edges, so stopping at five edges confirms the tree is complete. Five edges ( $n - 1 = 5$ for six vertices): $BC$ , $AC$ , $EF$ , $DE$ , $BD$ . Total cost $= 2 + 3 + 3 + 4 + 5 = 17$ , that is $\$17\,000$ .

Step 4: Interpret the result in context

Stating what the number means in the real situation shows the examiner the answer is understood, not just calculated. The cheapest cabling that connects all six offices costs $\$17\,000$ , with no redundant loops.

Counting walks with matrix powers

The adjacency matrix raised to the power $k$ has entries giving the number of walks of length exactly $k$ between vertices. Squaring the matrix counts two-step connections, which SCSA sometimes asks you to compute and interpret (for example, the number of two-flight routes between cities).

Traversal versus connection versus journey

It helps to group the network tools by the question they answer. Traversal problems (cover every edge or visit every vertex) use Euler and Hamilton ideas. Connection problems (link every site cheaply) use the minimum spanning tree. Journey problems (get from one place to another cheaply) use the shortest path. Scheduling problems (finish a project fastest) use critical path analysis, and capacity problems (push the most through) use maximum flow. Reading the verb in the question, "cover", "connect", "travel", "schedule" or "push through", points straight to the right method.

Exam-style practice questions

Practice questions written in the style of SCSA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

WACE 20227 marksFive towns are connected by roads with lengths (km):

AB=6

AC=9

BC=4

BD=8

CD=5

CE=7

DE=3

. (a) Find the minimum spanning tree and its total length. (b) State what the minimum spanning tree represents in this context.

Show worked answer →

Build the tree by adding the shortest edges that do not form a cycle (Prim's or Kruskal's method).

(a) Sort edges: $DE=3$ , $BC=4$ , $CD=5$ , $AB=6$ , $CE=7$ , $BD=8$ , $AC=9$ . Add $DE(3)$ , $BC(4)$ , $CD(5)$ ; then $AB(6)$ connects $A$ . Four edges now join all five towns: $DE$ , $BC$ , $CD$ , $AB$ . Total $= 3 + 4 + 5 + 6 = 18$ km. (5 marks)

(b) The minimum spanning tree is the cheapest set of roads that connects every town to every other (directly or indirectly) with no redundant loops. (2 marks)

Markers reward adding shortest cycle-free edges, stopping at $n-1 = 4$ edges, and interpreting the tree as the least-cost connection.

WACE 20245 marksA graph has

7

vertices and

10

edges. (a) Use the handshake rule to find the sum of the degrees. (b) Explain how an adjacency matrix records this graph and what its row sums represent.

Show worked answer →

The handshake rule links total degree to the edge count.

(a) Sum of degrees $= 2 \times \text{edges} = 2 \times 10 = 20$ . (2 marks)

(b) The adjacency matrix is a $7\times7$ array where entry $(i,j)$ is the number of edges between vertices $i$ and $j$ ; for this undirected graph it is symmetric. Each row sum is the degree of that vertex, so the row sums total $20$ , matching part (a). (3 marks)

Markers reward the handshake calculation and identifying row sums as vertex degrees.