QCE General Mathematics - Unit 4 - Networks and decision mathematics 1
Trees and Minimum Connector Problems | QCE General Mathematics
Learn trees, spanning trees, minimum spanning trees and practical connector problems for QCE General Mathematics.
Updated 2026-05-18 - 5 min read
QCAA official coverage - General Mathematics 2025 v1.3
Exact syllabus points covered
- Understand the meaning of tree, spanning tree and minimum spanning tree.
- Determine a minimum spanning tree in a weighted connected graph.
- Solve practical problems involving minimum spanning trees, e.g. minimising the length of cable needed to provide power from a single power station to substations in several towns.
A tree is a connected graph with no cycles. Trees are useful when a network must connect all locations without unnecessary loops, such as installing cable, roads, fibre or pipelines.
Original Sylligence diagram for general minimum spanning tree.
Trees and spanning trees
A spanning tree connects every vertex of a graph using a subset of the original edges. A graph can have many spanning trees. If the graph is weighted, a minimum spanning tree has the lowest total weight.
Finding a minimum spanning tree
One practical approach is:
- Choose the smallest available edge.
- Add the next smallest edge that does not create a cycle.
- Continue until every vertex is connected.
For a graph with $v$ vertices, a spanning tree will have $v-1$ edges.
Worked example
Common traps
Prim's algorithm
Prim's algorithm builds a minimum spanning tree from a starting vertex:
- Start at any vertex.
- Choose the smallest edge that connects the current tree to a new vertex.
- Add that edge and vertex.
- Repeat until every vertex is included.
The important restriction is that each new edge must connect to a vertex not already in the tree. This prevents cycles.
Multiple minimum spanning trees
If two or more edges have the same weight, there may be more than one valid minimum spanning tree. That is not a problem if the total weight is minimal and all vertices are connected without cycles.
Connector-problem wording
Minimum connector problems often appear as practical contexts: connecting towns by roads, substations by cable, campuses by fibre, or water tanks by pipes. These problems are not asking for the shortest route from one place to another. They are asking for the cheapest way to connect the whole network.
Depth: trees and spanning trees
A tree is a connected graph with no cycles. If a tree has $v$ vertices, it has:
$ e=v-1 $
edges. This relationship is a quick check when deciding whether a connected graph could be a tree.
A spanning tree connects all vertices of a graph using only some of the edges and contains no cycles. A minimum spanning tree is the spanning tree with the least total weight.
Minimum connector interpretation
Minimum connector problems occur when every location must be connected at minimum total cost. Examples include:
- linking towns with fibre cable
- connecting buildings with walkways
- designing a pipe network
- linking devices in a local network
The answer is not usually a route to travel. It is a set of connections to build.
Prim's algorithm
Prim's algorithm builds a minimum spanning tree.
- Start at any vertex.
- Choose the smallest-weight edge that connects the current tree to a new vertex.
- Add that edge and vertex.
- Repeat until all vertices are connected.
Never add an edge that creates a cycle.
Kruskal-style thinking
Even when using Prim's algorithm, it helps to understand the cycle rule: a minimum spanning tree must connect all vertices without closing a loop. If there are equal edge weights, there may be more than one minimum spanning tree with the same total weight.
Checking the final answer
A final minimum connector answer should:
- include all vertices
- have exactly $v-1$ edges
- have no cycles
- state the total weight or cost
- list the selected connections, not just the number
Depth: why minimum connector is not shortest path
A minimum connector problem connects every vertex as cheaply as possible. A shortest path problem travels from one specified vertex to another. These are different goals.
For example, the cheapest network connecting five towns may include a road that is not on the shortest route between any particular pair of towns. It is included because it helps connect the whole system cheaply.
Before choosing an algorithm, identify the command word:
| Task wording | Likely method | |---|---| | connect all locations at minimum cost | minimum spanning tree | | find the shortest route from A to F | shortest path | | visit every edge exactly once | Eulerian reasoning | | assign workers to jobs | Hungarian algorithm |
If a graph is already a tree, its only spanning tree is itself. If it has extra edges, a minimum spanning tree is found by removing enough cycle-forming edges while keeping every vertex connected.