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/b/

jmaths

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

Name Date

The Chinese postman problem Problem set B

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

Each question matches the question with the same number in set A. Do the ones you got wrong there.

Difficulty: first skills applying them stretch

Skills

  1. Answer these questions about the graph.

    2127683ABCDE
    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 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.

    582113414ABCFED

  3. Look at the graph.

    141137621012913ABCDEFGH
    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. Write out a shortest route that begins and ends at A and uses every edge. State its length.

    111512729ABCDE

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

    132127814121011CBAEDF
    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 snow plough must clear every road shown and return to the garage at A. The numbers are lengths in km.

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

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

    2129415758ABCDEF
    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 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.

    71394143126ABCDEF

Stretch

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

    510132897ABCDE

  2. The weights on the graph are lengths.

    104157126148119ABCDEFGH
    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 E. Does the length change? Give a reason.

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