Download IITian Academy App for accessing Online Mock Tests and More..
Question
The graph G has the following cost adjacency table.
\[\begin{array}{*{20}{c|ccccc}}
{}&{\text{A}}&{\text{B}}&{\text{C}}&{\text{D}}&{\text{E}} \\
\hline
{\text{A}}& {\text{ – }}&9&{\text{ – }}&8&4 \\
{\text{B}}& 9&{\text{ – }}&7&{\text{ – }}&2 \\
{\text{C}}& {\text{ – }}&7&{\text{ – }}&7&3 \\
{\text{D}}& 8&{\text{ – }}&7&{\text{ – }}&5 \\
{\text{E}}& 4&2&3&5&{\text{ – }}
\end{array}\]
Draw G in a planar form.
Giving a reason, determine the maximum number of edges that could be added to G while keeping the graph both simple and planar.
List all the distinct Hamiltonian cycles in G beginning and ending at A, noting that two cycles each of which is the reverse of the other are to be regarded as identical. Hence determine the Hamiltonian cycle of least weight.
Answer/Explanation
Markscheme
A2
[2 marks]
For a simple planar graph containing triangles, \(e \leqslant 3v – 6\) M1
Here \(v = 5{\text{ , so }}e \leqslant 9\) . A1
There are already 8 edges so the maximum number of edges that could be added is 1. R1
This can be done e.g. AC or BD R1
[4 marks]
The distinct Hamiltonian cycles are
ABCDEA A2
ABCEDA A2
ABECDA A2
AEBCDA A2
Note: Do not penalise extra cycles.
The weights are 32, 32, 29, 28 respectively. A1
The Hamiltonian cycle of least weight is AEBCDA. R1
[10 marks]
Examiners report
A fairly common error in (a) was to draw a non-planar version of G, for which no credit was given. In (b), most candidates realised that only one extra edge could be added but a convincing justification was often not provided. Most candidates were reasonably successful in (c) although in some cases not all possible Hamiltonian cycles were stated.
A fairly common error in (a) was to draw a non-planar version of G, for which no credit was given. In (b), most candidates realised that only one extra edge could be added but a convincing justification was often not provided. Most candidates were reasonably successful in (c) although in some cases not all possible Hamiltonian cycles were stated.
A fairly common error in (a) was to draw a non-planar version of G, for which no credit was given. In (b), most candidates realised that only one extra edge could be added but a convincing justification was often not provided. Most candidates were reasonably successful in (c) although in some cases not all possible Hamiltonian cycles were stated.
Question
The adjacency table of the graph G , with vertices P, Q, R, S, T is given by:
(a) Draw the graph G .
(b) (i) Define an Eulerian circuit.
(ii) Write down an Eulerian circuit in G starting at P.
(c) (i) Define a Hamiltonian cycle.
(ii) Explain why it is not possible to have a Hamiltonian cycle in G .
Answer/Explanation
Markscheme
(a)
A3
Note: Award A2 for one missing or misplaced edge,
A1 for two missing or misplaced edges.
[3 marks]
(b) (i) an Eulerian circuit is one that contains every edge of the graph exactly once A1
(ii) a possible Eulerian circuit is
\({\text{P}} \to {\text{Q}} \to {\text{S}} \to {\text{P}} \to {\text{Q}} \to {\text{Q}} \to {\text{R}} \to {\text{T}} \to {\text{R}} \to {\text{R}} \to {\text{P}}\) A2
[3 marks]
(c) (i) a Hamiltonian cycle passes through each vertex of the graph A1
exactly once A1
(ii) to pass through T, you must have come from R and must return to R. R3
hence there is no Hamiltonian cycle
[5 marks]
Examiners report
Stronger candidates had little problem with this question, but a significant number of weaker candidates started by making errors in drawing the graph G, where the most common error was the omission of the loops and double edges. They also had problems working with the concepts of Eulerian circuits and Hamiltonian cycles.
Question
The following diagram shows a weighted graph G with vertices A, B, C, D and E.
Show that graph \(G\) is Hamiltonian. Find the total number of Hamiltonian cycles in \(G\), giving reasons for your answer.
State an upper bound for the travelling salesman problem for graph \(G\).
Hence find a lower bound for the travelling salesman problem for \(G\).
Show that the lower bound found in (d) cannot be the length of an optimal solution for the travelling salesman problem for the graph \(G\).
Answer/Explanation
Markscheme
eg the cycle \({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{D}} \to {\text{E}} \to {\text{A}}\) is Hamiltonian A1
starting from any vertex there are four choices
from the next vertex there are three choices, etc … R1
so the number of Hamiltonian cycles is \(4!{\text{ }}( = 24)\) A1
Note: Allow 12 distinct cycles (direction not considered) or 60 (if different starting points count as distinct). In any case, just award the second A1 if R1 is awarded.
[3 marks]
total weight of any Hamiltonian cycles stated
eg \({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{D}} \to {\text{E}} \to {\text{A}}\) has weight \(5 + 6 + 7 + 8 + 9 = 35\) A1
[1 mark]
a lower bound for the travelling salesman problem is then obtained by adding the weights of CA and CB to the weight of the minimum spanning tree (M1)
a lower bound is then \(14 + 6 + 6 = 26\) A1
[2 marks]
METHOD 1
eg eliminating A from G, a minimum spanning tree of weight 18 is (M1)
A1
adding AD and AB to the spanning tree gives a lower bound of \(18 + 4 + 5 = 27 > 26\) A1
so 26 is not the best lower bound AG
Note: Candidates may delete other vertices and the lower bounds obtained are B-28, D-27 and E-28.
METHOD 2
there are 12 distinct cycles (ignoring direction) with the following lengths
Cycle Length
ABCDEA 35 M1
ABCEDA 33
ABDCEA 39
ABDECA 37
ABECDA 31
ABEDCA 31
ACBDEA 37
ACBEDA 29
ACDBEA 35
ACEBDA 33
AEBCDA 31
AECBDA 37 A1
as the optimal solution has length 29 A1
26 is not the best possible lower bound AG
Note: Allow answers where candidates list the 24 cycles obtained by allowing both directions.
[3 marks]
Examiners report
Part (a) was generally well answered, with a variety of interpretations accepted.
Part (b) also had a number of acceptable possibilities.
Part (d) was generally well answered, but there were few good attempts at part (e).
Part (d) was generally well answered, but there were few good attempts at part (e).
Question
The distances by road, in kilometres, between towns in Switzerland are shown in the following table.
A cable television company wishes to connect the six towns placing cables along the road system.
Use Kruskal’s algorithm to find the minimum length of cable needed to connect the six towns.
Visitors to Switzerland can visit some principal locations for tourism by using a network of scenic railways as represented by the following graph:
(i) State whether the graph has any Hamiltonian paths or Hamiltonian cycles, justifying your answers.
(ii) State whether the graph has any Eulerian trails or Eulerian circuits, justifying your answers.
(iii) The tourist board would like to make it possible to arrive in Geneva, travel all the available scenic railways, exactly once, and depart from Zurich. Find which locations would need to be connected by a further scenic railway in order to make this possible.
Answer/Explanation
Markscheme
Zurich-Basel 85 M1A1
Berne-Basel 100 A1
Sion-Berne 155
Sion-Geneva 160
Zurich-Lugano 210 A1
total length of pipe needed is 710 km A1
Note: Award M1 for attempt to start with smallest length.
Note: Accept graphical solution showing lengths chosen.
Note: Award N1 for a correct spanning tree and N1 for 710 km with no method shown.
[6 marks]
(i) possible Hamiltonian path eg Geneva-Montreux-Zermatt-Lugano-St Moritz-Interlaken-Luzern-Zurich-Berne A1
no possible Hamiltonian cycles eg we would have to pass through Montreux twice as Geneva is only connected to Montreux or Interlaken twice R1
(ii) possible Eulerian trail as there are 2 odd vertices (Geneva and St Moritz) R1
no possible Eulerian circuits as not all even vertices R1
Note: Accept an example of a Eulerian trail for the first R1.
(iii) St Moritz to Zurich A2
Note: If St Moritz and Zurich are connected via existing edges award A1.
[6 marks]
Total [11 marks]
Examiners report
[N/A]
[N/A]