Worksheets

Practise this lesson

Three printable worksheets that build from foundations to mastery, or build your own from any module’s questions.

Build Foundations & guided practice Apply Application practice Master Mastery challenge Build custom Build your own from any module question

Module 6 · Networks and Critical Paths

Module Review

MS-N2 & MS-N3 synthesis · HSC exam technique · Complete problem-solving workflow

MS12-7 MS-N2 + MS-N3 Lesson 12 of 12

Think First

You have studied two major outcome areas: MS-N2 (Network Concepts: vertices, edges, degree, trees, spanning trees, Dijkstra's algorithm) and MS-N3 (Critical Path Analysis: activity networks, EST/LST, float, Gantt charts, crashing).

Before reading on, without looking at your notes, can you list the key formula or rule for each of the following: (a) degree sum theorem, (b) spanning tree edges, (c) EST forward scan rule, (d) float formula, (e) crashing rule?

Learning Intentions

Recall and apply all key concepts from MS-N2 (Lessons 1–6) and MS-N3 (Lessons 7–11)
Execute the full CPA workflow from precedence table to critical path in a single uninterrupted problem
Select appropriate network algorithms (Kruskal's, Prim's, Dijkstra's) for different problem types
Apply HSC exam technique: identify question type, choose method, show working clearly, verify answer
Connect the two outcome areas: both deal with graphs/networks, just with different objectives

Module Summary, Key Formulas and Rules

Degree sum theorem (MS-N2): Sum of all vertex degrees = 2 × number of edges. A loop at a vertex counts as 2 towards degree.
Spanning tree (MS-N2): A spanning tree of n vertices has exactly n − 1 edges. Use Kruskal's (sort edges, skip cycles) or Prim's (grow from vertex) for minimum spanning tree.
Dijkstra's algorithm (MS-N2): Source node gets label 0; all others start ∞. Repeatedly select minimum unvisited, update neighbours. Once permanent, label cannot decrease.
EST, forward scan (MS-N3): Work left to right. EST(node) = maximum of (EST(predecessor) + duration) for all incoming activities.
LST, backward scan (MS-N3): Work right to left. LST(final node) = EST(final node). LST(node) = minimum of (LST(successor) − duration) for all outgoing activities.
Float formula (MS-N3): Float = LST(end node) − EST(start node) − duration. Zero float = critical activity.
Critical path (MS-N3): Longest path; all nodes have EST = LST; total duration = minimum project time.
Crashing (MS-N3): Only crashing critical path activities reduces project duration. Must crash all critical paths simultaneously.
Gantt chart (MS-N3): Bar starts at EST, length = duration. Float window extends from bar end to LST(end node).

MS-N2 Rapid Review, Network Concepts

Network basics (Lesson 1–2)

A network has vertices (nodes) and edges (connections).
Degree of a vertex = number of edges incident to it (loops count 2).
Degree sum theorem: Σ deg = 2|E|. Use to find missing degrees or edge counts.
A degree sequence is possible only if the sum is even.
Directed networks (digraphs) have one-way edges; undirected have two-way.

Paths and Euler (Lesson 3)

Walk: any sequence of edges. Trail: no repeated edges. Path: no repeated vertices.
Euler circuit: uses every edge once, returns to start, requires 0 odd-degree vertices.
Euler trail: uses every edge once, open walk, requires exactly 2 odd-degree vertices.
Hamiltonian path visits every vertex exactly once.

Trees and MST (Lessons 4–5)

A tree is connected, acyclic, and has exactly n − 1 edges for n vertices.
A spanning tree connects all vertices using n − 1 edges.
Kruskal's: Sort all edges by weight → add smallest → skip if it creates a cycle → stop when n−1 edges added.
Prim's: Start at any vertex → always add smallest edge connecting a new vertex → repeat until all vertices included.

Dijkstra's algorithm (Lesson 6)

Finds shortest path from source to all other vertices in a weighted graph.
Method: label source = 0, others = ∞; select minimum unlabelled; update neighbours (if new path is shorter, update); repeat until all labelled permanent.
Traceback: follow the path that gives the shortest distance at each step.

A graph has vertices A(deg 4), B(deg 3), C(deg 3), D(deg 2). Check: Σ deg = 4+3+3+2 = 12 = 2×6 edges. ✓

A spanning tree of 4 vertices needs 4−1 = 3 edges. Kruskal's would select the 3 cheapest non-cycle-forming edges from the 6 available.

Resource allocation in CPA assigns people or equipment to activities while respecting precedence. A resource histogram plots total resource use over time; the aim is to level peaks ('resource levelling') within float limits.

Pause, copy the resource histogram definition (bar chart of total resource use per time period) and the resource-levelling goal: redistribute non-critical activities within their float to smooth resource demand without extending the project into your book.

MS-N3 Rapid Review, Critical Path Analysis

Activity networks (Lesson 7)

Directed graph with activities as edges, nodes as events/milestones.
Precedence table → draw network: independent activities start from same start node; dependent activities wait for predecessors.
Critical path = longest path = minimum project duration.

Forward and backward scan (Lesson 8)

Forward scan: EST(node) = max of (predecessor EST + incoming duration). Left to right.
Backward scan: LST(final) = EST(final). LST(node) = min of (successor LST − outgoing duration). Right to left.
Record in split node boxes: left = EST, right = LST.

Critical path and float (Lesson 9)

Critical path: all connecting nodes have EST = LST.
Float = LST(end node) − EST(start node) − duration.
Float is shared on a path, using one activity's float reduces successor's float.

Gantt charts and crashing (Lesson 10)

Bar: start at EST, end at EST + duration. Float window: end of bar to LST(end node).
Crashing: only critical activities. Must crash ALL critical paths simultaneously.

Complex problems (Lesson 11)

Multiple critical paths: all have EST = LST throughout, all same total length.
Dummy activities: dashed arrows, duration 0, show shared-predecessor dependencies.

Precedence table: A(3), B(2), C(4, A), D(5, A,B), E(3, C,D)

Network: Start→A(3)→N2; Start→B(2)→N3; N2→C(4)→N4; N2+N3→D(5)→N5; N4+N5→E(3)→End

Forward: Start=0, N2=3, N3=2, N4=7, N5=max(3,2)+5=8, End=max(7,8)+3=11

Backward: End=11. N5=11−3=8. N4=11−3=8. N2=min(8−4,8−5)=min(4,3)=3. N3=8−5=3. Start=min(3−3,3−2)=min(0,1)=0.

Critical path: Start→A→D→E→End (3+5+3=11). Float for B=3−0−2=1. Float for C=8−3−4=1.

A resource histogram plots total resource usage (workers, machines) over each time period. When the histogram has a peak, more resources needed than are available, resource levelling fixes it by rescheduling non-critical activities: shift them later by up to their float amount. Critical activities cannot be moved because they have zero float.

Resource levelling reschedules non-critical activities (within their float) to smooth resource demand, moving activities later by up to their float without affecting project duration. Critical activities cannot be moved.

Pause, copy the levelling rule: non-critical activities may be shifted later by up to their float without affecting project duration; critical activities (float = 0) cannot be moved at all into your book.

Which item does NOT belong with the backward scan?

HSC Exam Technique

Identifying question type

If the question asks…	Use this method
Minimum total connection / minimum cable	Kruskal's / Prim's MST
Shortest route between two points	Dijkstra's algorithm
Earliest each activity can start	Forward scan → EST
Latest an activity can start without delay	Backward scan → LST
Which activities can be delayed / have slack	Float = LST(end) − EST(start) − duration
Minimum project time / which activities to speed up	Critical path analysis + crashing
Draw a schedule / resource chart	Gantt chart from EST values
Can the network have an Euler circuit?	Count odd-degree vertices (0 = yes)

Common exam errors, and how to avoid them

Forward scan: forgetting to take the MAXIMUM when two paths meet → always compare all incoming paths.
Backward scan: taking maximum instead of minimum when paths diverge → it is minimum on the way back.
Float calculation: using EST of end node instead of LST of end node → always use LST.
Crashing: crashing a non-critical activity → only crash critical activities to reduce project time.
Gantt chart: drawing bars from 0 instead of EST → each bar starts at the activity's own EST.
Spanning tree: forgetting the n−1 edge rule → always verify after constructing the tree.
Degree: forgetting loops count as 2 → re-read vertex description carefully.

Question: A building project has these activities. Find the minimum project duration, critical path, and float for any non-critical activities. Then state the effect of delaying activity R by 2 days.

Activity	Duration (weeks)	Depends on
P	2
Q	4	P
R	3	P
S	5	Q
T	4	Q, R
U	2	S, T

Step 1, Forward scan:

N1(Start)=0, N2(after P)=2, N3(after Q)=6, N4(after R)=5
N5(after S, from Q)=6+5=11
N6(after T, from Q and R): T needs both Q and R. EST=max(6,5)+4=max(6,5)+4=6+4=10. Wait: merge Q(6) and R(5) before T. EST(merge)=max(6,5)=6. EST(after T)=6+4=10.
N7(End): needs S and T both done. EST=max(11,10)+2=11+2=13.

Step 2, Backward scan:

N7=13. Before U merge: 13−2=11. N5(after S)=11. N6(after T)=11. N3(before S and before T merge): min(11−5, 11−4)=min(6,7)=6. N4(before T merge with R side): 11−4=7. N2(after P): min(6−4, 7−3)=min(2,4)=2. N1=2−2=0.

Step 3, Node boxes: N1(0,0)✓, N2(2,2)✓, N3(6,6)✓, N4(5,7) float, N5(11,11)✓, N6(10,11) float, N7(13,13)✓

Critical path: Start→P→Q→S→U→End (2+4+5+2=13 weeks).

Float for R: 7−2−3=2 weeks. Float for T: 11−6−4=1 week.

Effect of delaying R by 2 days: R has 2 weeks float. A 2-week delay uses up R's entire float, R is now critical. T (which depends on Q and R) would previously start at EST 6 (Q finishes first), but if R is delayed to start at week 4 (EST 2 + delay 2 = start week 4, finish week 7), T's start changes to max(6, 7)=7, T finishes week 11. U still starts week 11. Project not delayed, it still completes in 13 weeks. However, R now has zero float and any further delay to R would delay the project.

After shifting non-critical activities within their float, verify the levelled schedule with three checks: the total project duration is unchanged (critical path not disturbed), all precedence constraints are still respected (no activity starts before its predecessors finish), and no activity has been moved past its latest start time. Present the revised histogram or Gantt chart as evidence.

After resource levelling, check the schedule is still valid: total project duration unchanged, all precedence constraints respected, and no activity moved beyond its latest start time. Present the revised Gantt chart or histogram as evidence.

Pause, copy the three post-levelling checks: (1) total project duration unchanged; (2) all precedence constraints still satisfied; (3) no activity starts after its LST, then present the revised Gantt chart or histogram into your book.

To find the shortest route between two points in a weighted network, use _______ algorithm. To find the minimum total connection, use _______ or Prim's algorithm.

Activities

Multiple Choice

Short Answer

Answers

Activity	Duration (days)	Depends on
A, Requirements	5
B, UI Design	4	A
C, Backend	8	A
D, Testing	3	B, C
E, Deployment	2	D

Show MC Answers

Q1 → B (9)Spanning tree of n vertices has n−1 = 10−1 = 9 edges.

Q2 → D (0)Dijkstra's source vertex starts with label 0.

Q3 → CFloat = 0 means the activity is on the critical path. Any delay delays the project.

Q4 → C (6)Sum of degrees = 4+3+3+2 = 12 = 2×6 edges.

Q5 → D (16)A delay of 3 days is within the 4-day float, so the project duration is unchanged at 16 days.

Show SAQ Model Answers

SAQ 1: (a) Σdeg = 3+4+2+3 = 12 = 2×6 edges. ✓ (b) Odd-degree vertices: A(3), C not odd, B(4) even, D(3) odd. Odd-degree vertices are A and D (both have degree 3). Two odd-degree vertices → Euler trail exists, starting at A and ending at D (or vice versa). (c) Spanning tree of 4 vertices: 4−1 = 3 edges.

SAQ 2: Forward: Start=0, after J=6, after K=10, after L=9, after M: max(10+5,9+5)=max(15,14)=15, End=15+2=17. Backward: End=17, before N=15, before M from K: 15−5=10, before M from L: 15−5=10. After J from K: 10−4=6. After J from L: 10−3=7. After J=min(6,7)=6. Start=6−6=0. Critical path: Start→J→K→M→N (6+4+5+2=17). Float for L=10−6−3=1 day. Gantt: J(0→6), K(6→10), L(6→9+float window 9→10), M(10→15), N(15→17).

SAQ 3: Kruskal's algorithm finds the minimum spanning tree, it selects edges to minimise total weight while connecting all vertices (no cycles). Decision rule: always pick the lowest-weight edge that doesn't create a cycle. CPA finds the longest path through an activity network, it identifies which activities determine the minimum completion time. Decision rule: at each merge node, take the maximum (latest arriving predecessor). Both work on graphs, but Kruskal's minimises (sum of edge weights) while CPA maximises (longest path = minimum time before all work is done).