IB Maths AI HL Graph theory worksheet with answers
A free IB Maths AI HL worksheet on Graph theory: 12 questions, 50 marks, short and extended questions in the IB style. The answers and full worked solutions are on the last page.
In the print window, choose Save as PDF to download it.
Unless otherwise stated in the question, all numerical answers should be given exactly or correct to three significant figures.
1
Does the connected graph with this adjacency matrix have an Eulerian circuit, an Eulerian trail (but no circuit), or neither? M=ABCDEFA001001B001101C110010D010011E001101F110110
Answer[1]
2
(a)Find the number of walks of length 2 from C to E in the graph with this adjacency matrix: M=ABCDEA01011B10111C01001D11001E11110
Answer (a)[1]
(b)Does the graph shown have a Hamiltonian cycle, a Hamiltonian path but no Hamiltonian cycle, or neither?
Answer (b)[1]
3
(a)Find the number of walks of length 3 from F to B in the graph with this adjacency matrix: M=ABCDEFA010110B100111C000111D111010E111101F011010
Answer (a)[1]
(b)Does the graph with this adjacency matrix have a Hamiltonian cycle, a Hamiltonian path but no Hamiltonian cycle, or neither? M=ABCDEA01110B10000C10001D10000E00100
Answer (b)[1]
4
(a)Find the number of walks of length 3 from B to D in the graph with this adjacency matrix: M=ABCDA0111B1001C1001D1110
Answer (a)[1]
(b)The table shows the least distances, in km, between 5 towns: ABCDEA−9111211B9−898C118−1011D12910−12E1181112− Use the nearest neighbour algorithm, starting at E, to find an upper bound for the travelling salesman problem.
Answer (b)[2]
5
(a)The table shows the least distances, in km, between 6 towns: ABCDEFA−121181113B12−121188C1112−14815D81114−88E11888−13F13815813− By deleting vertex B, find a lower bound for the travelling salesman problem.
Answer (a)[2]
(b)Find the total weight of the shortest route that travels along every edge at least once and returns to its start (the Chinese postman problem), for the graph with these edge weights ("−" means no edge): ABCDEA−137913B13−5314C75−3−D933−11E1314−11−
Answer (b)[2]
6
(a)Find the total weight of the shortest route that travels along every edge of the weighted graph shown at least once and returns to its start (the Chinese postman problem).
Answer (a)[2]
(b)The table shows the least distances, in km, between 6 towns: ABCDEFA−101281312B10−8111014C128−15108D81115−1215E13101012−15F121481515− Use the nearest neighbour algorithm, starting at D, to find an upper bound for the travelling salesman problem.
Answer (b)[2]
7
(a)Find the number of edges of the simple graph G with this adjacency matrix: M=ABCDA0100B1011C0101D0110
Answer (a)[2]
(b)The table shows the least distances, in km, between 5 towns: ABCDEA−14131512B14−12812C1312−98D1589−9E121289− By deleting vertex E, find a lower bound for the travelling salesman problem.
Answer (b)[2]
8
(a)The table shows the least distances, in km, between 6 towns: ABCDEFA−151514108B15−9101313C159−131112D141013−1211E10131112−11F813121111− Use the nearest neighbour algorithm, starting at F, to find an upper bound for the travelling salesman problem.
Answer (a)[2]
(b)Find the total weight of the shortest route that travels along every edge of the weighted graph shown at least once and returns to its start (the Chinese postman problem).
Answer (b)[2]
9
(a)The table shows the least distances, in km, between 5 towns: ABCDEA−1581510B15−91013C89−1510D151015−13E10131013− Use the nearest neighbour algorithm, starting at B, to find an upper bound for the travelling salesman problem.
Answer (a)[2]
(b)Use Kruskal's algorithm to find the total weight of a minimum spanning tree of the weighted graph shown.
Answer (b)[2]
10
The table shows the least distances, in km, between 6 towns: ABCDEFA−1310121412B13−1110912C1011−10129D121010−118E1491211−14F12129814− Use the nearest neighbour algorithm, starting at B, to find an upper bound for the travelling salesman problem.
Answer[2]
11
(a)Use Kruskal's algorithm to find the total weight of a minimum spanning tree of the graph with these edge weights ("−" means no edge): ABCDEFA−948153B9−−5118C4−−−711D85−−114E1511711−−F38114−−
Answer (a)[2]
(b)The table shows the least distances, in km, between 6 towns: ABCDEFA−121512815B12−1081110C1510−14148D12814−1313E8111413−8F15108138− Use the nearest neighbour algorithm, starting at B, to find an upper bound for the travelling salesman problem.
Answer (b)[2]
(c)The table shows the least distances, in km, between 5 towns: ABCDEA−138109B13−14139C814−1210D101312−9E99109− By deleting vertex C, find a lower bound for the travelling salesman problem.
Answer (c)[2]
(d)Use Kruskal's algorithm to find the total weight of a minimum spanning tree of the weighted graph shown.
Answer (d)[2]
(e)Use Kruskal's algorithm to find the total weight of a minimum spanning tree of the graph with these edge weights ("−" means no edge): ABCDEA−212−−B2−224C122−133D−213−10E−4310−
Answer (e)[2]
12
(a)Does the graph shown have a Hamiltonian cycle, a Hamiltonian path but no Hamiltonian cycle, or neither?
Answer (a)[1]
(b)Does the connected graph with this adjacency matrix have an Eulerian circuit, an Eulerian trail (but no circuit), or neither? M=ABCDEA01111B10011C10001D11000E11100
Answer (b)[1]
(c)Use Kruskal's algorithm to find the total weight of a minimum spanning tree of the graph with these edge weights ("−" means no edge): ABCDEA−7462B7−12155C412−−13D615−−9E25139−
Answer (c)[2]
(d)The table shows the least distances, in km, between 5 towns: ABCDEA−8141410B8−14915C1414−118D14911−12E1015812− By deleting vertex D, find a lower bound for the travelling salesman problem.
Answer (d)[2]
(e)The table shows the least distances, in km, between 5 towns: ABCDEA−1113138B11−151415C1315−910D13149−10E8151010− Use the nearest neighbour algorithm, starting at E, to find an upper bound for the travelling salesman problem.
Answer (e)[2]
(f)The table shows the least distances, in km, between 5 towns: ABCDEA−1214811B12−15910C1415−1411D8914−11E11101111− Use the nearest neighbour algorithm, starting at C, to find an upper bound for the travelling salesman problem.
Answer (f)[2]
END OF PAPER
Answers and worked solutions
Question 1
Answer: neither[1]
Degrees: A 2, B 3, C 3, D 3, E 3, F 4Odd vertices: 4
Question 2
(a)Answer: =1[1]
Work out M2 (on a calculator)=1
(b)Answer: cycle[1]
Degrees: A 3, B 4, C 3, D 4, E 4A cycle through every vertex: A → B → C → D → E → A
Question 3
(a)Answer: =10[1]
Work out M3 (on a calculator)=10
(b)Answer: neither[1]
Degrees: A 3, B 1, C 2, D 1, E 1B, D, E have degree 1: each must be an end of a path, and a path has only two ends
Question 4
(a)Answer: =5[1]
Work out M3 (on a calculator)=5
(b)Answer: =49 km[2]
Route: E → B (8) → C (8) → D (10) → A (12) → E (11)8+8+10+12+11=49 km
Question 5
(a)Answer: =48 km[2]
Edges: AD (8), CE (8), DE (8), DF (8)Weight=32BE (8), BF (8)32+8+8=48 km
(b)Answer: =92[2]
Odd vertices: C and E13+7+9+13+5+3+14+3+11=78=1478+14=92
Question 6
(a)Answer: =69[2]
Odd vertices: A and C4+15+4+8+10+5+14=60=960+9=69
(b)Answer: =61 km[2]
Route: D → A (8) → B (10) → C (8) → F (8) → E (15) → D (12)8+10+8+8+15+12=61 km
Question 7
(a)Answer: =4[2]
Degrees: A 1, B 3, C 2, D 221+3+2+2=4
(b)Answer: =47 km[2]
Edges: BD (8), CD (9), AC (13)Weight=30EC (8), ED (9)30+8+9=47 km
Question 8
(a)Answer: =59 km[2]
Route: F → A (8) → E (10) → C (11) → B (9) → D (10) → F (11)8+10+11+9+10+11=59 km
(b)Answer: =61[2]
Odd vertices: A and C10+4+7+3+7+12+9+5=57=457+4=61
Question 9
(a)Answer: =50 km[2]
Route: B → C (9) → A (8) → E (10) → D (13) → B (10)9+8+10+13+10=50 km
(b)Answer: =18[2]
Edges chosen: AD (2), AB (3), BC (3), AE (5), CF (5)2+3+3+5+5=18
Question 10
Answer: =60 km[2]
Route: B → E (9) → D (11) → F (8) → C (9) → A (10) → B (13)9+11+8+9+10+13=60 km
Question 11
(a)Answer: =23[2]
Edges chosen: AF (3), AC (4), DF (4), BD (5), CE (7)3+4+4+5+7=23
(b)Answer: =54 km[2]
Route: B → D (8) → A (12) → E (8) → F (8) → C (8) → B (10)8+12+8+8+8+10=54 km
(c)Answer: =45 km[2]
Edges: AE (9), BE (9), DE (9)Weight=27CA (8), CE (10)27+8+10=45 km
(d)Answer: =19[2]
Edges chosen: AC (3), DE (3), AB (4), BF (4), CD (5)3+3+4+4+5=19
(e)Answer: =9[2]
Edges chosen: AB (2), BC (2), BD (2), CE (3)2+2+2+3=9
Question 12
(a)Answer: path[1]
Degrees: A 2, B 2, C 2, D 1, E 3D has degree 1, so it can't be on a cycle. A path through every vertex: A → B → E → C → D
(b)Answer: trail[1]
Degrees: A 4, B 3, C 2, D 2, E 3Odd vertices: 2
(c)Answer: =17[2]
Edges chosen: AE (2), AC (4), BE (5), AD (6)2+4+5+6=17
(d)Answer: =46 km[2]
Edges: AB (8), CE (8), AE (10)Weight=26DB (9), DC (11)26+9+11=46 km
(e)Answer: =52 km[2]
Route: E → A (8) → B (11) → D (14) → C (9) → E (10)8+11+14+9+10=52 km
(f)Answer: =52 km[2]
Route: C → E (11) → B (10) → D (9) → A (8) → C (14)11+10+9+8+14=52 km