3.16 Graph algorithms: trees, cycles and routesIB Maths: Applications and Interpretation HL: Mind map

Exam questions on 3.16 Graph algorithms: trees, cycles and routes

1. A connected graph has vertices $A, B, C, D, E$ and edges $AB, AC, BC, BD, CD, CE, DE$.
   Write down an Eulerian trail for this graph.2 marks
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.
   Use Prim's algorithm, starting at $A$, to find the order in which the edges are added to the tree.2 marks
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.
   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