3.16 Graph algorithms: trees, cycles and routesIB Maths: Applications and Interpretation HL: Subtopic test

1. 1
   A connected graph has vertices $A, B, C, D, E$ and edges $AB, 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]

   • A$A\to B\to D\to E\to C\to A$
   • B$A\to B\to C\to D\to E\to A$
   • C$A\to C\to B\to D\to E\to A$
   • D$A\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, F$ with cable. The possible links and their costs, in thousands of AED, are: $AB$ 12, $AC$ 9, $AD$ 13, $BC$ 7, $BD$ 15, $CD$ 10, $CE$ 14, $DE$ 6, $DF$ 11, $EF$ 8.

   (a)

   Kruskal's algorithm is used to find a minimum spanning tree. Which edge is the first to be rejected?

   [1 mark]

   • A$AB$
   • B$DF$
   • C$AD$
   • D$CE$

   (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 $A$, 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, D$, starting and finishing at $A$. The road lengths, in hundreds of metres, are: $AB$ 9, $AC$ 4, $AD$ 6, $BC$ 3, $BD$ 8, $CD$ 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 $A$ 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, E$ once each and return to the start depot $A$. The table of least distances, in km, between depots gives: $AB$ 19, $AC$ 8, $AD$ 21, $AE$ 17, $BC$ 23, $BD$ 16, $BE$ 10, $CD$ 14, $CE$ 13, $DE$ 6.

   (a)

   Use the nearest neighbour algorithm, starting at $A$, 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 $E$, to find a lower bound. Hence write down an inequality for the length $L$ of the shortest route. Another student deletes $D$ and gets a lower bound of $51$ km; state, with a reason, which lower bound should be used.

   [6 marks]

   Total for question 4: 12 marks

End of questions