Networks and decision mathematics (QCE General Mathematics Unit 4)

What this dot point is asking

The last two topics of Unit 4 in the QCAA General Mathematics 2025 syllabus use networks to make decisions:

• Topic 4: Networks and decision mathematics 1. Trees and minimum connector problems (minimum spanning trees), and project planning and scheduling using critical path analysis.
• Topic 5: Networks and decision mathematics 2. Flow networks (cuts, minimum cut and maximum flow), and assigning order with bipartite graphs and the Hungarian algorithm.

They build on Topic 3: Graphs and networks (terminology, adjacency matrices, planar graphs, Euler's formula, Eulerian and Hamiltonian routes, and shortest paths by trial and error).

Each technique has its own page. This page is the overview: it helps you recognise which technique a question needs, shows one compact example of each, and highlights the confusions that cost marks. In the external assessment these appear as short-response items and as extended problems where you must choose the method yourself.

The answer

Choosing the technique

Key words help: "connect all", "cable", "pipeline to every house" suggest a minimum spanning tree; "project", "activities", "earliest start", "delay" suggest critical path analysis; "capacity", "per hour", "source", "sink" suggest flow; "allocate", "assign", "each worker one task" suggest the Hungarian algorithm; "quickest route from A to B" is a shortest path.

Minimum spanning trees (Topic 4)

A tree is connected with no cycles; a tree on $v$ vertices has $v - 1$ edges. A minimum spanning tree connects every vertex with the least total weight. With Prim's algorithm, start anywhere and repeatedly add the smallest edge from the tree to a new vertex. For edges P-Q 4, P-R 6, Q-R 3, Q-S 7, R-S 5, R-T 8 and S-T 2, starting at P: P-Q (4), Q-R (3), R-S (5), S-T (2), total 14. Kruskal's algorithm (smallest edges first, skipping any that form a cycle) gives the same total and is a good check.

Critical path analysis (Topic 4)

Draw the project as an activity-on-arc network (no dummy activities). A forward scan gives each activity's earliest starting time (EST), taking the maximum at merges; a backward scan from the finish time gives latest starting times (LST), taking the minimum at branches. Float $=$ LST $-$ EST. Activities with zero float form the critical path, the longest path, whose length is the minimum completion time.

For A (4, none), B (3, A), C (6, A) and D (2, B and C): D's EST is $\max(4 + 3, 4 + 6) = 10$, so the project takes $10 + 2 = 12$. The critical path is A-C-D, and B has float $(10 - 3) - 4 = 3$.

Flow networks (Topic 5)

A flow network is a directed network from a source to a sink, with each edge's weight a capacity. A cut separates the source from the sink; its capacity is the sum of the capacities of edges crossing it from the source side to the sink side (edges crossing the other way are not counted). The maximum flow equals the capacity of the minimum cut. The syllabus limits problems to at most 8 possible cuts, so you can list them all.

With three vertices between S and T there are $2^3 = 8$ cuts. Their capacities are 16, 16, 18, 18, 20, 21, 26 and 27, so the minimum cut is 16 (two different cuts achieve it) and the maximum flow is 16.

Assignment (Topic 5)

An allocation of workers to tasks can be shown as a bipartite graph or a cost matrix. Small problems can be solved by inspection (list the allocations). For 3 x 3 to 5 x 5 matrices, the Hungarian algorithm reduces rows, then columns, covers the zeros with the fewest lines, adjusts if the number of lines is less than the matrix size, then assigns one zero per row and column and totals the original entries. To maximise, first subtract every entry from the largest.

For costs X: 9, 6, 8; Y: 7, 4, 9; Z: 6, 5, 7, row then column reduction gives X (2, 0, 0), Y (2, 0, 3), Z (0, 0, 0), which needs 3 lines. Y takes job 2, X job 3 and Z job 1: total $8 + 4 + 6 = 18$.

Common confusions

• Minimum spanning tree versus shortest path. A minimum spanning tree minimises the total of all connections; a shortest path minimises one route. The route between two vertices along a minimum spanning tree is not necessarily the shortest route.
• Critical path versus shortest path. The critical path is the longest path through a project network.
• Minimum cut versus the smallest edge. A cut must separate source from sink; one small edge does not limit the flow unless every route passes through it.
• Assignment versus minimum spanning tree. An assignment pairs members of two groups one-to-one; it does not connect vertices into a network.