3.16 Graph algorithms: trees, cycles and routes

3.16 Graph algorithms: trees, cycles and routes Test

IB Maths: Applications and Interpretation HL: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

IB Maths: Applications and Interpretation HL

3.16 Graph algorithms: trees, cycles and routes

Total 27 marks

Name

Class

Date

  1. 1
    A connected graph has vertices A,B,C,D,EA, B, C, D, E and edges AB,AC,BC,BD,CD,CE,DEAB, AC, BC, BD, CD, CE, DE.
    (a)
    Which statement about this graph is correct?
    [1 mark]
    • AIt has an Eulerian circuit because every vertex has even degree
    • BIt has an Eulerian circuit because it is connected
    • CIt has an Eulerian trail but no Eulerian circuit
    • DIt has no Eulerian trail because it contains a cycle
    (b)
    Which of the following is a Hamiltonian cycle of this graph?
    [1 mark]
    • AA→B→D→E→C→AA\to B\to D\to E\to C\to A
    • BA→B→C→D→E→AA\to B\to C\to D\to E\to A
    • CA→C→B→D→E→AA\to C\to B\to D\to E\to A
    • DA→B→D→C→E→AA\to B\to D\to C\to E\to A
    (c)
    Write down an Eulerian trail for this graph.
    [2 marks]

    Total for question 1: 4 marks

  2. 2
    A company must connect six sites A,B,C,D,E,FA, B, C, D, E, F with cable. The possible links and their costs, in thousands of AED, are: ABAB 12, ACAC 9, ADAD 13, BCBC 7, BDBD 15, CDCD 10, CECE 14, DEDE 6, DFDF 11, EFEF 8.
    (a)
    Kruskal's algorithm is used to find a minimum spanning tree. Which edge is the first to be rejected?
    [1 mark]
    • AABAB
    • BDFDF
    • CADAD
    • DCECE
    (b)
    Find the total cost of the cheapest network that connects all six sites.
    [1 mark]
    • A43 thousand AED
    • B51 thousand AED
    • C40 thousand AED
    • D30 thousand AED
    (c)
    Use Prim's algorithm, starting at AA, to find the order in which the edges are added to the tree.
    [2 marks]

    Total for question 2: 4 marks

  3. 3
    A postal worker must walk along every road of an estate with four junctions A,B,C,DA, B, C, D, starting and finishing at AA. The road lengths, in hundreds of metres, are: ABAB 9, ACAC 4, ADAD 6, BCBC 3, BDBD 8, CDCD 5.
    (a)
    By considering the degree of each junction, explain why some roads must be walked more than once, and find, for each pairing of the odd junctions, the least total distance that must be repeated.
    [3 marks]
    (b)
    Hence find the length of the shortest route that starts and finishes at AA and walks along every road at least once. State which roads are repeated.
    [4 marks]

    Total for question 3: 7 marks

  4. 4
    A courier must visit five depots A,B,C,D,EA, B, C, D, E once each and return to the start depot AA. The table of least distances, in km, between depots gives: ABAB 19, ACAC 8, ADAD 21, AEAE 17, BCBC 23, BDBD 16, BEBE 10, CDCD 14, CECE 13, DEDE 6.
    (a)
    Use the nearest neighbour algorithm, starting at AA, to find an upper bound for the length of the shortest route. Give the route, and explain why the answer is an upper bound.
    [6 marks]
    (b)
    Use the deleted vertex algorithm, deleting EE, to find a lower bound. Hence write down an inequality for the length LL of the shortest route. Another student deletes DD and gets a lower bound of 5151 km; state, with a reason, which lower bound should be used.
    [6 marks]

    Total for question 4: 12 marks

End of questions

Subtopic tests