Question
The diagram above shows the graph \(G\).
(i) Explain briefly why \(G\) has no Eulerian circuit.
(ii) Determine whether or not \(G\) is bipartite.
(iii) Write down the adjacency matrix of G. Hence find the number of walks of length \(4\) beginning at A and ending at C.
The cost adjacency matrix of a graph with vertices P, Q, R, S, T, U is given by
Use Dijkstra’s Algorithm to find the length of the shortest path between the vertices P and S. Show all the steps used by the algorithm and list the order of the vertices in the path.
Answer/Explanation
Markscheme
(i) Because the graph has vertices of odd degree. R2
(ii) We are looking for \(2\) disjoint sets. (M1)
Put A in Set 1. Then B and D have to go in Set 2. This means that E and C have to go in Set 1. Therefore the disjoint sets are \(\left\{ {{\rm{B,D}}} \right\}\) and \(\left\{ {{\rm{A,C,E}}} \right\}\) . All the edges join a vertex from one set to a vertex in the other set. R2
The graph is bipartite. A1
(iii)
\({\boldsymbol{M}} = \left( {\begin{array}{*{20}{c}}
0&2&0&1&0 \\
2&0&1&0&2 \\
0&1&0&1&0 \\
1&0&1&0&1 \\
0&2&0&1&0
\end{array}} \right)\)
We require the (\(1\), \(3\)) or (\(3\), \(1\)) element of \({\boldsymbol{M}^4}\) . M1M1
Using a GDC, the number of walks of length \(4\) is \(36\). A2
[12 marks]
The length of the shortest path is \(18\). A2
EITHER
P U Q T R S A2
OR
P U Q T S A2
[12 marks]
Question
Use Kruskal’s algorithm to find a minimum spanning tree for the weighted graph shown below. State the weight of the tree.
For the travelling salesman problem defined by this graph, find
(i) an upper bound;
(ii) a lower bound.
Given that the integers \(m\) and \(n\) are such that \(3|({m^2} + {n^2})\) , prove that \(3|m\) and \(3|n\) .
Hence show that \(\sqrt 2 \) is irrational.
Answer/Explanation
Markscheme
Start at an edge with weight \(2\), say BH, add other edges of weight \(2\) such that a cycle is not formed. Continue to add edges of increasing weight until all vertices have been included. M1
thus the minimum spanning tree is
\({\rm{BH + HC + GK + KH + KE + EF + GA + CD}}\) A3
total weight \( = 2 + 2 + 3 + 4 + 4 + 4 + 5 + 5 = 29\) A1
Note: GB may replace KH and other orders are possible.
[5 marks]
(i) upper bound \( = 2 \times \) weight of minimum spanning tree M1
\( = 58\) A1
(ii) deleting vertex F M1
the minimum spanning tree is
\({\rm{BH + HC + GK + KE + KH + GA + CD}}\) A2
total weight \( = 2 + 2 + 3 + 4 + 4 + 5 + 5 = 25\) A1
adding the two edges of least weight from F M1
lower bound \( = 25 + 4 + 6 = 35\) A1
Note: Alternative solutions may be given by deleting a different vertex.
[8 marks]
EITHER
\(3|m \Rightarrow m \equiv 0(\bmod 3)\) (R1)
if this is false then \(m \equiv 1\) or \(2(\bmod 3)\) and \({m^2} \equiv 1\) or \(4(\bmod 3)\) R1A1
since \(4 \equiv 1(\bmod 3)\) then \({m^2} \equiv 1(\bmod 3)\) A1
similarly \({n^2} \equiv 1(\bmod 3)\) A1
hence \({m^2} + {n^2} \equiv 2(\bmod 3)\)
but \({m^2} + {n^2} \equiv 0(\bmod 3)\) (R1)
this is a contradiction so \(3|m\) and \(3|n\) R1AG
OR
\(m \equiv 0\) , 1 or \(2(\bmod 3)\) and \(n \equiv 0\) , 1 or \(2(\bmod 3)\) M1R1
\( \Rightarrow {m^2} \equiv 0\) or \(1(\bmod 3)\) and \({n^2} \equiv 0\) or \(1(\bmod 3)\) A1A1
so \({m^2} + {n^2} \equiv 0,1,2(\bmod 3)\) A1
but \(3|{m^2} + {n^2}\) so \({m^2} + {n^2} \equiv 0(\bmod 3)\) R1
\(m \equiv 0(\bmod 3)\) and \(n \equiv 0(\bmod 3)\) R1
\( \Rightarrow 3|m\) and \(3|n\) AG
[7 marks]
suppose \(\sqrt 2 = \frac{a}{b}\) , where \(a,b \in \mathbb{Z}\) and \(a\) and \(b\) are coprime M1
then
\(2{b^2} = {a^2}\) A1
\({a^2} + {b^2} = 3{b^2}\) A1
\(3{b^2} \equiv 0(\bmod 3)\) A1
but by (a) \(a\) and \(b\) have a common factor so \(\sqrt 2 \ne \frac{a}{b}\) R1
\( \Rightarrow \sqrt 2 \) is irrational AG
[5 marks]
Question
The vertices and weights of the graph \(G\) are given in the following table.
(a) (i) Use Kruskal’s algorithm to find the minimum spanning tree for \(G\), indicating clearly the order in which the edges are included.
(ii) Draw the minimum spanning tree for \(G\).
(b) Consider the travelling salesman problem for \(G\).
(i) An upper bound for the problem can be found by doubling the weight of the minimum spanning tree. Use this method to find an upper bound.
(ii) Starting at \({\text{A}}\), use the nearest neighbour algorithm to find another upper bound.
(iii) By first removing \({\text{A}}\), use the deleted vertex algorithm to find a lower bound for the problem.
(c) The travelling salesman problem is now modified so that starting at \({\text{A}}\), the vertices \({\text{B}}\) and \({\text{C}}\) have to be visited first in that order, then \({\text{D}}\), \({\text{E}}\), \({\text{F}}\) in any order before returning to \({\text{A}}\).
(i) Solve this modified problem.
(ii) Comment whether or not your answer has any effect on the upper bound to the problem considered in (b).
Answer/Explanation
Markscheme
(a) (i) using Kruskal’s algorithm, the minimum spanning tree is built up as follows
\({\text{BF}}\) A1
\({\text{BE, BC}}\) A1
\({\text{DE, AD}}\) A1
(ii) 
A1
[4 marks]
(b) (i) weight of minimum spanning tree \(= 69\) A1
Note: This mark may be earned earlier.
upper bound \(= 138\) A1
(ii) starting at \({\text{A}}\), the cycle is \({\text{A}} \to {\text{D}} \to {\text{E}} \to {\text{B}} \to {\text{F}} \to {\text{C}} \to {\text{A}}\) M1A1
an upper bound is the total weight of this cycle (M1)
\(17 + 16 + 12 + 10 + 20 + 19 = 94\) A1
(iii) the minimum spanning tree of the reduced graph is as above with AD removed (R1)
its total weight is \(10 + 12 + 14 + 16 = 52\) A1
adding the weights of the two deleted edges of the minimum spanning tree gives (M1)
lower bound \( = 52 + 17 + 18 = 87\) A1
[10 marks]
(c) (i) the possible cycles, and their weights, are
\({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{D}} \to {\text{E}} \to {\text{F}} \to {\text{A Weight 102 (or 70 exc A}} \to {\text{B}} \to {\text{C)}}\)
\({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{D}} \to {\text{F}} \to {\text{E}} \to {\text{A Weight 107 (or 75 exc A}} \to {\text{B}} \to {\text{C)}}\)
\({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{E}} \to {\text{D}} \to {\text{F}} \to {\text{A Weight 106 (or 74 exc A}} \to {\text{B}} \to {\text{C)}}\)
\({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{E}} \to {\text{F}} \to {\text{D}} \to {\text{A Weight 99 (or 67 exc A}} \to {\text{B}} \to {\text{C)}}\)
\({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{F}} \to {\text{D}} \to {\text{E}} \to {\text{A Weight 110 (or 78 exc A}} \to {\text{B}} \to {\text{C)}}\)
\({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{F}} \to {\text{E}} \to {\text{D}} \to {\text{A Weight 98 (or 66 exc A}} \to {\text{B}} \to {\text{C)}}\) A3
Note: Award A(3 – n) for \(n\) errors up to \(n = 2\), A0 thereafter.
the solution is therefore the cycle \({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{F}} \to {\text{E}} \to {\text{D}} \to {\text{A}}\)
(with weight \(98\)) A1
(ii) no, it has no effect A1
[5 marks]
Question
Consider the following weighted graph.
Determine whether or not the graph is Eulerian.
Determine whether or not the graph is Hamiltonian.
Use Kruskal’s algorithm to find a minimum weight spanning tree and state its weight.
Deduce an upper bound for the total weight of a closed walk of minimum weight which visits every vertex.
Explain how the result in part (b) can be used to find a different upper bound and state its value.
Answer/Explanation
Markscheme
the graph is not Eulerian A1
because the graph contains vertices of odd degree R1
[2 marks]
the graph is Hamiltonian A1
because, for example, ABDFHGECA is a Hamiltonian cycle R1
[2 marks]
correctly start to use Kruskal’s algorithm DE(1) (M1)
BC(2), FG(2) or vice-versa A1
DC(3), AC(3) or vice-versa A1
GH(4) (rejecting AB) A1
DF(5) or EG(5) (rejecting BD) A1
total weight \( = 20\) A1
[6 marks]
the minimum weight spanning tree can be traversed twice (M1)
so upper bound is \(2 \times 20 = 40\) A1
[2 marks]
the Hamiltonian cycle found in (b) is a closed walk visiting every vertex and hence can be applied here R1
weight \( = 39\) A1
[2 marks]
Question
While on holiday Pauline visits the local museum. On the ground floor of the museum there are six rooms, A, B, C, D, E and F. The doorways between the rooms are indicated on the following floorplan.
There are 6 museum s in 6 towns in the area where Pauline is on holiday. The 6 towns and the roads connecting them can be represented by a graph. Each vertex represents a town, each edge represents a road and the weight of each edge is the distance between the towns using that road. The information is shown in the adjacency table.
Pauline wants to visit each town and needs to start and finish in the same town.
Draw a graph G to represent this floorplan where the rooms are represented by the vertices and an edge represents a door between two rooms.
Explain why the graph G has an Eulerian trail but not an Eulerian circuit.
Explain the consequences of having an Eulerian trail but not an Eulerian circuit, for Pauline’s visit to the ground floor of the museum.
Write down a Hamiltonian cycle for the graph G.
Explain the consequences of having a Hamiltonian cycle for Pauline’s visit to the ground floor of the museum.
Use the nearest-neighbour algorithm to determine a possible route and an upper bound for the length of her route starting in town Z.
By removing Z, use the deleted vertex algorithm to determine a lower bound for the length of her route.
Answer/Explanation
Markscheme
A2
[2 Marks]
two vertices are of odd degree A1
to have an Eulerian circuit it must have all vertices of even degree R1
hence no Eulerian circuit, but an Eulerian trail AG
[2 Marks]
it allows Pauline to go through every door once (provided she starts in
room B or room E) A1
and she cannot return to the room in which she started A1
[2 Marks]
for example: A → F → E → D → C → B → A A2
Note: Award A1 if the cycle does not return to the start vertex.
[2 Marks]
she can visit every room once without repeating and return to the start A1
[1 Mark]
Z → V → Y → X → U → W → Z A1
6 + 4 + 9 + 7 + 10 + 10 = 46 A1
[2 marks]
attempt to find the minimal spanning tree (M1)
VY
VW
UX
XY A2
Note: Award A1 if one error made.
Note: Accept correct drawing of minimal spanning tree.
weight of minimal spanning tree = 4 + 5 + 7 + 9 = 25 (A1)
since Z is removed, we add on VZ and ZY (M1)
hence lower bound for route is 25 + 13 = 38 A1
[6 marks]