Year 12 · Networks
Quick tips — memory joggers
Building the network
Forward & backward scanning
Float & critical path
Network flow (max-flow, min-cut)
Level 1 · Fluency
In an activity network, what does the number written beside an activity represent?
The time (duration) the activity takes to complete.
In an activity network, what does an arrow (a directed edge) represent?
An activity (a task) to be carried out; the direction of the arrow shows the order in which activities are done.
In an activity network, what do the circles (nodes) represent?
Events — points in time marking the start and/or finish of activities.
Level 2 · Application
A project has activities with these dependencies: A and B can start immediately; C follows A; D follows A; E follows B and C. Explain, for activity E, what must be complete before it can start.
Both B and C must be finished before E can start (E has immediate predecessors B and C).
A project has these dependencies: P and Q can start immediately; R follows P; S follows Q and R. Explain, for activity S, what must be complete before it can start.
Both Q and R must be finished before S can start (S has immediate predecessors Q and R). Because R itself follows P, in effect P must be done before R, and Q done, before S begins.
In a project, activity T has immediate predecessors R and S. Activity R itself follows P, and S follows Q. List every activity that must be finished before T can begin.
R and S are the immediate predecessors, but R needs P first and S needs Q first, so P, Q, R and S must all be complete before T can begin.
Level 3 · Further Application
A project has the activities, durations and predecessors shown.
| Activity | Duration (h) | Immediate predecessor(s) |
|---|---|---|
| A | 4 | – |
| B | 6 | – |
| C | 3 | A |
| D | 8 | A |
| E | 5 | B, C |
| F | 2 | D, E |
| G | 9 | B, C |
(a) A and B (they have no predecessors).
(b) E and G both list C as a predecessor, so both require C to be complete.
A project has the activities and predecessors shown.
| Activity | Duration (h) | Immediate predecessor(s) |
|---|---|---|
| P | 5 | – |
| Q | 3 | – |
| R | 4 | P |
| S | 6 | P |
| T | 2 | R |
| U | 7 | S, Q |
(a) P and Q (they have no predecessors).
(b) R and S both list P as a predecessor, so both require P to be complete.
A project has the activities and predecessors shown.
| Activity | Duration (h) | Immediate predecessor(s) |
|---|---|---|
| A | 2 | – |
| B | 4 | A |
| C | 3 | A |
| D | 5 | B, C |
| E | 1 | B |
| F | 6 | D, E |
(a) B and C both list A as a predecessor.
(b) D — it has immediate predecessors B and C, so both must be complete first.
Level 1 · Fluency
The minimum completion time of a project equals the length of which path through the network?
The longest path from start to finish (the critical path).
The critical path of a project has a total length of 23 days. State the minimum time in which the whole project can be completed.
23 days
The minimum completion time equals the length of the critical path, so the project needs 23 days.
A project's critical path is A – C – F, with durations 5, 8 and 4 hours. State the minimum completion time for the project.
17 hours
Add the critical-path durations: 5 + 8 + 4 = 17 hours.
Level 2 · Application
Using the activity network below, find the minimum completion time for the project.
16 hours
Forward scan of event times: E₁=0, E₂=4, E₃=max(6, 4+3)=7, E₄=max(4+8, 7+5)=12, E₅=max(12+2, 7+9)=16. Minimum completion time = 16 hours.
Every path from start to finish through a project network has been listed with its total duration: Start–A–D = 11 days, Start–B–E = 14 days, Start–B–F = 9 days. Find the minimum completion time for the project.
14 days
The minimum completion time is the length of the longest path. Comparing 11, 14 and 9, the longest is Start–B–E = 14 days.
A project has the activity table below. By listing the paths from start to finish, find the minimum completion time.
| Activity | Duration (h) | Immediate predecessor(s) |
|---|---|---|
| A | 4 | – |
| B | 3 | – |
| C | 5 | A |
| D | 2 | B |
| E | 4 | C, D |
13 hours
Path A–C–E = 4 + 5 + 4 = 13 h; path B–D–E = 3 + 2 + 4 = 9 h. E must wait for the later of C and D, so the minimum completion time is the longer path = 13 hours.
Level 3 · Further Application
Using the activity network above:
| Activity | Earliest start (h) | Float (h) |
|---|---|---|
| D | ? | ? |
| F | ? | ? |
(a) 16 hours.
(b) A – C – G (4 + 3 + 9 = 16).
(c) D: earliest start 4, float 2. F: earliest start 12, float 2.
A project has the activity table below.
| Activity | Duration (h) | Immediate predecessor(s) |
|---|---|---|
| A | 3 | – |
| B | 7 | – |
| C | 4 | A |
| D | 2 | B, C |
(a) 9 hours. (b) B – D (and A – C – D). (c) C: earliest start 3 h, float 0 h.
D must wait for the later of B (finishes at 7) and A–C (finishes at 3 + 4 = 7). Both give 7, so D starts at 7 and finishes at 7 + 2 = 9 hours (a). Both paths equal 9, so there are two critical paths, A – C – D and B – D (b). (c) C's earliest start = 3 (after A). Latest start: D must start by 7, so C must finish by 7, giving latest start 7 − 4 = 3; float = 3 − 3 = 0.
The paths through a project network and their durations are: P–R–T = 12 days (critical), P–S = 8 days, Q–S = 10 days.
(a) 12 days. (b) 2 days.
(a) The longest path is P–R–T = 12 days, the minimum completion time.
(b) The longest path through S is 10 days, which is 12 − 10 = 2 days shorter than the critical path, so S has 2 days of float.
Level 1 · Fluency
What is found by forward scanning (from the start) of a network?
The earliest start time (EST) of each activity.
What is found by backward scanning (from the finish) of a network?
The latest start time (LST) of each activity.
When forward scanning, two paths lead into the same event. Do you take the largest or the smallest incoming total as the event time?
The largest — every predecessor must be finished, so you wait for the longest incoming path.
Level 2 · Application
Using the activity network above, use forward scanning to find the earliest start time of activities F and G.
Event times: E₃ = 7, E₄ = 12. F starts at event 4 (EST 12); G starts at event 3 (EST 7).
A project has the activity table below. By forward scanning, find the earliest start time of activity E.
| Activity | Duration (h) | Immediate predecessor(s) |
|---|---|---|
| A | 4 | – |
| B | 2 | – |
| C | 3 | A |
| D | 7 | B |
| E | 5 | C, D |
9 hours
C finishes at 4 + 3 = 7 h; D finishes at 2 + 7 = 9 h. E must wait for the later of its predecessors, so EST of E = max(7, 9) = 9 hours.
Activities P and Q both lead into the event where activity R begins. P has an earliest start of 3 h and duration 6 h; Q has an earliest start of 5 h and duration 2 h. Use forward scanning to find the earliest start time of R.
9 hours
P finishes at 3 + 6 = 9 h; Q finishes at 5 + 2 = 7 h. R starts at the later of the two, so EST of R = max(9, 7) = 9 hours.
Level 3 · Further Application
Using the activity network above:
6; 2 hours
(a) Backward scan: L₅ = 16, L₄ = 16 − 2 = 14. D finishes at event 4, so latest finish 14; LST = 14 − 8 = 6.
(b) Float = LST − EST = 6 − 4 = 2 hours.
A project has a minimum completion time of 20 hours. Activity H (duration 4 h) is the only activity leading into the finish event, and its earliest start time is 13 h.
16 h; 3 hours
(a) H must finish by the completion time, 20 h, so its latest finish is 20; LST = 20 − 4 = 16 h.
(b) Float = LST − EST = 16 − 13 = 3 hours.
In a project, the finish event has a latest time of 25 days. Activity K (duration 6 days) leads directly into the finish event. Activity J (duration 5 days) leads only into the start of K.
K: 19; J: 14; float 6 days
(a) K must finish by 25, so LST of K = 25 − 6 = 19. J must finish before K starts (by 19), so LST of J = 19 − 5 = 14.
(b) Float = LST − EST = 14 − 8 = 6 days.
Level 1 · Fluency
An activity has an earliest start time of 0. What does this tell you about its predecessors?
It has no predecessors — it can begin at the very start of the project.
An activity has an earliest start time greater than 0. What does this tell you about the activity?
It has at least one predecessor that must finish first, so it cannot start at the very beginning of the project.
Two activities both have an earliest start time of 0. What does this tell you about how the project begins?
Both activities have no predecessors, so the project starts with these two activities able to run in parallel from time 0.
Level 2 · Application
An activity has an earliest start time of 8 days. Explain what this means and what must be true about the activities before it.
It cannot begin until 8 days have passed; all of its preceding activities must be finished, and the longest chain of them takes 8 days.
An activity has an earliest start time of 12 hours. Explain what this means and what must be true about the activities before it.
It cannot begin until 12 hours have elapsed; every one of its predecessors must be complete, and the longest chain of predecessors leading to it takes 12 hours.
Two activities feed into the same event. One predecessor finishes at 7 h and the other finishes at 10 h. Explain why the next activity's earliest start time is 10 h, not 7 h.
The activity needs both predecessors complete before it can start, so it must wait for the slower (later) one. That is the one finishing at 10 h, so its EST is 10 h.
Level 3 · Further Application
Explain, using the ideas of predecessors:
(a) With no predecessors nothing must happen first, so it can start at time 0.
(b) The activity needs both predecessors finished; it must wait for the slower one, so its EST is the later (maximum) of the two finishing times.
Explain, using the ideas of predecessors:
(a) The activity cannot start until every predecessor is finished, so it must wait at least as long as the longest chain of them takes; its EST is therefore at least that total.
(b) EST is the maximum of the predecessors' finishing times. Adding another finishing time to a maximum can only make the maximum larger or leave it the same, so the EST cannot decrease.
Explain, using the ideas of predecessors:
(a) Nothing has to happen before the start event, so it is set to time 0 — the reference point from which all other times are measured.
(b) The activity waits for the later of its two predecessors' finishing times. Both finish at 6 h, so the maximum is 6 h and the activity can start immediately after, giving EST = 6 h.
Level 1 · Fluency
An activity has EST = 4 h, LST = 9 h. Calculate its float.
5 hours
Float = LST − EST = 9 − 4 = 5 hours.
An activity has EST = 3 h and LST = 11 h. Calculate its float.
8 hours
Float = LST − EST = 11 − 3 = 8 hours.
An activity has EST = 7 days and LST = 7 days. Calculate its float.
0 days (so it is critical)
Float = LST − EST = 7 − 7 = 0 days. A zero float means the activity is on the critical path.
Level 2 · Application
An activity has EST = 4 h, LST = 9 h and a duration of 3 h. Calculate its float and explain what it means for scheduling.
Float = 9 − 4 = 3 h. The activity can be delayed by up to 3 hours (or take up to 3 hours longer to start) without delaying the whole project.
An activity has EST = 5 h, LST = 12 h and a duration of 4 h. Calculate its float and explain what it means for scheduling.
Float = 7 h
Float = LST − EST = 12 − 5 = 7 h. The activity may start up to 7 hours late without delaying the whole project.
An activity has an earliest start of 6 h, a duration of 5 h and a latest finish of 15 h. Calculate its float.
Float = 4 h
First find the latest start: LST = latest finish − duration = 15 − 5 = 10 h. Float = LST − EST = 10 − 6 = 4 h.
Level 3 · Further Application
On a project the non-critical activities have floats of 1, 2, 0.5, 3 and 1.5 days.
(a) That activity can slip by at most half a day before it delays the project.
(b) The activity with float 0.5 days is least flexible — the smaller the float, the less it can be delayed before becoming critical.
Three activities have the earliest and latest start times shown.
| Activity | EST (h) | LST (h) |
|---|---|---|
| P | 2 | 5 |
| Q | 4 | 4 |
| R | 6 | 9 |
(a) P: 3 h, Q: 0 h, R: 3 h. (b) Q is critical.
(a) Float = LST − EST: P = 5 − 2 = 3 h; Q = 4 − 4 = 0 h; R = 9 − 6 = 3 h.
(b) Q has a float of 0 h, so Q is on the critical path.
The non-critical activities on a project have floats of 4, 1, 2.5 and 0.5 days.
(a) The activity with float 4 days, by up to 4 days. (b) The project finishes 1 day late.
(a) The largest float is 4 days, so that activity can be delayed by up to 4 days.
(b) The 2-day delay exceeds the 1-day float by 2 − 1 = 1 day, so the project is delayed by 1 day.
Level 1 · Fluency
What is the float of every activity on the critical path?
Zero.
Is the critical path the longest or the shortest path through the network?
The longest path from start to finish.
An activity has a non-zero float. Can it lie on the critical path?
No — every activity on the critical path has zero float.
Level 2 · Application
Explain why delaying an activity on the critical path delays the whole project, but delaying a non-critical activity (within its float) does not.
Critical activities have zero float, so any delay pushes out the finish time. A non-critical activity has spare time (float); a delay within that float is absorbed and the finish time is unchanged.
The critical path is the longest path through the network, yet it gives the minimum time to complete the project. Explain why this is not a contradiction.
Every activity must be completed, so the project cannot finish until the longest chain of dependent activities is done. No amount of work elsewhere can shorten that chain, so the longest path sets the earliest possible finish — which is therefore the minimum completion time.
A project network has two different paths that are both the longest, with equal length. Explain what this means for the critical path.
There are two critical paths. Every activity on either path has zero float, and delaying any of them delays the whole project.
Level 3 · Further Application
A project has a completion time of 16 hours.
(a) 18 hours — a delay on the critical path adds directly to the finish time.
(b) Still 16 hours: the 2-hour delay is within the 3-hour float, so it is absorbed and does not change the completion time.
A project has a completion time of 30 hours.
(a) 32 hours. (b) 2 hours.
(a) The 5 h float absorbs 5 h of the delay; the remaining 7 − 5 = 2 h pushes out the finish, giving 30 + 2 = 32 hours.
(b) The delay exceeds the float by 7 − 5 = 2 hours.
A project has a completion time of 24 days, with a single critical path.
(a) Not necessarily.
(b) Shortening the critical path may allow another path to become the new (longest) critical path. Once a different path becomes critical, further shortening of the first activity no longer reduces the completion time, so the saving can be less than 3 days.
Level 1 · Fluency
An activity has EST = 8 h and LST = 8 h. Is it on the critical path?
Yes — its float is 8 − 8 = 0, so it is critical.
An activity has EST = 5 h and LST = 9 h. Is it on the critical path?
No.
Float = LST − EST = 9 − 5 = 4 h. Since the float is not zero, the activity is not on the critical path.
Which activities make up the critical path — those with the largest float, those with the smallest duration, or those with zero float?
Those with zero float.
Level 2 · Application
Activity F has EST = 8 h, LST = 8 h and duration 5 h. State its float and whether it lies on the critical path.
is
Float = 8 − 8 = 0, so F is on the critical path.
Three activities have the earliest and latest start times shown. Calculate each float and state which activities lie on the critical path.
| Activity | EST (h) | LST (h) |
|---|---|---|
| P | 2 | 2 |
| Q | 2 | 5 |
| R | 8 | 8 |
P and R are on the critical path.
Float = LST − EST: P = 2 − 2 = 0; Q = 5 − 2 = 3; R = 8 − 8 = 0. Zero float means critical, so P and R lie on the critical path (Q does not).
Activity K has EST = 6 h and LST = 6 h. Activity L has EST = 6 h and LST = 10 h. State which of K and L is critical and explain.
K is critical; L is not.
K: float = 6 − 6 = 0, so K is critical. L: float = 10 − 6 = 4 h, so L has spare time and is not critical.
Level 3 · Further Application
In a project network:
6 hours
(a) Float = 10 − 4 = 6 hours.
(b) Increasing the duration by 3 h uses up 3 h of the 6 h float, leaving 3 h. The float is not exhausted, so G would still be non-critical (no new critical path forms).
In a project network, activity M has EST = 5 h, LST = 11 h and duration 4 h.
(a) 6 hours. (b) 6 hours.
(a) Float = LST − EST = 11 − 5 = 6 hours.
(b) Each extra hour of duration reduces the float by 1 hour, so the duration must increase by the whole float, 6 hours, to bring the float to 0 and make M critical.
The activities of a project have the floats shown (in hours).
| Activity | A | B | C | D | E |
|---|---|---|---|---|---|
| Float (h) | 0 | 2 | 0 | 5 | 0 |
(a) A, C, E. (b) Yes, a second critical path forms.
(a) The zero-float activities are A, C and E.
(b) Delaying B by exactly its 2 h float reduces B's float to 0, so B (and its path) becomes critical — a second critical path forms, though the completion time is still 18 h.
Level 1 · Fluency
A particular cut in a flow network has a capacity of 42 L/min. What can be said about the maximum flow — is it exactly 42, at most 42, at least 42, or impossible to tell?
At most 42 L/min.
At most 42 L/min. The maximum flow can never exceed the capacity of any cut.
The cuts in a flow network have capacities 30, 25 and 40 L/min. State the maximum flow.
25 L/min
By max-flow = min-cut, the maximum flow equals the smallest cut capacity = 25 L/min.
When calculating the capacity of a cut, which edges do you count — those crossing forward (source side to sink side), or every edge the cut line touches?
Only the edges crossing forward, from the source side to the sink side. Edges pointing backward (sink side to source side) are not counted.
Level 2 · Application
For the flow network below, calculate the capacity of the cut that separates {S} from {A, B, T} (i.e. the edges leaving S).
23 L/min
Edges leaving S: S→A (15) and S→B (8). Cut capacity = 15 + 8 = 23 L/min.
A cut in a flow network separates the source side {S, A} from the sink side {B, T}. The forward edges crossing the cut are A→B (capacity 9) and A→T (capacity 12). There is also an edge B→A (capacity 4) crossing backward. Calculate the capacity of this cut.
21 L/min
Count only forward edges (source side to sink side): A→B (9) and A→T (12). Cut capacity = 9 + 12 = 21 L/min. The backward edge B→A is not counted.
The possible cuts in a pipe network have capacities 34, 28, 30 and 41 kL/h.
(a) 28 kL/h. (b) It is the minimum cut (the bottleneck).
(a) Max-flow = min-cut = the smallest cut capacity = 28 kL/h.
(b) Because the flow equals this cut's capacity, it is the minimum cut — the bottleneck that limits the flow of the whole network.
Level 3 · Further Application
For the flow network above:
23 L/min
(a) A→B = 15 − 12 = 3 L/min. Inflow to B = 3 (from A) + 8 (from S) = 11 L/min.
(b) B→T = 11 L/min (all of B’s inflow). Maximum flow to T = 12 (A→T) + 11 (B→T) = 23 L/min — equal to the minimum cut.
Water flows from source S to sink T. Two pipes leave S: S→A (capacity 10 L/min) and S→B (capacity 7 L/min). All flow reaches T through A→T (capacity 6 L/min) and B→T (capacity 12 L/min).
(a) 6 L/min. (b) 13 L/min.
(a) A can receive up to 10 L/min from S, but its only outlet A→T carries at most 6 L/min, so the flow through A is limited to 6 L/min.
(b) Through B: S→B allows 7 L/min and B→T allows up to 12, so 7 L/min passes. Maximum flow = 6 + 7 = 13 L/min.
Water flows from S to T. The three cuts in the network have capacities: cut 1 = 26, cut 2 = 19, cut 3 = 22 (all ML/day). The town's demand is 21 ML/day.
(a) 19 ML/day. (b) Not met; shortfall 2 ML/day.
(a) Max-flow = min-cut = smallest cut = 19 ML/day.
(b) 19 < 21, so the network does not meet demand; the shortfall is 21 − 19 = 2 ML/day.
Level 1 · Fluency
In an activity table, a row reads “E, 5, predecessors B and C”. On the network, from where must activity E begin?
From the point where both B and C have finished (the event that B and C lead into).
In an activity table, activity K has “–” listed as its predecessor. On the network, from where does activity K begin?
From the start event (at time 0) — with no predecessor, K can begin immediately.
On a network, three activities all point into the same event, and activity W begins from that event. What does this tell you about W's predecessors?
W has three immediate predecessors — all three activities must be complete before W can start.
Level 2 · Application
Convert the first four rows of the activity table (A, B, C, D) into an activity network, then state which two activities start at the beginning.
| Activity | Duration | Predecessors |
|---|---|---|
| A | 4 | – |
| B | 6 | – |
| C | 3 | A |
| D | 8 | A |
A and B start at the beginning; C and D both start after A. A valid partial network is:
An activity table lists: P (–), Q (–), R after P, S after Q. Without drawing, describe how to build the network: which activities leave the start event, and from which events do R and S begin?
| Activity | Duration | Predecessors |
|---|---|---|
| P | 5 | – |
| Q | 3 | – |
| R | 4 | P |
| S | 2 | Q |
P and Q both leave the start event (neither has a predecessor). R begins from the event at the finish of P; S begins from the event at the finish of Q.
An activity table lists: A (–), B after A, C after A, D after both B and C. Without drawing, state how many activities leave the start event and how many arrows point into the event where D begins.
| Activity | Duration | Predecessors |
|---|---|---|
| A | 2 | – |
| B | 4 | A |
| C | 3 | A |
| D | 5 | B, C |
One activity (A) leaves the start event. Two arrows (B and C) point into the event where D begins.
Level 3 · Further Application
Using the full activity table (A–G) from earlier:
(a) The complete network is:
(b) Two activities lead into the finish (event 5): F and G.
A project has the activity table below.
| Activity | Duration | Predecessors |
|---|---|---|
| P | 5 | – |
| Q | 4 | – |
| R | 3 | P |
| S | 6 | P |
| T | 2 | Q |
| U | 7 | S, T |
(a) Two (P and Q have no predecessors).
(b) R and U lead into the finish — they are not listed as a predecessor of any other activity.
A project has the activity table below.
| Activity | Duration | Predecessors |
|---|---|---|
| A | 3 | – |
| B | 2 | – |
| C | 4 | A |
| D | 5 | A |
| E | 1 | B |
| F | 6 | C, D |
| G | 2 | E |
(a) A and B (no predecessors).
(b) F and G lead into the finish — neither is a predecessor of any other activity.
Level 1 · Fluency
A water network has a maximum flow of 120 kL/day and demand is 100 kL/day. Does the network currently meet demand?
Yes — the maximum flow (120) exceeds the current demand (100 kL/day).
A network has a maximum flow of 90 kL/day and demand is 105 kL/day. Does the network meet demand?
No.
The maximum flow (90) is less than the demand (105 kL/day), so the network does not meet demand.
A pipe network has a minimum cut of 60 ML/day. Demand is 60 ML/day. Does the network meet demand?
Yes, but only just.
Max-flow = min-cut = 60 ML/day, which equals the demand of 60 ML/day. It exactly meets demand, with no spare capacity.
Level 2 · Application
A water network has a maximum flow of 120 kL/day. Demand is forecast to grow to 135 kL/day. Determine whether the network will meet demand and, if not, the extra capacity needed.
not; 15 kL/day
135 > 120, so the network will not meet demand; an extra 135 − 120 = 15 kL/day of capacity is required.
A gas network has a maximum flow of 200 GJ/h. Demand is forecast at 245 GJ/h. Determine whether the network will meet demand and, if not, the extra capacity needed.
not; 45 GJ/h
245 > 200, so the network will not meet demand; an extra 245 − 200 = 45 GJ/h of capacity is required.
A network's cuts have capacities 80, 65 and 72 kL/day. Demand is 70 kL/day.
(a) 65 kL/day. (b) Not met; shortfall 5 kL/day.
(a) Max-flow = min-cut = smallest capacity = 65 kL/day.
(b) 65 < 70, so demand is not met; shortfall = 70 − 65 = 5 kL/day.
Level 3 · Further Application
A town’s water network has a maximum flow capacity of 850 kL/day. Current demand is 780 kL/day and grows by 4% per year.
3 years
(a) After 2 years: 780(1.04)² = 843.6 kL/day. After 3 years: 780(1.04)³ = 877.4 kL/day.
(b) 843.6 < 850 but 877.4 > 850, so the network first fails to meet demand after 3 years.
A network has a maximum flow capacity of 600 ML/day. Current demand is 540 ML/day and grows by 3% per year.
4 years
(a) After 3 years: 540(1.03)³ = 590.1 ML/day. After 4 years: 540(1.03)⁴ = 607.8 ML/day.
(b) 590.1 < 600 but 607.8 > 600, so the network first fails to meet demand after 4 years.
A network has a maximum flow of 1000 kL/day. Demand is 900 kL/day now and grows by 50 kL/day each year (a constant, linear increase).
(a) \(900 + 50n\) kL/day. (b) 3 years.
(a) Linear growth adds 50 each year, so demand \(= 900 + 50n\) kL/day.
(b) Solve \(900 + 50n > 1000\): \(50n > 100\), so \(n > 2\). At \(n = 2\) demand is exactly 1000 (just met), so it first exceeds capacity after 3 years.