The Chinese postman problem Problem set B Worked solutions

Answer these questions about the graph.

1. (a) Write down the degree of each vertex and say which are odd.

   • Degrees: A 2, B 2, C 3, D 3, E 2.
   • Odd vertices: C and D.

2. (b) Which edges must be repeated in a shortest Chinese postman route?

   • Shortest path from C to D: C–D = 7.

3. (c) Find the length of the route.

   • 38 + 7 = 45.

A lifeguard must walk along every boardwalk on the beach shown, starting and finishing at A. The numbers are lengths in metres. Find the length of the shortest route and state which boardwalks are walked twice.

• Odd vertices: B and E.
• Paths: B–A–F–E = 12; B–E = 14; B–C–D–E = 21.
• Repeat B–A–F–E.
• 47 + 12 = 59.

Look at the graph.

1. (a) Write down the four odd vertices.

   • Degrees: A 2, B 3, C 3, D 2, E 2, F 3, G 3, H 2.

2. (b) Compare the three pairings of the odd vertices. Use the shortest path for each pair.

   • BC (11) + FG (6) = 17
   • BF (12) + CG (9) = 21
   • BG (18) + CF (15) = 33

3. (c) State which edges are repeated and the length of the shortest route.

   • Smallest: 17.
   • Route length 87 + 17 = 104.

Write out a shortest route that begins and ends at A and uses every edge. State its length.

• Odd vertices C and D: repeat CE (9), ED (2).
• Route: A–B–C–D–E–C–E–D–A.
• Check: 8 edges walked; 56 + 11 = 67.

A ranger must walk along every trail of a forest, starting at the main gate A and finishing at the lookout hut B. The graph shows the trails, with lengths in km.

1. (a) Find the length of the shortest route that starts at A, finishes at B and covers every edge.

   • Degrees: A 3, B 3, C 3, D 5, E 2, F 2. Odd vertices: A, B, C, D.
   • A and B can stay odd. Only C and D need fixing: C–E–D = 9; C–D = 10.
   • Repeat C–E–D. 89 + 9 = 98.

2. (b) The route must now finish where it started, at A. How much longer is the shortest route?

   • AB + CD = 11 + 9 = 20; AC + BD = 23 + 8 = 31; AD + BC = 14 + 12 = 26.
   • Smallest 20: 89 + 20 = 109.
   • 109 − 98 = 11.

A snow plough must clear every road shown and return to the garage at A. The numbers are lengths in km.

1. (a) Find the length of the shortest route.

   • Odd vertices C and D: repeat C–D = 10.
   • 62 + 10 = 72 km.

2. (b) The vehicle travels at a steady 15 km/h. Find the time in minutes.

   • 72 ÷ 15 = 4.8 hours
   • 72 ÷ 15 × 60 = 288 minutes.

A cyclist wants to ride along every cycle path shown, starting and finishing at A. The numbers are lengths in km.

1. (a) Compare the three ways of pairing the odd vertices and state which roads are repeated.

   • BC (9) + DE (7) = 16
   • BD (4) + CE (15) = 19
   • BE (11) + CD (13) = 24
   • Smallest 16: repeat BC (9), DE (7).

2. (b) Find the length of the shortest route.

   • 62 + 16 = 78.

A museum cleaner must go along every gallery passage shown, starting and finishing at A. The numbers are lengths in metres. Find the shortest route, write it out and give its length.

• AB (7) + CD (9) = 16
• AC (13) + BD (11) = 24
• AD (4) + BC (13) = 17
• Repeat AB (7), CD (9). Route: A–B–A–D–C–D–E–C–B–F–A.
• 68 + 16 = 84.

A new path of length 11 is built directly between C and D. Find the new length of the shortest route that covers every path and returns to the start. Is it shorter than before? Explain.

• Before: odd vertices C and D, repeat C–D (13), route 67.
• With the new path, C and D are even. All vertices are even, so no repeats.
• New route: 54 + 11 = 65, which is 2 shorter.

The weights on the graph are lengths.

1. (a) Find the length of the shortest route that starts and finishes at A and covers every edge.

   • BC (4) + FG (12) = 16
   • BF (8) + CG (11) = 19
   • BG (15) + CF (12) = 27
   • 96 + 16 = 112.

2. (b) The route now starts and finishes at E. Does the length change? Give a reason.

   • The repeated edges depend only on which vertices are odd.
   • The route is a closed circuit, so any start gives the same length, 112.