Networks and decision mathematics (WACE Year 12 Mathematics Applications)

Syllabus dot point

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

9 min readUpdated 2 Jun 2026

Quick answer

A network is a graph whose edges carry weights such as distance, cost or time. Represent a situation with vertices and weighted edges, record it as a matrix, and use the right algorithm for the right question: a minimum spanning tree to connect everything cheaply, a shortest path to travel between two points cheaply, and Euler or Hamilton routes to traverse edges or visit vertices. Choosing the correct tool for the wording is the core skill.

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
Exam-style questions

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.

Key network terms

A weight is the number on an edge (distance, time, cost). A path is a route that does not repeat a vertex. A cycle returns to its start without repeating other vertices. A connected graph has a route between every pair of vertices. A tree is a connected graph with no cycles.

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.

Spanning tree connects, shortest path travels

A minimum spanning tree links every vertex together cheaply; it is about the whole network. A shortest path is the cheapest route between two named vertices only. Confusing these is the most common networks error, so read whether the question wants everything connected or a single journey.

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.

Common errors

Confusing spanning tree with shortest path: A spanning tree connects everything; a shortest path is one journey. Read the question carefully.
Adding too many edges to a spanning tree: A spanning tree of $n$ vertices has exactly $n - 1$ edges; one more creates a cycle.
Creating a cycle while building the tree: Skip any edge that would join two already-connected vertices.
Misreading a weighted matrix: Distinguish a zero (no connection) from a blank, and remember adjacency entries count edges while weighted entries store distances.

Exam-style questions

Questions in the style of SCSA exam questions on this dot point, each with a worked answer. They are written by ExamExplained unless tagged "Past paper"; the year shows the paper a question is modelled on.

WACE 2022-style7 marks

Five 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 2024-style5 marks

A 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.