The Chinese postman problem Problem set A One question at a time

Use 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 = 4.

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

   • 45 + 4 = 49.

A gardener must walk along every path in the grounds shown, starting and finishing at A. The numbers are lengths in metres. Find the length of the shortest route and state which paths are walked twice.

• Odd vertices: B and E.
• Paths: B–C–D–E = 9; B–E = 10; B–A–F–E = 32.
• Repeat B–C–D–E.
• 51 + 9 = 60.

Use the graph below.

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 (13) + FG (11) = 24
   • BF (8) + CG (15) = 23
   • BG (19) + CF (21) = 40

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

   • Smallest: 23.
   • Route length 87 + 23 = 110.

Find a Chinese postman route that starts and finishes at A. Write it out and give its length.

• Odd vertices C and D: repeat CD (2).
• Route: A–B–C–D–C–E–D–A.
• Check: 7 edges walked; 48 + 2 = 50.

A postal worker must walk along every street of an estate, starting at the sorting office A and finishing at the school B. The graph shows the streets, with lengths in hundreds of metres.

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 2, D 2, E 3, F 5. Odd vertices: A, B, E, F.
   • A and B can stay odd. Only E and F need fixing: E–B–F = 8; E–F = 10.
   • Repeat E–B–F. 77 + 8 = 85.

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

   • AB + EF = 16 + 8 = 24; AE + BF = 12 + 4 = 16; AF + BE = 14 + 4 = 18.
   • Smallest 16: 77 + 16 = 93.
   • 93 − 85 = 8.

A street sweeper must clean every street shown and return to the depot 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 = 7.
   • 52 + 7 = 59 km.

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

   • 59 ÷ 20 = 2.95 hours
   • 59 ÷ 20 × 60 = 177 minutes.

A volunteer must deliver leaflets along every road 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 (8) + DE (6) = 14
   • BD (2) + CE (9) = 11
   • BE (8) + CD (10) = 18
   • Smallest 11: repeat BD (2), CE (9).

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

   • 57 + 11 = 68.

A security guard must walk along every corridor shown, starting and finishing at A. The numbers are lengths in metres. Find the shortest route, write it out and give its length.

• AB (14) + CD (6) = 20
• AC (18) + BD (10) = 28
• AD (15) + BC (4) = 19
• Repeat AD (15), BC (4). Route: A–B–C–B–F–A–D–C–E–D–A.
• 74 + 19 = 93.

A new path of length 13 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 (15), route 80.
• With the new path, C and D are even. All vertices are even, so no repeats.
• New route: 65 + 13 = 78, which is 2 shorter.

Use the graph. Edge weights are lengths.

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

   • BC (10) + FG (11) = 21
   • BF (5) + CG (8) = 13
   • BG (16) + CF (15) = 31
   • 94 + 13 = 107.

2. (b) The route now starts and finishes at D. 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, 107.