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

What these 14 flashcards ask

Difference between a trail and a path?
Difference between a circuit and a cycle?
When does a connected graph have an Eulerian circuit?
When does a connected graph have an Eulerian trail but no circuit?
What is a Hamiltonian cycle?
How many edges does a tree with n vertices have?
State Kruskal's algorithm.
State Prim's algorithm.
How is Prim's matrix method carried out?
What does the Chinese postman problem find?
How do you solve Chinese postman with four odd vertices?
What does the nearest neighbour algorithm give for the TSP?
What does the deleted vertex algorithm give?
Why complete a table of least distances?

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

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

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).