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.
An undirected network has roads AB=4, AC=2, BC=1, BD=5, CD=8, CE=10, DE=2, DF=6 and EF=3 km. Apply Prim's algorithm starting at A, showing the order in which vertices are added. State the selected edges and total weight, and compare with the Kruskal minimum-spanning-tree weight of 13 km.
[6 marks] - 10.
Marking analysis: A learner attempts the following task: “An undirected network has roads AB=4, AC=2, BC=1, BD=5, CD=8, CE=10, DE=2, DF=6 and EF=3 km. Apply Prim's algorithm starting at A, showing the order in which vertices are added. State the selected edges and total weight, and compare with the Kruskal minimum-spanning-tree weight of 13 km.” 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.
For the undirected network PQ=7, PR=9, PU=14, QR=10, QS=15, RS=11, RU=2, ST=6 and UT=9, apply Dijkstra's algorithm from P until every vertex has a permanent label. State the labelling order, allowing either order when tentative distances tie, and identify the tied final distances.
[2 marks] - 14.
Marking analysis: A learner attempts the following task: “For the undirected network PQ=7, PR=9, PU=14, QR=10, QS=15, RS=11, RU=2, ST=6 and UT=9, apply Dijkstra's algorithm from P until every vertex has a permanent label. State the labelling order, allowing either order when tentative distances tie, and identify the tied final distances.” Their response addresses only this point: “States the order of permanent labelling as P, Q, R, U, then S and T (the two vertices tie at 20, so either order of S and T is acceptable).” 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.
Five cities have symmetric direct distances (km): WX=12, WY=10, WZ=19, WV=8, XY=3, XZ=7, XV=6, YZ=2, YV=20, ZV=4. Find a lower bound for a travelling-salesman tour by deleting W, finding a minimum spanning tree on the remaining cities and adding the two shortest edges incident to W. Compare it with the supplied nearest-neighbour upper bound of 29 km.
[6 marks] - 18.
Marking analysis: A learner attempts the following task: “Five cities have symmetric direct distances (km): WX=12, WY=10, WZ=19, WV=8, XY=3, XZ=7, XV=6, YZ=2, YV=20, ZV=4. Find a lower bound for a travelling-salesman tour by deleting W, finding a minimum spanning tree on the remaining cities and adding the two shortest edges incident to W. Compare it with the supplied nearest-neighbour upper bound of 29 km.” 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 connected undirected graphs, classify whether it has an Euler circuit, an Euler trail but not a circuit, or neither, using its vertex degrees: (a) 4, 4, 2, 2, 2. (b) 3, 3, 2, 2. (c) 3, 3, 3, 3.
[3 marks] · no calculator - 22.
Marking analysis: A learner attempts the following task: “For each of the following connected undirected graphs, classify whether it has an Euler circuit, an Euler trail but not a circuit, or neither, using its vertex degrees: (a) 4, 4, 2, 2, 2. (b) 3, 3, 2, 2. (c) 3, 3, 3, 3.” 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 a Hamiltonian cycle. Find one in the complete undirected five-city network with distances (km) WX=12, WY=10, WZ=19, WV=8, XY=3, XZ=7, XV=6, YZ=2, YV=20, ZV=4, and state its total length.
[3 marks] - 28.
Marking analysis: A learner attempts the following task: “Define a Hamiltonian cycle. Find one in the complete undirected five-city network with distances (km) WX=12, WY=10, WZ=19, WV=8, XY=3, XZ=7, XV=6, YZ=2, YV=20, ZV=4, and state 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.
A complete weighted graph models travel between locations A, B, C, D and E. Its symmetric weights (km) are AB=BC=CD=DA=1, AC=BD=1.41, AE=DE=6.02 and BE=CE=5.02. Starting at A and breaking the initial tie by choosing B, nearest neighbour gives A-B-C-D-E-A with length 15.04 km. An optimal tour A-B-E-C-D-A has length 13.04 km. Explain why nearest neighbour misses an optimum in this case.
[3 marks] · no calculator - 32.
Marking analysis: A learner attempts the following task: “A complete weighted graph models travel between locations A, B, C, D and E. Its symmetric weights (km) are AB=BC=CD=DA=1, AC=BD=1.41, AE=DE=6.02 and BE=CE=5.02. Starting at A and breaking the initial tie by choosing B, nearest neighbour gives A-B-C-D-E-A with length 15.04 km. An optimal tour A-B-E-C-D-A has length 13.04 km. Explain why nearest neighbour misses an optimum 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