T3T4 Review Solutions — Networks and Graphs

1. Graph terminology. Fluency

   • (a) 5 vertices, 6 edges.
   • (b) deg(A)=2, deg(B)=3, deg(C)=3, deg(D)=3, deg(E)=1.
   • (c) Sum = 2+3+3+3+1 = 12 = 2×6. ✓
   • (d) No. Vertices B, C, D have odd degree (3) and E has odd degree (1) — four odd-degree vertices. An Euler circuit requires all vertices to have even degree.

2. Handshaking lemma and degree sequences. Fluency

   • (a) Sum = 2 × 9 = 18.
   • (b) Sum = 5+4+3+2+2 = 16 (even). Possibly valid — the handshaking lemma is satisfied.
   • (c) 5×4/2 = 10 edges.
   • (d) n − 1 = 9 edges.

3. Kruskal's MST algorithm. Fluency

   • (a) S–T=3, Q–R=4, R–S=5, P–Q=6, R–T=7, Q–S=8, P–R=9.
   • (b) Add S–T(3). Add Q–R(4). Add R–S(5) — joins {Q,R} to {S,T}. Add P–Q(6) — connects P. Done. MST: S–T, Q–R, R–S, P–Q.
   • (c) 3+4+5+6 = 18.
   • (d) n − 1 = 5 − 1 = 4 edges.

4. Dijkstra's shortest path. Fluency

   • (a) A=0, B=∞, C=∞, D=∞, E=∞.
   • (b) Visit A(0): B=7, C=3. Visit C(3): B=4, D=11. Visit B(4): D=6, E=9. Visit D(6): E unchanged (9). Visit E(9). Final: A=0, B=4, C=3, D=6, E=9.
   • (c) A → C → B → E = 3+1+5 = 9.
   • (d) C, at distance 3.

5. Reading a weighted network. Understanding

   • (a) 1→2→4→6 = 5+7+4 = 16. 1→2→5→6 = 5+9+2 = 16. 1→2→3→5→6 = 5+3+6+2 = 16. 1→3→5→6 = 8+6+2 = 16. 1→3→2→4→6 = 8+3+7+4 = 22.
   • (b) Minimum weight = 16. Example shortest paths: 1→2→4→6 or 1→3→5→6.
   • (c) Sorted edges: 5–6=2, 2–3=3, 4–6=4, 1–2=5, 3–5=6, 2–4=7, 1–3=8, 2–5=9. Kruskal’s: Add 5–6, 2–3, 4–6, 1–2, 3–5. Done. MST: 5–6, 2–3, 4–6, 1–2, 3–5. Total = 2+3+4+5+6 = 20.
   • (d) Original: deg(3) = 3 (edges to 1, 2, 5). MST: deg(3) = 2 (edges 2–3 and 3–5 only; edge 1–3 excluded).

6. Euler paths and circuits in context. Understanding

   • (a) Sum = 4+4+2+3+3+2+4+2 = 24. Edges = 24/2 = 12 streets.
   • (b) No — two vertices have odd degree (both degree-3 intersections). An Euler circuit requires all even degrees.
   • (c) With exactly 2 odd-degree vertices, the carrier repeats the shortest path between them — at minimum 1 extra street.
   • (d) Adding one street changes both odd-degree vertices to even degree. All vertices now have even degree → an Euler circuit exists.

7. Spanning trees. Understanding

   • (a) n − 1 = 11 edges.
   • (b) True — the shortest edge is always added first by Kruskal's without creating a cycle.
   • (c) n − 1 = 15 ⇒ n = 16 vertices.
   • (d) A spanning tree connects all n vertices with n−1 edges and no cycles. Adding any edge creates a second path between two vertices that are already connected → a cycle.

8. Critical path analysis. Understanding

   • (a) S→A→C→End = 5+4+2 = 11. S→A→D→End = 5+6+1 = 12. S→B→D→End = 3+8+1 = 12.
   • (b) Two critical paths tied at 12: S→A→D→End and S→B→D→End.
   • (c) Float for C = 12 − 11 = 1 day.
   • (d) Yes. S→B→D→End is a critical path (zero float). A 2-day delay to B extends this path to 14 days, delaying the project to 14 days.

9. Comparing network algorithms. Problem Solving

   • (a) Sort: D–E=15, B–C=20, C–E=25, A–C=30, C–D=35, B–D=40, A–B=50. Add D–E(15), B–C(20), C–E(25) — joins {B,C} to {D,E}. Add A–C(30) — connects A. Done. MST: D–E, B–C, C–E, A–C = 15+20+25+30 = 90 km.
   • (b) A=0. B=50, C=30. Visit C(30): B=50 (unchanged), D=65, E=55. Visit B(50): D=65 (unchanged). Visit E(55): D=65 (unchanged). Visit D(65). A→C→D = 30+35 = 65 km.
   • (c) No — the MST includes C–E (25) not C–D (35), optimising total cost. The shortest-path tree from A uses C–D and C–E to reach D and E directly. Different objectives produce different structures.
   • (d) Inspector needs an Euler path/circuit. MST degrees: A=1(A–C), C=3(A–C, B–C via C–E? wait: edges are D–E, B–C, C–E, A–C): A=1, B=1, C=3, D=1, E=2. Four odd-degree vertices (A, B, C, D) → no Euler path exists. Some roads must be repeated.

10. Network robustness and bridges. Problem Solving

    • (a) 84 000 + 12 000 + 15 000 = $111 000.
    • (b) All n−1 edges (every edge in a spanning tree is a bridge by definition).
    • (c) Each redundant cable creates one cycle, removing that cycle’s edges from being bridges. With 2 extra cables: at minimum 4 bridges remain (MST had 6 bridges; 2 cables can eliminate at most 2).
    • (d) Each extra cable eliminates at most 1 bridge. To eliminate all 6 (n−1 = 6) bridges from the MST: at minimum 6 additional cables are required.

11. Full algorithm application. Problem Solving

    • (a) A=0, B=4, C=7. Visit B(4): C=7 (unchanged), D=10. Visit C(7): D=10 (unchanged), E=15. Visit D(10): E=12, F=19. Visit E(12): F=min(19,12+4)=16. Visit F(16). Shortest = 16 min: A→B→D→E→F.
    • (b) Sort: D–E=2, B–C=3, A–B=4, E–F=4, C–D=5, B–D=6, A–C=7, C–E=8, D–F=9. Add D–E, B–C, A–B, E–F, C–D. Done. MST total = 2+3+4+4+5 = 18 minutes.
    • (c) Degrees: A=2, B=3, C=4, D=4, E=3, F=2. Odd-degree: B and E. No Euler circuit, but an Euler path exists (B to E or E to B).
    • (d) A→D→E→F = 11+2+4 = 17 min > 16 min. No change — existing route (16 min) remains shortest.

12. Networks in the real world. Problem Solving

    • (a) Kruskal's MST algorithm. Result: spanning tree with 7 edges connecting all 8 zones at minimum total pipe cost, no redundant loops.
    • (b) Run Dijkstra's algorithm from each candidate location. Choose the depot location that minimises the maximum or average response time across all 8 zones.
    • (c) 4 odd-degree vertices → pair them optimally (2 pairs) and duplicate the shortest path between each pair. Minimum extra passes = 2.
    • (d) Must shorten critical path by 2 months. Only critical-path activities (zero float) are candidates — accelerating activities with 3 or 5 months of float has no effect on the project end date.