Module 6 · Networks and Critical Paths

Module Review

MST-12-S2-07 synthesis · HSC exam technique · Complete problem-solving workflow

MST-12-S2-07 MS-N2 + MS-N3 Lesson 12 of 12
Your guided path0 of 7 done · keep going
1
You are here

Orient and prepare

Retrieve the key network and critical-path rules before the module synthesis.

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

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).
2

Review network concepts

Consolidate degree, paths, trees, MST and shortest-path methods.

1

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.
Quick Review Example, Degree and spanning tree

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.

A connected graph has 8 vertices. Its minimum spanning tree contains exactly how many edges?
3

Review critical path analysis

Consolidate scans, float, Gantt charts and crashing.

2

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.
Complete CPA Workflow, Condensed Example

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?
4

Prepare for exam questions

Choose the correct network method and avoid common errors.

3

HSC Exam Technique

Identifying question type

If the question asks… Use this method
Minimum total connection / minimum cableKruskal's / Prim's MST
Shortest route between two pointsDijkstra's algorithm
Earliest each activity can startForward scan → EST
Latest an activity can start without delayBackward scan → LST
Which activities can be delayed / have slackFloat = LST(end) − EST(start) − duration
Minimum project time / which activities to speed upCritical path analysis + crashing
Draw a schedule / resource chartGantt 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.
HSC-Style Question, Full worked solution

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

Activity Duration (weeks) Depends on
P2
Q4P
R3P
S5Q
T4Q, R
U2S, 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): T needs both Q and R, so merge them first. EST(merge) = max(6, 5) = 6, and 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 weeks: 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.
5

Apply the module methods

Complete mixed network and CPA problems under exam-style conditions.

Activities

Activity 1, Complete CPA from Scratch

A software development project has these activities:

Activity Duration (days) Depends on
A, Requirements5
B, UI Design4A
C, Backend8A
D, Testing3B, C
E, Deployment2D
  1. Draw the activity network.
  2. Perform forward and backward scans. Show all EST and LST in a table.
  3. State the critical path and minimum project duration.
  4. Calculate float for all non-critical activities.
  5. Draw a Gantt chart. Show float windows for non-critical activities.
  6. Backend (C) can be crashed from 8 to 6 days. What is the new minimum project duration?

Activity 2, MS-N2 Mixed Review

A telecommunications network has 6 towers (vertices) with the following connections and weights (km of cable):

A–B(3), A–C(5), B–C(2), B–D(7), C–D(4), C–E(6), D–E(3), D–F(5), E–F(2).

  1. What is the degree of vertex C? (Check: how many edges connect to C?)
  2. Using Kruskal's algorithm, find the minimum spanning tree. State the edges selected and the total weight.
  3. Using Dijkstra's algorithm, find the shortest path from A to F. Show the table of labels.
  4. Does this network have an Euler circuit? Justify using vertex degrees.
6

Show what you can do

Complete the fixed drills and short-answer questions, then check each worked answer.

Multiple Choice

Q1. A connected network has 10 vertices. Its minimum spanning tree has:

Q2. In Dijkstra's algorithm, the source vertex is given initial label:

Q3. Activity K has float = 0. This means activity K is:

Q4. A network has four vertices with degrees 4, 3, 3, 2. How many edges does it have?

Q5. A project's minimum duration is 16 days. A non-critical activity has 4 days float. If that activity is delayed by 3 days, the project duration is:

Short Answer

SAQ 1 (MS-N2). A network has vertices A(degree 3), B(degree 4), C(degree 2), D(degree 3). (a) Verify the degree sum theorem. (b) An Euler trail requires exactly 2 odd-degree vertices, does this network qualify? State which vertices would be the start and end. (c) How many edges does a spanning tree of this 4-vertex network need?

SAQ 2 (MS-N3). A project has activities: J(6), K(4) after J, L(3) after J, M(5) after K and L, N(2) after M. Perform the complete CPA workflow. State: minimum project duration, critical path, float for all activities, and the Gantt chart bar positions for each activity.

SAQ 3 (synthesis). Explain the difference between Kruskal's algorithm and critical path analysis. Both involve making decisions about edges/activities in a network, what is each trying to achieve, and how do the decision rules differ?

Answers

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 → C Float = 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).

7

Retrieve, reflect and finish

Return to the opening problem, mark the lesson complete and choose the next destination.

Revisit, Think First Answers

(a) Degree sum theorem: Σ degrees = 2 × |edges|. A loop counts as 2 towards degree.

(b) Spanning tree edges: A spanning tree of n vertices always has n − 1 edges.

(c) EST forward scan rule: At each node, take the MAXIMUM of all incoming (predecessor EST + duration) values.

(d) Float formula: Float = LST(end node) − EST(start node) − duration.

(e) Crashing rule: Only crash CRITICAL PATH activities. When there are multiple critical paths, crash at least one activity on every critical path (or a shared activity) simultaneously.

Module 6 Complete!

You have completed all 12 lessons covering MS-N2 (Network Concepts) and MS-N3 (Critical Path Analysis). You are ready to tackle HSC exam questions on this module.