L39 Solutions — Network Applications

1. Choosing the right method. Fluency

   • (a) Kruskal's minimum spanning tree algorithm — goal is to connect all 8 towns at minimum total cost.
   • (b) Dijkstra's shortest path algorithm — finds the minimum-weight route between two specific vertices.
   • (c) An Euler circuit (or Euler path) — every street (edge) must be traversed at least once, starting and ending at the depot.
   • (d) Critical path analysis — find the longest path through the activity network; this gives the minimum possible completion time.

2. Critical path. Fluency

   • (a) Two paths: Start → A → C → End and Start → B → C → End.
   • (b) Start→A→C→End = 4+3+2 = 9 days. Start→B→C→End = 2+7+2 = 11 days.
   • (c) Critical path: Start → B → C → End (11 days). This is the longest path, so 11 days is the minimum project time.
   • (d) Float for A = critical path length − path through A = 11 − 9 = 2 days. Activity A can be delayed by up to 2 days without delaying the project.

3. MST in context. Fluency

   • (a) Sorted: C–D=10, B–C=15, D–E=18, A–C=20, B–D=25, A–B=30, C–E=35.
   • (b) Add C–D(10). Add B–C(15) — connects B. Add D–E(18) — connects E. Add A–C(20) — connects A. Done (5 vertices, 4 edges). Skip B–D(25): creates cycle. MST: C–D, B–C, D–E, A–C.
   • (c) 10 + 15 + 18 + 20 = $63.
   • (d) Total of all 7 cables: 30+20+15+25+10+35+18 = $153. Saving = 153 − 63 = $90.

4. Shortest path in context. Fluency

   • (a) Dijkstra from H: H=0, A=3, B=5 (initial). Visit A(3): B=min(5, 3+2)=5, C=7. Visit B(5): C=min(7, 5+1)=6, D=11. Visit C(6): D=min(11, 6+3)=9. Visit D(9). Shortest time = 9 minutes.
   • (b) Trace back from D: D←C(6+3=9), C←B(5+1=6), B←H. Fastest route: H → B → C → D = 5+1+3 = 9 minutes.
   • (c) With A–B closed, the path H→B→C→D is unaffected (it doesn’t use A–B). Shortest path remains H → B → C → D = 9 minutes. The closure has no effect on the optimal route.
   • (d) Distances: A=3, B=5, C=6, D=9. D is hardest to reach (9 minutes) — it is the furthest location and requires traversing multiple edges.

5. Critical path analysis. Understanding

   • (a) Three paths: S→A→C→E→F, S→A→D→E→F, S→B→D→E→F.
   • (b) S→A→C→E→F = 2+6+5+3 = 16 weeks. S→A→D→E→F = 2+1+5+3 = 11 weeks. S→B→D→E→F = 4+3+5+3 = 15 weeks.
   • (c) Critical path: S → A → C → E → F = 16 weeks. This is the longest path; minimum project duration is 16 weeks.
   • (d) If A→C drops to 4 weeks: S→A→C→E→F = 2+4+5+3 = 14 weeks. But S→B→D→E→F = 15 weeks becomes the new critical path. Project now takes 15 weeks (reduced by 1 week, not 2). The bottleneck shifts to the B→D path.

6. Transport network. Understanding

   • (a) Dijkstra from A: A=0, B=8, C=12. Visit B(8): C=12 (unchanged), D=18. Visit C(12): D=18 (unchanged), E=27. Visit D(18): E=min(27, 18+6)=24, F=27. Visit E(24): F=min(27, 24+4)=27 (unchanged). Visit F(27). Shortest time = 27 minutes.
   • (b) Trace: F←D(18+9=27), D←B(8+10=18), B←A. Fastest route: A → B → D → F = 8+10+9 = 27 minutes.
   • (c) Sort: E–F=4, B–C=5, D–E=6, C–D=7, A–B=8, D–F=9, B–D=10, A–C=12, C–E=15. Kruskal’s: Add E–F(4), B–C(5), D–E(6), C–D(7), A–B(8) — done (6 vertices). MST: E–F, B–C, D–E, C–D, A–B. Total = 4+5+6+7+8 = 30 minutes.
   • (d) Yes — the direct A–F route (18 min) is shorter than the current shortest (27 min). New shortest path: A → F = 18 minutes directly.

7. Chinese Postman application. Understanding

   • (a) No — degrees are 2, 4, 3, 3, 4, 2. Two vertices have odd degree (the two degree-3 vertices). An Euler circuit requires all vertices to have even degree.
   • (b) To create an Euler circuit, the plough must repeat the shortest path between the two odd-degree vertices. This means at least 1 extra road pass.
   • (c) The two vertices with degree 3 cause the problem. All other vertices already have even degree.
   • (d) The minimum extra distance = length of the shortest path between the two odd-degree vertices = 0.8 km (the direct connecting road).

8. Network design trade-offs. Understanding

   • (a) The MST sacrifices redundancy. Every edge in the MST is a single point of failure — there are no alternative paths between any two nodes. Full connection provides multiple routes between every pair of nodes.
   • (b) If one MST edge fails, the network splits into two disconnected components — some nodes can no longer communicate. Full connection: alternative paths exist, so connectivity is maintained even when edges fail.
   • (c) Full connection is justified when uptime is critical — for example hospitals, emergency services, financial systems, or data centres where network failure has severe consequences.
   • (d) MST + 2 extra edges creates redundant loops. If any single edge in those loops fails, an alternative path exists. This provides resilience at a fraction of the full-connection cost — a practical engineering compromise.

9. Project scheduling. Problem Solving

   • (a) Network: Start→A(3)→B(5)→D(6)→F(3)→G(1)→End. Also A→C(4)→E(7)→F, and B→E (E requires both B and C). So edges: Start→A, A→B, A→C, B→D, B→E, C→E, D→F, E→F, F→G.
   • (b) Path 1: Start→A→B→D→F→G = 3+5+6+3+1 = 18 days. Path 2: Start→A→B→E→F→G = 3+5+7+3+1 = 19 days. Path 3: Start→A→C→E→F→G = 3+4+7+3+1 = 18 days.
   • (c) Critical path: Start → A → B → E → F → G = 19 days. Minimum project time is 19 days.
   • (d) To save 2 days: reduce A by 2 days (3→1) — all three paths shorten by 2 (to 16, 17, 16), making the project 17 days. Alternatively reduce critical-path activities A, B, E, F, or G totalling 2 days. No effect: accelerating C or D cannot shorten the project — they are not on the critical path.

10. Network optimisation. Problem Solving

    • (a) MST has n−1 = 7−1 = 6 edges.
    • (b) Sort: E–F=6, B–C=7, C–E=8, A–C=9, F–G=9, D–F=10, B–E=11, C–D=12, E–G=13, A–B=14, C–F=15, A–D=18. Kruskal’s: Add E–F(6). Add B–C(7). Add C–E(8) — joins {B,C} to {E,F}. Add A–C(9) — connects A. Add F–G(9) — connects G. Add D–F(10) — connects D. Done. MST: E–F, B–C, C–E, A–C, F–G, D–F.
    • (c) 6+7+8+9+9+10 = $49 000.
    • (d) After 30% increase: B–C=9.1, C–E=10.4, A–C=11.7. Re-running Kruskal’s yields the same set of MST edges (each C-edge is still cheaper than any non-C alternative). Total cost increases to 6+9.1+10.4+11.7+9+10 = $56 200.