General Mathematics · Unit 4 · Topic 4

Networks and decision mathematics 1

Connect every vertex of a network for the least total weight with minimum spanning trees, then plan projects with activity-on-arc networks, forward and backward scans, critical paths and float times.

  • 8 lessons
  • 2 h 10 min of lessons
  • 12 worked examples
  • 12 hours in the syllabus
0 of 8

Start here

Trees and spanning trees

Lesson 1 of 8 · 14 min

Start the topic

Lessons

8
  1. Trees and spanning trees (up next)

    Recognise trees and spanning trees, explain why a tree with vv vertices has v−1v - 1 edges, and find the spanning trees of a small graph.

  2. Finding minimum spanning trees

    Find a minimum spanning tree and its weight by inspection, with Kruskal's method and with Prim's method, and recognise when there is more than one.

  3. Minimum connector problems

    Model practical cable, pipe and path problems as minimum spanning trees, cost them, and adapt the method when a link must be used or cannot be used.

  4. Precedence tables and project networks

    Read a precedence table, and draw a project as an activity-on-arc network with each activity as a labelled arrow and each event as a numbered circle.

  5. Forward scanning and earliest starting times

    Scan a project network from start to finish to find the earliest starting time of every activity and the minimum time in which the project can be completed.

  6. Backward scanning, latest starting times and float

    Scan a project network from the finish back to the start to find the latest starting time of every activity, then calculate each activity's float.

  7. Critical paths and the minimum completion time

    Use ESTs and LSTs to locate the critical path or paths of a project, and explain why their length is the minimum completion time.

  8. Solving scheduling problems

    Use critical path analysis to decide what a delay does to a project, how far a project can be shortened, and how to justify scheduling decisions in context.

  9. Topic quiz

    Ten questions across the topic, from foundation to complex unfamiliar. Your results feed your mastery.

About this topic

In Graphs and networks you used networks to describe connections. Now you use them to make decisions.

The first question is how to connect every town to a power station, or every paddock to a bore, using the least cable or pipe. The answer is always a tree — a network with no cycles — and the cheapest one is a minimum spanning tree. You will find one by inspection, with Kruskal's method and with Prim's method.

The second question is how quickly a project can be finished when some jobs must wait for others. You will draw the project as a network of activities, scan it forwards and backwards to find when each activity can start, find the critical path that sets the finish date, and work out how much each other activity can slip without making the project late.

Both halves reward careful, systematic working: list each edge as you choose it, write the times at every event, and state your answer in the context of the problem.

Before you start

Builds on Graphs and networks.

  • Graph language from Graphs and networks: vertex, edge, weighted graph, network, cycle, connected graph, directed graph.
  • Adding whole numbers and decimals accurately, and multiplying a total length by a cost per unit.
  • Reading a table carefully, row by row.

What QCAA says you need to know9 dot points

Trees and minimum connector problems

4 hours

Project planning and scheduling using critical path analysis (CPA)

8 hours

Subject matter from the General Mathematics General senior syllabus 2025 v1.3 (opens in a new tab), CC BY 4.0 © State of Queensland (QCAA).

The focus areas you can practise on their own. Each one maps to dot points above.

  • Trees and spanning trees

    Recognise trees and spanning trees, and use the fact that a tree with n vertices has n − 1 edges.

    Practise
  • Finding minimum spanning trees

    Find a minimum spanning tree and its weight by inspection, Kruskal's method or Prim's method, and decide whether it is unique.

    Practise
  • Minimum connector problems

    Model a cable, pipe or path problem as a minimum spanning tree, including edges that must be used or cannot be used, and costs.

    Practise
  • Project networks

    Read and write precedence tables, and draw a project as an activity-on-arc network.

    Practise
  • Earliest starting times

    Scan a project network forwards to find each activity's EST and the minimum completion time.

    Practise
  • Latest starting times

    Scan a project network backwards to find each activity's LST.

    Practise
  • Critical paths

    Use ESTs and LSTs to locate the critical path or paths, and use them to give the minimum completion time.

    Practise
  • Float times

    Calculate float = LST − EST for non-critical activities and say what it means for the schedule.

    Practise
  • Scheduling problems

    Use critical path analysis to judge delays, shorten a project, add an activity, and justify scheduling decisions.

    Practise

Worked examples12

All 12

Common mistakes

Including a cycle in a spanning tree

A tree has no cycles. If an edge joins two vertices that are already connected in your tree, it would make a cycle — skip it, however light it is.

Wrong number of edges

A spanning tree of a graph with vv vertices has exactly v−1v - 1 edges. Count them before you add the weights.

Taking the smallest value in the forward scan

An activity can only start when all of its predecessors are finished, so at an event with several incoming activities the earliest time is the largest of the values.

Taking the largest value in the backward scan

An event must happen early enough for every activity leaving it to start on time, so in the backward scan take the smallest of the values.

Reading the LST from the start of an activity

The latest time written at an activity's start event is the LST of the most urgent activity leaving it, not necessarily of this one. Always use LST = (latest time at the end event) − duration.

Giving the minimum time as the sum of all durations

Activities on different branches can run at the same time. The minimum completion time is the length of the longest path, not the total of every duration.

Thinking any delay to a non-critical activity is harmless

A non-critical activity can slip only by its float. A delay of dd beyond its float makes the whole project d−floatd - \text{float} longer.

Shortening a critical activity too far

Once one path is shortened below another, the other path becomes critical. Recheck every path after you change a duration.

Exam tips

  1. Name your method. "Using Kruskal's method, choose edges in order of weight: DEDE (3), BDBD (4), …" earns method marks even if you slip on an addition.

  2. List the edges of a minimum spanning tree and count them: v−1v - 1 edges is a quick check that you have not missed or added one.

  3. Write both times at every event as you scan, and state the minimum completion time with units: "The minimum completion time is 16 days."

  4. Give a critical path as a sequence of activities, such as A–C–E–F, and check that its durations add to the minimum completion time.

  5. If there is more than one critical path, give them all. The syllabus says "critical path/s" for a reason.

  6. For "effect of a delay" questions, compare the delay with the activity's float and say what happens to the finish time.

  7. Show a table of EST, LST and float when a question asks about several activities. It is quicker to mark and to check.

  8. Minimum spanning tree and critical path questions can be done without a calculator. Paper 2 contexts may add costs, so set out the multiplication.

Where this shows up

  • Energy companies plan transmission lines and gas pipelines between towns using minimum connector methods.

  • Farmers plan irrigation pipes and water points across paddocks with the least length of pipe.

  • Telecommunications companies lay fibre-optic cable between exchanges to join every site for the least cost.

  • Builders, event organisers and engineers use critical path analysis to schedule trades and set realistic finish dates.

  • Project managers watch the critical activities most closely, and use float to move non-critical work when people or equipment are busy.

  • Large projects, such as a new hospital or a festival stage, are shortened ("crashed") by spending money on the critical activities that are cheapest to speed up.

Save your progress with a free account