DP Mathematics: Applications and Interpretation Questionbank

AHL 3.14—Graph theory
Description
[N/A]Directly related questions
-
20N.3.AHL.TZ0.Hdm_5a:
Find the maximum possible value of ee.
-
20N.3.AHL.TZ0.Hdm_5b:
Find an expression for e'e' in terms of ee.
-
20N.3.AHL.TZ0.Hdm_5c:
Given that the complement of GG is also planar and connected, find the possible values of ee.
-
20N.3.AHL.TZ0.Hdm_5d:
HH is a simple graph with vv vertices and ee edges.
Given that both HH and its complement are planar and connected, find the maximum possible value of vv.
-
21N.3.AHL.TZ0.1b.i:
Use Prim’s algorithm, starting at vertex BB, to find the weight of the minimum spanning tree of the remaining graph. You should indicate clearly the order in which the algorithm selects each edge.
-
21N.3.AHL.TZ0.1b.ii:
Hence, for the case where x<9x<9, find a lower bound for Daniel’s travel time, in terms of xx.
-
21N.3.AHL.TZ0.1a:
Write down a Hamiltonian cycle in WW.
-
21N.3.AHL.TZ0.1c.i:
pp.
-
21N.3.AHL.TZ0.1f:
The tourist office in the city has received complaints about the lack of cleanliness of some routes between the attractions. Corinne, the office manager, decides to inspect all the routes between all the attractions, starting and finishing at HH. The sum of the weights of all the edges in graph WW is (92+x)(92+x).
Corinne inspects all the routes as quickly as possible and takes 22 hours.
Find the value of xx during Corinne’s inspection.
-
21N.3.AHL.TZ0.1c.ii:
qq.
-
21N.3.AHL.TZ0.1e.i:
Find the least value of xx for which the edge AFAF will definitely not be used by Daniel.
-
21N.3.AHL.TZ0.1c.iii:
rr.
-
21N.3.AHL.TZ0.1d.i:
Use the nearest neighbour algorithm to find two possible cycles.
-
21N.3.AHL.TZ0.1d.ii:
Find the best upper bound for Daniel’s travel time.
-
21N.3.AHL.TZ0.1e.ii:
Hence state the value of the upper bound for Daniel’s travel time for the value of xx found in part (e)(i).
-
22M.1.AHL.TZ1.13a:
Write down an expression for the position vector r of the ship, t hours after 1:00 pm.
-
22M.1.AHL.TZ1.13b:
Find the time at which the bearing of the ship from the harbour is 045˚.
-
22M.3.AHL.TZ1.2f.ii:
Write down the number of days it takes for the pollution to reach the last town.
-
22M.3.AHL.TZ1.2f.i:
Find which town is last to be polluted. Justify your answer.
-
22M.3.AHL.TZ2.2d.i:
By using Kruskal’s algorithm, find the minimum spanning tree for S, showing clearly the order in which edges are added.
-
22M.3.AHL.TZ2.2d.ii:
Hence find the minimum installation cost for the cables that would allow all the buildings to be part of the computer network.
-
22M.3.AHL.TZ2.2e:
State why a path that forms a Hamiltonian cycle does not always form an Eulerian circuit.
-
19N.3.AHL.TZ0.Hdm_4a.i:
Write down the minimum number of edges in G.
-
19N.3.AHL.TZ0.Hdm_4a.ii:
Find the maximum number of edges in G.
-
19N.3.AHL.TZ0.Hdm_4a.iii:
Find the maximum number of edges in G, given that G contains an Eulerian circuit.
-
19N.3.AHL.TZ0.Hdm_4b.i:
Explain why 2e=kf.
-
19N.3.AHL.TZ0.Hdm_4b.ii:
Find the value of f when v=9 and k=3.
-
19N.3.AHL.TZ0.Hdm_4b.iii:
Find the possible values of f when v=13.