L38 Solutions — Shortest Paths and Spanning Trees

1. Euler paths and circuits. Fluency

   • (a) All even degrees → Euler circuit exists (and hence also an Euler path).
   • (b) Exactly 2 odd-degree vertices → Euler path exists (start at one odd-degree vertex, end at the other), but no Euler circuit.
   • (c) Neither. An Euler path requires 0 or 2 odd-degree vertices. Four odd-degree vertices means no Euler path or circuit is possible.
   • (d) Edges: AB, BC, CD, DA, AC. deg(A)=3, deg(B)=2, deg(C)=3, deg(D)=2. Two odd-degree vertices (A, C) → Euler path exists (A to C or C to A), but no Euler circuit.

2. Kruskal's algorithm. Fluency

   • (a) AC=3, BC=4, BD=6, AB=7, CD=8, AD=10.
   • (b) Add AC(3). Add BC(4) — connects B. Add BD(6) — connects D. Skip AB(7): would create cycle A–B–C–A. Done (4 vertices, 3 edges). MST: AC, BC, BD.
   • (c) 3 + 4 + 6 = 13.
   • (d) 3 edges (n − 1 = 4 − 1 = 3).

3. Dijkstra's algorithm. Fluency

   • (a) Initial: A=0, B=∞, C=∞, D=∞.
   • (b) Visit A(0): B=5, C=2. Visit C(2): B=min(5, 2+3)=5, D=min(∞, 2+4)=6. Visit B(5): D=min(6, 5+8)=6. Visit D(6). Done.
   • (c) Shortest distance A to D = 6.
   • (d) Shortest path: A → C → D (cost 2+4=6).

4. Spanning trees. Fluency

   • (a) A path graph on 4 vertices (A–B–C–D) has 1 spanning tree — the path itself (no other spanning tree exists since it’s already a tree).
   • (b) 6 edges (n − 1 = 7 − 1 = 6).
   • (c) True — a spanning tree must include every vertex of the graph by definition.
   • (d) Total weight = 25 + 8 = 33. It is no longer a spanning tree — it now has n edges (too many) and contains a cycle.

5. Shortest path on a network diagram. Understanding

   • (a) A=0, B=∞, C=∞, D=∞, E=∞, F=∞.
   • (b) Step 1 — Visit A(0): B=4, C=6. Step 2 — Visit B(4): C=min(6, 4+3)=6, D=min(∞, 4+5)=9.
   • (c) Continuing: Visit C(6): E=min(∞, 6+8)=14. Visit D(9): E=min(14, 9+2)=11, F=min(∞, 9+7)=16. Visit E(11): F=min(16, 11+4)=15. Visit F(15). Shortest distance = 15.
   • (d) Shortest path: A → B → D → E → F (4+5+2+4=15).

6. MST on a network. Understanding

   • (a) DE=2, BC=3, AB=4, EF=4, AC=6, BD=5, CE=8, DF=7. (Full list from Q5 graph.)
   • (b) Add DE(2). Add BC(3). Add AB(4) — connects A. Add EF(4) — connects F. Add BD(5) — joins {A,B,C} with {D,E,F}. Done. MST: DE, BC, AB, EF, BD. Total = 2+3+4+4+5 = 18.
   • (c) 18.
   • (d) Shortest path A→F = 15; MST total = 18. They are different concepts: the MST connects all vertices at minimum total cost (used for wiring/cabling), while the shortest path finds the cheapest route between two specific vertices (used for navigation/routing).

7. Euler paths in context. Understanding

   • (a) Degrees: 4, 4, 2, 4, 2, 2 — zero odd-degree vertices.
   • (b) Yes — all vertices have even degree, so an Euler circuit exists. The postman can walk every street exactly once and return to the start.
   • (c) Adding two more odd-degree vertices would give 2 odd-degree vertices → Euler path (not circuit). To maintain an Euler circuit, all vertices must have even degree; adding 2 odd-degree vertices breaks this.
   • (d) 4 odd-degree vertices → 2k = 4, so k = 2. At least 2 streets must be repeated.

8. Comparing algorithms. Understanding

   • (a) A shortest path finds the minimum-weight route between two specific vertices. A minimum spanning tree finds the minimum-weight set of edges that connects all vertices.
   • (b) If there is only one spanning tree, the graph itself must be a tree (connected and acyclic).
   • (c) Yes — for example, in a path graph A–B–C, the MST is the entire graph, and the shortest path from A to C (A–B–C) is part of it. However this is not always true in graphs with cycles.
   • (d) A delivery driver visiting 5 stops should use a shortest-path algorithm (or a travelling-salesman approach) — they need the cheapest route visiting specific points, not a spanning tree which doesn’t optimise routes.

9. Network planning. Problem Solving

   • (a) With 5 vertices, the number of spanning trees can be large (Cayley's formula gives 5³ = 125 for K₅). Many possible spanning trees.
   • (b) Sort: BD=8, CD=9, AC=10, CE=11, BC=12, BE=14, AB=15, DE=16, AE=18, AD=20. Add BD(8). Add CD(9). Add AC(10) — connects A. Skip CE(11): creates cycle? No — CE connects E. Add CE(11). Done (5 vertices, 4 edges). MST: BD, CD, AC, CE.
   • (c) 8 + 9 + 10 + 11 = $38 000.
   • (d) MST has n−1 = 4 edges. ✓ (5 vertices − 1 = 4.)

10. Königsberg bridge problem. Problem Solving

    • (a) deg(A)=3 (odd), deg(B)=3 (odd), deg(C)=5 (odd), deg(D)=3 (odd). 4 odd-degree vertices.
    • (b) No. An Euler circuit requires all vertices to have even degree. With 4 odd-degree vertices, no Euler circuit exists — it is impossible to cross every bridge exactly once and return to start.
    • (c) No. An Euler path requires exactly 0 or 2 odd-degree vertices. With 4 odd-degree vertices, not even a one-way Euler path is possible.
    • (d) We need to change 4 odd-degree vertices to even. Each bridge added/removed changes the parity of 2 vertices. We need to fix all 4 odd vertices → at least 2 bridges added or removed.