Download IITian Academy App for accessing Online Mock Tests and More..
Question
The table below shows the distances between towns A, B, C, D and E.
(i) Draw the graph, in its planar form, that is represented by the table.
(ii) Write down with reasons whether or not it is possible to find an Eulerian trail in this graph.
(iii) Solve the Chinese postman problem with reference to this graph if A is to be the starting and finishing point. Write down the walk and determine the length of the walk.
Show that a graph cannot have exactly one vertex of odd degree.
Answer/Explanation
Markscheme
(i)
A1A1A1
Note: Award A1 for the vertices, A1 for edges and A1 for planar form.
(ii) It is possible to find an Eulerian trail in this graph since exactly two of the vertices have odd degree R1
(iii) B and D are the odd vertices M1
\(BC + CD = 3 + 2 = 5{\text{ and }}BD = 9,\) A1
since 5 < 9 , BC and CD must be traversed twice R1
A possible walk by inspection is ACBDABCDCEA A1
This gives a total length of
2(2 + 3) + 8 + 9 + 5 + 7 + 10 + 6 = 55 for the walk A1
[9 marks]
The sum of all the vertex degrees is twice the number of edges, i.e. an even number.
Hence a graph cannot have exactly one vertex of odd degree. M1R1
[2 marks]
Examiners report
Drawing the graph usually presented no difficulty. Distinguishing between Eulerian and semi-Eulerian needs attention but this part was usually done successfully.
A simple, clear argument for part (c) was often hidden in mini-essays on graph theory.
Drawing the graph usually presented no difficulty. Distinguishing between Eulerian and semi-Eulerian needs attention but this part was usually done successfully.
A simple, clear argument for part (c) was often hidden in mini-essays on graph theory.
Question
In the graph given above, the numbers shown represent the distance along that edge.
Using Dijkstra’s algorithm, find the length of the shortest path from vertex S to vertex T . Write down this shortest path.
(i) Does this graph have an Eulerian circuit? Justify your answer.
(ii) Does this graph have an Eulerian trail? Justify your answer.
The graph above is now to be considered with the edges representing roads in a town and with the distances being the length of that road in kilometres. Huan is a postman and he has to travel along every road in the town to deliver letters to all the houses in that road. He has to start at the sorting office at S and also finish his route at S . Find the shortest total distance of such a route. Fully explain the reasoning behind your answer.
Answer/Explanation
Markscheme
from tabular method as shown above (or equivalent) M1A1A1
Note: Award the first A1 for obtaining 3 as the shortest distance to C.
Award the second A1 for obtaining the rest of the shortest distances.
shortest path has length 17 A1
backtracking as shown above (or equivalent) (M1)
shortest path is SABT A1
[6 marks]
(i) no, as S and T have odd degree A1R1
Note: Mentioning one vertex of odd degree is sufficient.
(ii) yes, as only S and T have odd degree A1R1
Note: In each case only award the A1 if the R1 has been given.
Accept an actual trail in (b)(ii).
[4 marks]
Huan has to travel along all the edges via an open Eulerian trail of length R1
4 + 3 + 5 + 2 + 1 + 3 + 5 + 4 + 7 + 8 + 5 + 6 + 7 + 6 + 6 + 8 + 9 = 94 A1
and then back to S from T along the shortest path found in (a) of length 17 R1
so shortest total distance is 94 + 17 = 111 A1
[4 marks]
Examiners report
This was quite well answered. Some candidates did not make their method clear and others showed no method at all. Some clearly had a correct method but did not make it clear what their final answers were. It is recommended that teachers look at the tabular method with its backtracking system as shown in the mark scheme as an efficient way of tackling this type of problem.
Fairly good knowledge shown here but not by all.
Some good answers but too much confusion with methods they partly remembered about the travelling salesman problem. Candidates should be aware of helpful connections between parts of a question.
Question
The following graph represents the cost in dollars of travelling by bus between 10 towns in a particular province.
Use Dijkstra’s algorithm to find the cheapest route between \(A\) and \(J\), and state its cost.
For the remainder of the question you may find the cheapest route between any two towns by inspection.
It is given that the total cost of travelling on all the roads without repeating any is \(\$ 139\).
A tourist decides to go over all the roads at least once, starting and finishing at town \(A\).
Find the lowest possible cost of his journey, stating clearly which roads need to be travelled more than once. You must fully justify your answer.
Answer/Explanation
Markscheme
M1A1A1A1
(M1 for an attempt at Dijkstra’s)
(A1 for value of \({\text{D}} = 17\))
(A1 for value of \({\text{H}} = 22\))
(A1 for value of \({\text{G}} = 22\))
route is \(ABDHJ\) (M1)A1
cost is \($27\) A1
Note: Accept other layouts.
[7 marks]
there are 4 odd vertices \(A\), \(D\), \(F\) and \(J\) A1
these can be joined up in 3 ways with the following extra costs
\(AD\) and \(FJ\)\(\;\;\;17 + 13 = 30\)
\(AF\) and \(DJ\)\(\;\;\;23 + 10 = 33\)
\(AJ\) and \(DF\)\(\;\;\;27 + 12 = 39\) M1A1A1
Note: Award M1 for an attempt to find different routes.
Award A1A1 for correct values for all three costs A1 for one correct.
need to repeat \(AB\), \(BD\), \(FG\) and \(GJ\) A1
total cost is \(139 + 30 = \$ 169\) A1
[6 marks]
Total [13 marks]
Examiners report
Many candidates had the correct route and the cost. Not all showed sufficient working with their Dijkstra’s algorithm. See the mark-scheme for the neat way of laying out the working, including the back-tracking method. This tabular working is efficient, avoids mistakes and saves time.
There was often confusion here between this problem and the travelling salesman. Good candidates started with the number of vertices of odd degree. Weaker candidates just tried to write the answer down without complete reasoning. All the 3 ways of joining the odd vertices had to be considered so that you knew you had the smallest. Sometimes a mark was lost by giving which routes (paths) had to be repeated rather than which roads (edges).
Question
The weights of the edges of a graph \(H\) are given in the following table.
(i) Draw the weighted graph \(H\).
(ii) Use Kruskal’s algorithm to find the minimum spanning tree of \(H\). Your solution should indicate the order in which the edges are added.
(iii) State the weight of the minimum spanning tree.
Consider the following weighted graph.
(i) Write down a solution to the Chinese postman problem for this graph.
(ii) Calculate the total weight of the solution.
(i) State the travelling salesman problem.
(ii) Explain why there is no solution to the travelling salesman problem for this graph.
Answer/Explanation
Markscheme
(i) 
A2
Note: Award A1 if one edge is missing. Award A1 if the edge weights are not labelled.
(ii) the edges are added in the order:
\(FG{\rm{ }}1\) M1A1
\(CE{\rm{ }}2\) A1
\(ED{\rm{ }}3\)
\(EG{\rm{ }}4\) A1
\(AC{\rm{ }}4\)
Note: \(EG\) and \(AC\) can be added in either order.
(Reject \(EF\))
(Reject \(CD\))
\(EB5\) OR \(AB5\) A
Notes: The minimum spanning tree does not have to be seen.
If only a tree is seen, the order by which edges are added must be clearly indicated.
(iii) \(19\) A1
[8 marks]
(i) eg, \(PQRSRTSTQP\) OR \(PQTSTRSRQP\) M1A1
Note: Award M1 if in either (i) or (ii), it is recognised that edge \(PQ\) is needed twice.
(ii) total weight \( = 34\) A1
[3 marks]
(i) to determine a cycle where each vertex is visited once only (Hamiltonian cycle) A1
of least total weight A1
(ii) EITHER
to reach \(P\), \(Q\) must be visited twice which contradicts the definition of the \(TSP\) R1
OR
the graph is not a complete graph and hence there is no solution to the \(TSP\) R1
[3 marks]
Total [14 marks]
Examiners report
Part (a) was generally very well answered. Most candidates were able to correctly sketch the graph of \(H\) and apply Kruskal’s algorithm to determine the minimum spanning tree of \(H\). A few candidates used Prim’s algorithm (which is no longer part of the syllabus).
Most candidates understood the Chinese Postman Problem in part (b) and knew to add the weight of \(PQ\) to the total weight of \(H\). Some candidates, however, did not specify a solution to the Chinese Postman Problem while other candidates missed the fact that a return to the initial vertex is required.
In part (c), many candidates had trouble succinctly stating the Travelling Salesman Problem. Many candidates used an ‘edge’ argument rather than simply stating that the Travelling Salesman Problem could not be solved because to reach vertex \(P\), vertex \(Q\) had to be visited twice.
Question
Mathilde delivers books to five libraries, A, B, C, D and E. She starts her deliveries at library D and travels to each of the other libraries once, before returning to library D. Mathilde wishes to keep her travelling distance to a minimum.
The weighted graph \(H\), representing the distances, measured in kilometres, between the five libraries, has the following table.
Draw the weighted graph \(H\).
Starting at library D use the nearest-neighbour algorithm, to find an upper bound for Mathilde’s minimum travelling distance. Indicate clearly the order in which the edges are selected.
By first removing library C, use the deleted vertex algorithm, to find a lower bound for Mathilde’s minimum travelling distance.
Answer/Explanation
Markscheme
complete graph on 5 vertices A1
weights correctly marked on graph A1
[2 marks]
clear indication that the nearest-neighbour algorithm has been applied M1
DA (or 16) A1
AB (or 18) then BC (or 15) A1
CE (or 17) then ED (or 19) A1
\({\text{UB}} = 85\) A1
[5 marks]
an attempt to find the minimum spanning tree (M1)
DA (16) then BE (17) then AB (18) (total 51) A1
reconnect C with the two edges of least weight, namely CB (15) and CE (17) M1
\({\text{LB}} = 83\) A1
[4 marks]
Examiners report
[N/A]
[N/A]
[N/A]
Question
Consider the following weighted graph G.
State what feature of G ensures that G has an Eulerian trail.
State what feature of G ensures that G does not have an Eulerian circuit.
Write down an Eulerian trail in G.
State the Chinese postman problem.
Starting and finishing at B, find a solution to the Chinese postman problem for G.
Calculate the total weight of the solution.
Answer/Explanation
Markscheme
G has an Eulerian trail because it has (exactly) two vertices (B and F) of odd degree R1
[1 mark]
G does not have an Eulerian circuit because not all vertices are of even degree R1
[1 mark]
for example BAEBCEFCDF A1A1
Note: Award A1 for start/finish at B/F, A1 for the middle vertices.
[2 marks]
to determine the shortest route (walk) around a weighted graph A1
using each edge (at least once, returning to the starting vertex) A1
Note: Correct terminology must be seen. Do not accept trail, path, cycle or circuit.
[2 marks]
we require the Eulerian trail in (b), (weight = 65) (M1)
and the minimum walk FEB (15) A1
for example BAEBCEFCDFEB A1
Note: Accept EB added to the end or FE added to the start of their answer in (b) in particular for follow through.
[3 marks]
total weight is (65 + 15=)80 A1
[1 mark]
Examiners report
[N/A]
[N/A]
[N/A]
[N/A]
[N/A]
[N/A]