DP Mathematics HL Questionbank

• Syllabus

10.9

Sub sections and their related questions

Graph algorithms: Kruskal’s; Dijkstra’s.

• 12N.3dm.hl.TZ0.1a: Using Dijkstra’s algorithm, find the length of the shortest path from vertex S to vertex T ....
• 08M.3dm.hl.TZ1.5a: The weighted graph H is shown below.   Use Kruskal’s Algorithm, indicating the order in which...
• 08N.3dm.hl.TZ0.2a: Use Kruskal’s algorithm to find the minimum spanning tree for the following weighted graph and...
• 08N.3dm.hl.TZ0.2b: Use Dijkstra’s algorithm to find the shortest path from A to D in the following weighted graph...
• 09M.3dm.hl.TZ0.1: Sameer is trying to design a road system to connect six towns, A, B, C, D, E and F. The possible...
• 09N.3dm.hl.TZ0.2a + c: (a)     (i)     What feature of the graph enables you to deduce that G contains an Eulerian...
• SPNone.3dm.hl.TZ0.4b: (i)     Use Kruskal’s algorithm to find and draw a minimum spanning tree for the subgraph...
• 10M.3dm.hl.TZ0.2: A graph G with vertices A, B, C, D, E has the following cost adjacency...
• 10N.3dm.hl.TZ0.3: Consider the following weighted graph.     (a)     (i)     Use Kruskal’s algorithm to find...
• 13M.3dm.hl.TZ0.2b: (i)     Use Dijkstra’s algorithm to find the path of minimum total weight joining A to D. (ii)  ...
• 13N.3dm.hl.TZ0.1: The following diagram shows a weighted graph.   (a)     Use Kruskal’s algorithm to find a...
• 14N.3dm.hl.TZ0.3a: Use Dijkstra’s algorithm to find the cheapest route between \(A\) and \(J\), and state its cost.
• 15M.3dm.hl.TZ0.1a: The weights of the edges of a graph \(H\) are given in the following table. (i)     Draw the...
• 15N.3dm.hl.TZ0.1a: The distances by road, in kilometres, between towns in Switzerland are shown in the following...
• 16M.3dm.hl.TZ0.2a: Starting at A, use the nearest neighbour algorithm to find an upper bound for the travelling...
• 16M.3dm.hl.TZ0.2b: By first removing A , use the deleted vertex algorithm to find a lower bound for the travelling...
• 16N.3dm.hl.TZ0.4a: (i)     Draw the graph \({\kappa _4}\) including the weights of all the edges. (ii)     Use the...
• 16N.3dm.hl.TZ0.4b: Consider the graph \({\kappa _5}\). Use the deleted vertex algorithm, with \({{\text{A}}_5}\) as...
• 16N.3dm.hl.TZ0.4c: (i)     Use the nearest-neighbour algorithm, starting at vertex \({{\text{A}}_1}\), to find a...
• 16N.3dm.hl.TZ0.4d: By splitting the weight of the edge \({{\text{A}}_i}{{\text{A}}_j}\) into two parts or otherwise,...