Mathematics: Applications & Interpretation HL
Graph theory and networks — Topic 3 HL
- 1.
A simple graph has vertices with degrees 3, 2, 2, 3, 2. Use the handshaking lemma to find the number of edges in the graph.
[2 marks] - 2.
Marking analysis: A learner attempts the following task: “A simple graph has vertices with degrees 3, 2, 2, 3, 2. Use the handshaking lemma to find the number of edges in the graph.” Their response addresses only this point: “States the handshaking lemma: the sum of all vertex degrees equals twice the number of edges.” Evaluate the response against the complete 2-mark task. Identify what earns credit and state every additional requirement needed for full marks.
[2 marks] - 3.
Explain why no simple graph can have the degree sequence 3, 2, 2, 2.
[2 marks] · no calculator - 4.
Marking analysis: A learner attempts the following task: “Explain why no simple graph can have the degree sequence 3, 2, 2, 2.” Their response addresses only this point: “Calculates the sum of the proposed degrees: 3 + 2 + 2 + 2 = 9.” Evaluate the response against the complete 2-mark task. Identify what earns credit and state every additional requirement needed for full marks.
[2 marks] · no calculator - 5.
A graph has vertices A, B, C, D and edges AB, AC, BC, BD. Construct the adjacency matrix for this graph, and verify that the sum of each row equals the degree of the corresponding vertex.
[4 marks] - 6.
Marking analysis: A learner attempts the following task: “A graph has vertices A, B, C, D and edges AB, AC, BC, BD. Construct the adjacency matrix for this graph, and verify that the sum of each row equals the degree of the corresponding vertex.” Their response addresses only this point: “Constructs the 4×4 adjacency matrix with rows/columns ordered A, B, C, D: [[0,1,1,0],[1,0,1,1],[1,1,0,0],[0,1,0,0]].” Evaluate the response against the complete 4-mark task. Identify what earns credit and state every additional requirement needed for full marks.
[4 marks] - 7.
A network connecting six towns A, B, C, D, E, F has the following roads and distances (km): AB=4, AC=2, BC=1, BD=5, CD=8, CE=10, DE=2, DF=6, EF=3. Use Kruskal's algorithm to find a minimum spanning tree for this network, showing the order in which edges are added, and state its total weight.
[6 marks] - 8.
Marking analysis: A learner attempts the following task: “A network connecting six towns A, B, C, D, E, F has the following roads and distances (km): AB=4, AC=2, BC=1, BD=5, CD=8, CE=10, DE=2, DF=6, EF=3. Use Kruskal's algorithm to find a minimum spanning tree for this network, showing the order in which edges are added, and state its total weight.” Their response addresses only this point: “Sorts the edges by increasing weight: BC(1), AC(2), DE(2), EF(3), AB(4), BD(5), DF(6), CD(8), CE(10).” Evaluate the response against the complete 6-mark task. Identify what earns credit and state every additional requirement needed for full marks.
[6 marks] - 9.
Using the same network as the previous question, apply Prim's algorithm starting from vertex A to find a minimum spanning tree, showing the order in which vertices are added. Confirm that the total weight matches the result from Kruskal's algorithm.
[6 marks] - 10.
Marking analysis: A learner attempts the following task: “Using the same network as the previous question, apply Prim's algorithm starting from vertex A to find a minimum spanning tree, showing the order in which vertices are added. Confirm that the total weight matches the result from Kruskal's algorithm.” Their response addresses only this point: “Starts at A; the cheapest edge from the tree {A} is AC(2), so C is added.” Evaluate the response against the complete 6-mark task. Identify what earns credit and state every additional requirement needed for full marks.
[6 marks] - 11.
A network has vertices P, Q, R, S, T, U with weighted edges: PQ=7, PR=9, PU=14, QR=10, QS=15, RS=11, RU=2, ST=6, UT=9. Use Dijkstra's algorithm to find the shortest path from P to T, stating the path and its total length.
[7 marks] - 12.
Marking analysis: A learner attempts the following task: “A network has vertices P, Q, R, S, T, U with weighted edges: PQ=7, PR=9, PU=14, QR=10, QS=15, RS=11, RU=2, ST=6, UT=9. Use Dijkstra's algorithm to find the shortest path from P to T, stating the path and its total length.” Their response addresses only this point: “Assigns P a permanent label of 0 and considers its neighbours: Q gets a working value of 7, R gets 9, U gets 14.” Evaluate the response against the complete 7-mark task. Identify what earns credit and state every additional requirement needed for full marks.
[7 marks] - 13.
Using the same Dijkstra's algorithm table from the previous question, state the order in which the vertices P, Q, R, S, T, U received their permanent labels.
[2 marks] - 14.
Marking analysis: A learner attempts the following task: “Using the same Dijkstra's algorithm table from the previous question, state the order in which the vertices P, Q, R, S, T, U received their permanent labels.” Their response addresses only this point: “States the order of permanent labelling as P, Q, R, U, S, T.” Evaluate the response against the complete 2-mark task. Identify what earns credit and state every additional requirement needed for full marks.
[2 marks] - 15.
Five cities W, X, Y, Z, V have the following direct distances (km): WX=12, WY=10, WZ=19, WV=8, XY=3, XZ=7, XV=6, YZ=2, YV=20, ZV=4. Starting at W, use the nearest-neighbour algorithm to find an upper bound for the length of a travelling salesman tour that visits every city once and returns to W.
[5 marks] - 16.
Marking analysis: A learner attempts the following task: “Five cities W, X, Y, Z, V have the following direct distances (km): WX=12, WY=10, WZ=19, WV=8, XY=3, XZ=7, XV=6, YZ=2, YV=20, ZV=4. Starting at W, use the nearest-neighbour algorithm to find an upper bound for the length of a travelling salesman tour that visits every city once and returns to W.” Their response addresses only this point: “From W, the nearest unvisited city is V (8 km).” Evaluate the response against the complete 5-mark task. Identify what earns credit and state every additional requirement needed for full marks.
[5 marks] - 17.
Using the same five cities as the previous question, find a lower bound for the travelling salesman tour by deleting city W, finding the minimum spanning tree of the remaining four cities, and adding the two shortest edges connected to W.
[6 marks] - 18.
Marking analysis: A learner attempts the following task: “Using the same five cities as the previous question, find a lower bound for the travelling salesman tour by deleting city W, finding the minimum spanning tree of the remaining four cities, and adding the two shortest edges connected to W.” Their response addresses only this point: “Deletes W and finds the minimum spanning tree of X, Y, Z, V using Kruskal's or Prim's algorithm.” Evaluate the response against the complete 6-mark task. Identify what earns credit and state every additional requirement needed for full marks.
[6 marks] - 19.
A delivery network forms a graph where every edge must be traversed at least once, starting and ending at the depot. The edges and distances (km) are: AB=3, BC=4, CA=5, CD=6, where A is the depot. Exactly two vertices, C and D, have odd degree. Find the length of the shortest possible route that traverses every edge at least once and returns to A.
[5 marks] - 20.
Marking analysis: A learner attempts the following task: “A delivery network forms a graph where every edge must be traversed at least once, starting and ending at the depot. The edges and distances (km) are: AB=3, BC=4, CA=5, CD=6, where A is the depot. Exactly two vertices, C and D, have odd degree. Find the length of the shortest possible route that traverses every edge at least once and returns to A.” Their response addresses only this point: “Calculates the total weight of all edges: 3 + 4 + 5 + 6 = 18.” Evaluate the response against the complete 5-mark task. Identify what earns credit and state every additional requirement needed for full marks.
[5 marks] - 21.
For each of the following degree sequences, state whether the corresponding graph has an Euler circuit, an Euler trail (but not a circuit), or neither: (a) 4, 4, 2, 2 (all even). (b) 3, 3, 2, 2 (exactly two odd). (c) 3, 3, 3, 3 (four odd).
[3 marks] · no calculator - 22.
Marking analysis: A learner attempts the following task: “For each of the following degree sequences, state whether the corresponding graph has an Euler circuit, an Euler trail (but not a circuit), or neither: (a) 4, 4, 2, 2 (all even). (b) 3, 3, 2, 2 (exactly two odd). (c) 3, 3, 3, 3 (four odd).” Their response addresses only this point: “States that (a), with all vertices of even degree, has an Euler circuit.” Evaluate the response against the complete 3-mark task. Identify what earns credit and state every additional requirement needed for full marks.
[3 marks] · no calculator - 23.
Explain why a tree with n vertices always has exactly n − 1 edges, and state the number of edges in a tree with 6 vertices.
[3 marks] · no calculator - 24.
Marking analysis: A learner attempts the following task: “Explain why a tree with n vertices always has exactly n − 1 edges, and state the number of edges in a tree with 6 vertices.” Their response addresses only this point: “Explains that a tree is a connected graph with no cycles, and that connecting n vertices with the fewest possible edges while remaining connected requires exactly n − 1 edges.” Evaluate the response against the complete 3-mark task. Identify what earns credit and state every additional requirement needed for full marks.
[3 marks] · no calculator - 25.
A triangle graph has vertices A, B, C, each pair joined by an edge, with adjacency matrix M = [[0,1,1],[1,0,1],[1,1,0]]. Calculate M², and explain what the entries of M² represent.
[4 marks] - 26.
Marking analysis: A learner attempts the following task: “A triangle graph has vertices A, B, C, each pair joined by an edge, with adjacency matrix M = [[0,1,1],[1,0,1],[1,1,0]]. Calculate M², and explain what the entries of M² represent.” Their response addresses only this point: “Multiplies M by itself to obtain M² = [[2,1,1],[1,2,1],[1,1,2]].” Evaluate the response against the complete 4-mark task. Identify what earns credit and state every additional requirement needed for full marks.
[4 marks] - 27.
Define what is meant by a Hamiltonian cycle, and find one Hamiltonian cycle in the five-city network from an earlier question (W, X, Y, Z, V, all pairs connected), stating its total length.
[3 marks] - 28.
Marking analysis: A learner attempts the following task: “Define what is meant by a Hamiltonian cycle, and find one Hamiltonian cycle in the five-city network from an earlier question (W, X, Y, Z, V, all pairs connected), stating its total length.” Their response addresses only this point: “Defines a Hamiltonian cycle as a closed route that visits every vertex of a graph exactly once before returning to the starting vertex.” Evaluate the response against the complete 3-mark task. Identify what earns credit and state every additional requirement needed for full marks.
[3 marks] - 29.
Explain the key difference between a tree and a general connected graph, in terms of the number of edges relative to the number of vertices, and in terms of cycles.
[2 marks] · no calculator - 30.
Marking analysis: A learner attempts the following task: “Explain the key difference between a tree and a general connected graph, in terms of the number of edges relative to the number of vertices, and in terms of cycles.” Their response addresses only this point: “Explains that a tree is a connected graph with exactly n − 1 edges and no cycles, while a general connected graph may have n − 1 or more edges and can contain one or more cycles.” Evaluate the response against the complete 2-mark task. Identify what earns credit and state every additional requirement needed for full marks.
[2 marks] · no calculator - 31.
Five locations A, B, C, D, E form a square ABCD of side 1 km (with diagonals AC = BD ≈ 1.41 km), plus a fifth location E that is 6.02 km from A and D, and 5.02 km from B and C. Starting at A, the nearest-neighbour algorithm gives the tour A→B→C→D→E→A with length 15.04 km, but the optimal tour A→B→E→C→D→A has length 13.04 km. Explain why the nearest-neighbour algorithm failed to find the optimal tour in this case.
[3 marks] · no calculator - 32.
Marking analysis: A learner attempts the following task: “Five locations A, B, C, D, E form a square ABCD of side 1 km (with diagonals AC = BD ≈ 1.41 km), plus a fifth location E that is 6.02 km from A and D, and 5.02 km from B and C. Starting at A, the nearest-neighbour algorithm gives the tour A→B→C→D→E→A with length 15.04 km, but the optimal tour A→B→E→C→D→A has length 13.04 km. Explain why the nearest-neighbour algorithm failed to find the optimal tour in this case.” Their response addresses only this point: “Explains that the nearest-neighbour algorithm makes the locally optimal choice at each step without considering the overall structure of the remaining route.” Evaluate the response against the complete 3-mark task. Identify what earns credit and state every additional requirement needed for full marks.
[3 marks] · no calculator