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

jmaths

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

Name Date

Exam practice: the whole unit Problem set B

Set out every algorithm. Marks are shown for the long questions.

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. The graph shows the ferry routes between six islands. Is it possible to start on one island, finish on a different island, and sail along every route exactly once? Give a reason.

    1045524744ABCDEF

  2. The graph shows the roads between seven towns, with lengths in km. Find the shortest distance between:

    497475211531012ABCDEFG
    1. (a) A and F
    2. (b) A and G
    3. (c) C and G
    4. (d) C and F

  3. The table shows the shortest distances, in minutes, between six places. Use the nearest neighbour algorithm, starting at E, to find an upper bound for the travelling salesman problem.

    ABCDEFA-71391817B7-1531310C1315-18911D9318-1111E1813911-10F1710111110-

  4. Use the graph. Sketch a minimum spanning tree for the subgraph with vertices A, B, C, E, F, G, then write down its total weight.

    497475211531012ABCDEFG
    1. (a) Write down the edges of the minimum spanning tree of the subgraph without D.
    2. (b) Write down its total weight.

In context

  1. The vertices in the graph represent seven depots of a delivery company. The edges represent the roads between them. The weight on each edge is the driving time in minutes. It is found that the optimum solution starting at G is G-F-C-A-B-D-E-G. [17 marks]

    10741110511132108ABCDEFG
    1. (a) Determine whether it is possible to complete a journey that starts and finishes at different towns and uses each road exactly once. Give a reason for your answer. [2 marks]
    2. (b) The table of shortest distances between the towns is built from the graph. Find the shortest distance between (i) C and E; (ii) B and F; (iii) E and F; (iv) D and G. [2 marks]
    3. (c) Use the nearest neighbour algorithm on the table of shortest distances, starting at G, to find an upper bound for the travelling salesman problem. [3 marks]
    4. (d) Sketch a minimum spanning tree for the subgraph with vertices A, B, C, D, E, F, and write down its total weight. [4 marks]
    5. (e) Hence find a lower bound for the travelling salesman problem. [2 marks]
    6. (f) Explain one way in which a better lower bound could be found. [1 mark]
    7. (g) Given that the length of each road shown on the graph is given to the nearest minute, find the lower bound for the total distance in the optimal solution. [3 marks]

Stretch

  1. The table shows the shortest distances, in minutes, between six places. A route is needed that visits every place and returns to the start.

    ABCDEFA-518171415B5-17161211C1817-101319D171610-1014E14121310-14F1511191414-
    1. (a) Use the nearest neighbour algorithm, starting at F, to find an upper bound.
    2. (b) Delete A and find a lower bound.
    3. (c) Explain how a better lower bound could be found. Then delete D and state the better of the two lower bounds.

jmaths.xyz · AI HL · AHL 1.13 Exam practice: the whole unit