Sign in to jmaths to print this page or save it as a PDF: jmaths-8ce638778fd6.herokuapp.com/maths/ai-hl/graph-theory/ahl-1-10/problems/

jmaths

IB Mathematics: Applications and Interpretation HL · AHL 1: Graph Theory · AHL 1.10

Name Date

The Chinese postman problem Problem set A

Find the odd vertices first. Show the paths you compare and the repeated edges. No calculator is needed.

Difficulty: first skills applying them stretch

Skills

  1. Use the graph.

    13124637ABCDE
    1. (a) Write down the degree of each vertex and say which are odd.
    2. (b) Which edges must be repeated in a shortest Chinese postman route?
    3. (c) Find the length of the route.

  2. 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.

    1223413710ABCFED

  3. Use the graph below.

    51339116781510ABCDEFGH
    1. (a) Write down the four odd vertices.
    2. (b) Compare the three pairings of the odd vertices. Use the shortest path for each pair.
    3. (c) State which edges are repeated and the length of the shortest route.

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

    143261310ABCDE

  5. 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.

    1071114412694DFCBEA
    1. (a) Find the length of the shortest route that starts at A, finishes at B and covers every edge.
    2. (b) The route must now finish where it started, at A. How much longer is the shortest route?

In context

  1. A street sweeper must clean every street shown and return to the depot at A. The numbers are lengths in km.

    347135119ABCDE
    1. (a) Find the length of the shortest route.
    2. (b) The vehicle travels at a steady 20 km/h. Find the time in minutes.

  2. A volunteer must deliver leaflets along every road shown, starting and finishing at A. The numbers are lengths in km.

    1078296411ABCDEF
    1. (a) Compare the three ways of pairing the odd vertices and state which roads are repeated.
    2. (b) Find the length of the shortest route.

  3. 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.

    144615751112ABCDEF

Stretch

  1. 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.

    11615421314ABCDE

  2. Use the graph. Edge weights are lengths.

    610153119145813ABCDEFGH
    1. (a) Find the length of the shortest route that starts and finishes at A and covers every edge.
    2. (b) The route now starts and finishes at D. Does the length change? Give a reason.

jmaths.xyz · AI HL · AHL 1.10 The Chinese postman problem