Topic 3.16: Route algorithms (HL only) Questions

Dijkstra's algorithm is best described as finding:

In Kruskal's algorithm, an edge is rejected when it:

If every vertex of a connected graph has even degree, the Chinese postman route length equals:

Write down whether an Eulerian trail exists, and where it must start.

Write down the number of edges in any spanning tree of the graph.

The nearest-neighbour algorithm for the TSP gives:

A spanning tree on 10 vertices has how many edges?

A TSP problem gives an upper bound of 64 and a lower bound of 64. The optimal tour length is:

Four cities P, Q, R, S have distances (km): PQ = 8, PR = 5, PS = 9, QR = 6, QS = 7, RS = 4. Use the nearest-neighbour algorithm starting at P to find an upper bound for the travelling-salesman tour.

Find the length of the shortest closed route that covers every road.

A water authority can lay pipes between 4 pumping stations P, Q, R, S. Lengths (km): PQ = 3, PR = 7, QR = 2, QS = 6, RS = 4. Use Kruskal's algorithm to find the minimum spanning tree and its total length.

A fibre provider can link 5 hubs (1, 2, 3, 4, 5). Costs (£000): 12 = 5, 13 = 8, 23 = 3, 24 = 6, 34 = 4, 35 = 9, 45 = 2. Use Kruskal's algorithm to find the cheapest network connecting all hubs, and state its cost.

For the network PQ = 3, PR = 7, QR = 2, QS = 6, RS = 4, use Prim's algorithm starting at P. List the edges in the order they are added and give the total weight.

In Dijkstra's algorithm, the next vertex to be made permanent is the one with the:

A road network has lengths (m): AB = 200, AC = 300, BC = 150, BD = 250, CD = 100, CE = 350, DE = 200. The total of all the roads is 1550 m. A snow-plough must clear every road and return to the depot. Find the length of the shortest closed route.

In the deleted-vertex lower bound, after removing a vertex you find the MST of the rest and then add:

A connected graph has odd-degree vertices at P, Q, R, S. How many distinct ways can they be paired for route inspection?

Find the total weight of the minimum spanning tree.

Prim's algorithm differs from Kruskal's mainly because it:

Explain the difference between the Chinese postman (route inspection) problem and the travelling salesman problem, and state what each algorithm guarantees.