IB DP Maths Topic 10.9 Graph algorithms: Kruskal’s; Dijkstra’s. HL Paper 3

 

https://play.google.com/store/apps/details?id=com.iitianDownload IITian Academy  App for accessing Online Mock Tests and More..

Question

The weighted graph H is shown below.

Use Kruskal’s Algorithm, indicating the order in which the edges are added, to find and draw the minimum spanning tree for H.

[6]
a.

(i)     A tree has v vertices. State the number of edges in the tree, justifying your answer.

(ii)     We will call a graph with v vertices a “forest” if it consists of c components each of which is a tree. 

Here is an example of a forest with 4 components.

 

How many edges will a forest with v vertices and c components have?

[5]
b.
Answer/Explanation

Markscheme

The edges are included in the order

CF     A1

EF     A1

BC     A1

CD     A1

AB     A1

     A1

[6 marks]

a.

(i)     A tree with v vertices has v −1 edges.     A1

Using v + f = e + 2 with f = 1, the result follows.     R1

 

(ii)     Each of the c trees will have one less edge than the number of vertices.     R1

Thus the forest will have v c edges.     A2

[5 marks]

b.

Examiners report

In (a), many candidates derived the minimum spanning tree although in some cases the method was not clearly indicated as required and some candidates used an incorrect algorithm. Part (b) was reasonably answered by many candidates although some justifications were unsatisfactory. Part (c) caused problems for many candidates who found difficulty in writing down a rigorous proof of the required result. 

a.

In (a), many candidates derived the minimum spanning tree although in some cases the method was not clearly indicated as required and some candidates used an incorrect algorithm. Part (b) was reasonably answered by many candidates although some justifications were unsatisfactory. Part (c) caused problems for many candidates who found difficulty in writing down a rigorous proof of the required result. 

b.

Question

Use Kruskal’s algorithm to find the minimum spanning tree for the following weighted graph and state its length.

[5]
a.

Use Dijkstra’s algorithm to find the shortest path from A to D in the following weighted graph and state its length.

 

[7]
b.
Answer/Explanation

Markscheme

Kruskal’s algorithm gives the following edges

CD     (4)     M1A1

AD     (5)

EF     (7)     A1

EA     (8)

BC     (11)

FG     (12)     A1     N0

length of the spanning tree is 47     A1

[5 marks]

a.

for Dijkstra’s algorithm there are three things associated with a node: order; distance from the initial node as a permanent or temporary node     M1

     A4

Note: Deduct A1 for each error or omission.

the shortest path is AFBCD     A1

the length is 26     A1     N0

[7 marks]

b.

Examiners report

Setting out clearly the steps of the algorithms is still a problem for many although getting the correct spanning tree and its length were not.

a.

Setting out clearly the steps of the algorithms is still a problem for many although getting the correct spanning tree and its length were not.

b.

Question

Sameer is trying to design a road system to connect six towns, A, B, C, D, E and F. The possible roads and the costs of building them are shown in the graph below. Each vertex represents a town, each edge represents a road and the weight of each edge is the cost of building that road. He needs to design the lowest cost road system that will connect the six towns.

 

(a)     Name an algorithm which will allow Sameer to find the lowest cost road system.

(b)     Find the lowest cost road system and state the cost of building it. Show clearly the steps of the algorithm.

Answer/Explanation
Answer/Explanation

Markscheme

(a)     EITHER

Prim’s algorithm     A1

OR

Kruskal’s algorithm     A1

[1 mark]

 

(b)     EITHER

using Prim’s algorithm, starting at A

lowest cost road system contains roads AC, CD, CF, FE and AB     A1

cost is 20     A1

OR

using Kruskal’s algorithm

lowest cost road system contains roads CD, CF, FE, AC and AB     A1

cost is 20     A1

Note: Accept alternative correct solutions.

 

[7 marks]

Total [8 marks]

Examiners report

Most candidates were able to name an algorithm to find the lowest cost road system and then were able apply the algorithm. All but the weakest candidates were able to make a meaningful start to this question. In 1(b) some candidates lost marks by failing to indicate the order in which edges were added.

Question

The diagram below shows the weighted graph G .

(a)     (i)     What feature of the graph enables you to deduce that G contains an Eulerian circuit?

  (ii)     Find an Eulerian circuit.

(c)     Use Kruskal’s Algorithm to find the minimum spanning tree for G , showing the order in which the edges are added.

Answer/Explanation

Markscheme

(a)     (i)     all the vertices have even degree     A1

  (ii)     for example ABCDECFBEFA     A2

[3 marks]

 

(c)     the edges are included in the order shown

     M1A1A1A1A1A1

Note: Award each A1 for the edge added in the correct order. Award no further marks after the first error.

 

[6 marks]

Total [9 marks]

Examiners report

Part (a) was well answered in general. Part (c) was well answered.

Question

A graph G with vertices A, B, C, D, E has the following cost adjacency table.

\[\begin{array}{*{20}{c|ccccc}}
  {}&{\text{A}}&{\text{B}}&{\text{C}}&{\text{D}}&{\text{E}} \\
\hline
  {\text{A}}& – &{12}&{10}&{17}&{19} \\
  {\text{B}}&{12}& – &{13}&{20}&{11} \\
  {\text{C}}&{10}&{13}& – &{16}&{14} \\
  {\text{D}}&{17}&{20}&{16}& – &{15} \\
  {\text{E}}&{19}&{11}&{14}&{15}& –  
\end{array}\]

(a)     (i)     Use Kruskal’s algorithm to find and draw the minimum spanning tree for G.

  (ii)     The graph H is formed from G by removing the vertex D and all the edges connected to D. Draw the minimum spanning tree for H and use it to find a lower bound for the travelling salesman problem for G.

(b)     Show that 80 is an upper bound for this travelling salesman problem.

Answer/Explanation

Markscheme

(a)     (i)     the edges are joined in the order

AC

BE

AB

ED     A2

     A1

Note: Final A1 independent of the previous A2.

(ii)

     A1

the weight of this spanning tree is 33     A1

to find a lower bound for the travelling salesman problem, we add to that the two smallest weights of edges to D, i.e. 15 +16, giving 64     M1A1

[7 marks]

 

(b)     an upper bound is the weight of any Hamiltonian cycle, e.g. ABCDEA has weight 75 so 80 is certainly an upper bound     M1A1

[2 marks]

Total [9 marks]

Examiners report

Part (a) was well done by many candidates although some candidates simply drew the minimum spanning tree in (i) without indicating the use of Kruskal’s Algorithm. It is important to stress to candidates that, as indicated in the rubric at the top of Page 2, answers must be supported by working and/or explanations. Part (b) caused problems for some candidates who obtained the unhelpful upper bound of 96 by doubling the weight of the minimum spanning tree. It is useful to note that the weight of any Hamiltonian cycle is an upper bound and in this case it was fairly easy to find such a cycle with weight less than or equal to 80.

Question

Consider the following weighted graph.

 

 

(a)     (i)     Use Kruskal’s algorithm to find the minimum spanning tree. Indicate the order in which you select the edges and draw the final spanning tree.

  (ii)     Write down the total weight of this minimum spanning tree.

(b)     Sketch a spanning tree of maximum total weight and write down its weight.

Answer/Explanation

Markscheme

(a)     (i)     (Kruskal’s: successively take an edge of smallest weight without forming a cycle)

\({1^{{\text{st}}}}\) edge DC (weight 1)     A1

\({2^{{\text{nd}}}}\) edge EG (weight 2)     A1

\({3^{{\text{rd}}}}\) edge DE (weight 3)     A1

\({4^{{\text{th}}}}\) edge EF (weight 6)     A1

\({5^{{\text{th}}}}\) edge AD (weight 7)     A1

\({6^{{\text{th}}}}\) edge AB (weight 8)     A1

    A1

Notes: Weights are not required on the diagram.

Allow A2(d) if the (correct) edges are in the wrong order e.g. they have used Prim’s rather than Kruskal’s algorithm.

 

(ii)     total weight is 1 + 2 + 3 + 6 + 7 + 8 = 27     A1

[8 marks]

 

(b)     EITHER

    A3

OR

    A3

Notes: Award A2 for five or four correct edges,

A1 for three or two correct edges

A0 otherwise.

Weights are not required on the diagram.

 

THEN

total weight is 6 + 7 + 7 + 8 + 9 + 10 = 47     A1

[4 marks]

Total [12 marks]

Examiners report

Good algorithm work was shown; sometimes there were mistakes in giving the order of the edges chosen by, for example doing Prim’s algorithm instead of Kruskal’s.

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.

[6]
a.

(i)     Does this graph have an Eulerian circuit? Justify your answer.

(ii)     Does this graph have an Eulerian trail? Justify your answer.

[4]
b.

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.

[4]
c.
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]

a.

(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]

b.

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]

c.

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.

a.

Fairly good knowledge shown here but not by all.

b.

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.

c.

Question

The diagram shows a weighted graph with vertices A, B, C, D, E, F, G. The weight of each edge is marked on the diagram.

(i)     Explain briefly why the graph contains an Eulerian trail but not an Eulerian circuit.

(ii)     Write down an Eulerian trail.

[4]
a.

(i)     Use Dijkstra’s algorithm to find the path of minimum total weight joining A to D.

(ii)     State the minimum total weight.

[8]
b.
Answer/Explanation

Markscheme

(i)     there is an Eulerian trail because there are only 2 vertices of odd degree     R1

there is no Eulerian circuit because not all vertices have even degree     R1

 

(ii)     eg GBAGFBCFECDE     A2

[4 marks]

a.

(i)

\(\begin{array}{*{20}{l}}
  {{\text{Step}}}&{{\text{Vertices labelled}}}&{{\text{Working values}}}&{} \\
  1&{\text{A}}&{{\text{A(0), B-3, G-2}}}&{{\boldsymbol{M1A1}}} \\
  2&{{\text{A, G}}}&{{\text{A(0), G(2), B-3, F-8}}}&{{\boldsymbol{A1}}} \\
  3&{{\text{A, G, B}}}&{{\text{A(0), G(2), B(3), F-7, C-10}}}&{{\boldsymbol{A1}}} \\
  4&{{\text{A, G, B, F}}}&{{\text{A(0), G(2), B(3), F(7), C-9, E-12}}}&{} \\
  5&{{\text{A, G, B, F, C}}}&{{\text{A(0), G(2), B(3), F(7), C(9), E-10, D-15}}}&{{\boldsymbol{A1}}} \\
  6&{{\text{A, G, B, F, C, E}}}&{{\text{A(0), G(2), B(3), F(7), C(9), E(10), D-14}}}&{} \\
  7&{{\text{A, G, B, F, C, E, D}}}&{{\text{A(0), G(2), B(3), F(7), C(9), E(10), D(14)}}}&{{\boldsymbol{A1}}}
\end{array}\)

Note: In both (i) and (ii) accept the tabular method including back tracking or labels by the vertices on a graph.

Note: Award M1A1A1A1A0A0 if final labels are correct but intermediate ones are not shown.

(ii)     minimum weight path is ABFCED     A1

minimum weight is 14     A1

Note: Award the final two A1 marks whether or not Dijkstra’s Algorithm is used.

[8 marks]

b.

Examiners report

In part (a) the criteria for Eulerian circuits and trails were generally well known and most candidates realised that they must start/finish at G/E. Candidates who could not do (a) generally struggled on the paper.

a.

For part (b) the layout varied greatly from candidate to candidate. Not all candidates made their method clear and some did not show the temporary labels. It is recommended that teachers look at the tabular method with its backtracking system as it is an efficient way of tackling this type of problem and has a very clear layout.

b.

Question

The following diagram shows a weighted graph.



 

(a)     Use Kruskal’s algorithm to find a minimum spanning tree, clearly showing the order in which the edges are added.

(b)     Sketch the minimum spanning tree found, and write down its weight.

Answer/Explanation

Markscheme

(a)     use Kruskal’s algorithm: begin by choosing the shortest edge and then select a sequence of edges of non-decreasing weights, checking at each stage that no cycle is completed     (M1)

choice edge weight
1BG1
2AG2
3FG3
4BC4
5DE5
6AH6
7EG7

A1

A3

Note: A1 for steps 2–4, A1for step 5 and A1for steps 6, 7.

     Award marks only if it is clear that Kruskal’s algorithm is being used.

[5 marks] 

(b)     weight \( = 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28\)     A1


     A1

Note: Award FT only if it is a spanning tree.

[2 marks]

Examiners report

Well answered by the majority of candidates.

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.

[7]
a.

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.

[6]
b.
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]

a.

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]

b.

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.

a.

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).

b.

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.

[8]
a.

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.

[3]
b.

(i)     State the travelling salesman problem.

(ii)     Explain why there is no solution to the travelling salesman problem for this graph.

[3]
c.
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\)     A1

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]

a.

(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]

b.

(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]

c.

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).

a.

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.

b.

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.

c.

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.

[5]
a.

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.

[6]
b.
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]

a.

(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]

b.

Examiners report

[N/A]

a.

[N/A]

b.

Question

The weights of the edges in the complete graph \(G\) are shown in the following table.

Starting at A, use the nearest neighbour algorithm to find an upper bound for the travelling salesman problem for \(G\).

[5]
a.

By first removing A , use the deleted vertex algorithm to find a lower bound for the travelling salesman problem for \(G\).

[7]
b.
Answer/Explanation

Markscheme

attempt to use the nearest neighbour algorithm     M1

\(\begin{array}{*{20}{l}} {{\text{the nearest neighbour path is}}}&{{\text{A}} \to {\text{D}} \to {\text{C }}A1} \\ {}&{ \to {\text{E}} \to {\text{B}} \to {\text{F}} \to {\text{A }}A1} \end{array}\)

the upper bound is the total weight of this path, ie     (M1)

\(8 + 7 + 8 + 10 + 13 + 9 = 55\)    A1

Note:     The (M1) is for adding 6 weights together.

[5 marks]

a.

attempt to use an appropriate algorithm, with A deleted, to determine the minimum spanning tree, eg Kruskal’s     (M1)

CD (7)     A1

CE, CB (8,9)     A1

DF or EF (11)     A1

the weight of this minimum spanning tree is 35     (A1)

adding in the two smallest weights joining A (AD and AF) to this tree gives a lower bound     (M1)

of \(35 + 8 + 9 = 52\)     A1

Note:     Clear diagrams aiding solutions are acceptable in (a) and (b).

[7 marks]

b.

Examiners report

Generally good use of the nearest neighbour algorithm. Some candidates showed no knowledge of it and there was some confusion with the twice the weight of a minimal spanning tree method. Some candidates forgot to go back to A and thus did not have a Hamiltonian cycle.

a.

The method was generally known. Some candidates used nearest neighbour instead of Kruskal’s algorithm to find a minimal spanning tree. Some forgot to add in the two edges connected to . Some with the right method made mistakes in not noticing the correct edge to choose. A

b.

Question

The simple, complete graph \({\kappa _n}(n > 2)\) has vertices \({{\text{A}}_1},{\text{ }}{{\text{A}}_2},{\text{ }}{{\text{A}}_3},{\text{ }} \ldots ,{\text{ }}{{\text{A}}_n}\). The weight of the edge from \({{\text{A}}_i}\) to \({{\text{A}}_j}\) is given by the number \(i + j\).

Consider the general graph \({\kappa _n}\).

(i)     Draw the graph \({\kappa _4}\) including the weights of all the edges.

(ii)     Use the nearest-neighbour algorithm, starting at vertex \({{\text{A}}_1}\), to find a Hamiltonian cycle.

(iii)     Hence, find an upper bound to the travelling salesman problem for this weighted graph.

[4]
a.

Consider the graph \({\kappa _5}\). Use the deleted vertex algorithm, with \({{\text{A}}_5}\) as the deleted vertex, to find a lower bound to the travelling salesman problem for this weighted graph.

[5]
b.

(i)     Use the nearest-neighbour algorithm, starting at vertex \({{\text{A}}_1}\), to find a Hamiltonian cycle.

(ii)    Hence find and simplify an expression in \(n\), for an upper bound to the travelling salesman problem for this weighted graph.

[7]
c.

By splitting the weight of the edge \({{\text{A}}_i}{{\text{A}}_j}\) into two parts or otherwise, show that all Hamiltonian cycles of \({\kappa _n}\) have the same total weight, equal to the answer found in (c)(ii).

[3]
d.
Answer/Explanation

Markscheme

(i)          A1A1

Note: A1 for the graph, A1 for the weights.

(ii)     cycle is \({{\text{A}}_1}{{\text{A}}_2}{{\text{A}}_3}{{\text{A}}_4}{{\text{A}}_1}\)     A1

(iii)     upper bound is \(3 + 5 + 7 + 5 = 20\)     A1

[4 marks]

a.

with \({{\text{A}}_5}\) deleted, (applying Kruskal’s Algorithm) the minimum spanning tree will consist of the edges \({{\text{A}}_1}{{\text{A}}_2},{\text{ }}{{\text{A}}_1}{{\text{A}}_3}{\text{, }}{{\text{A}}_1}{{\text{A}}_4}\), of weights 3, 4, 5     (M1)A1

the two edges of smallest weight from \({{\text{A}}_5}\) are \({{\text{A}}_5}{{\text{A}}_1}\) and \({{\text{A}}_5}{{\text{A}}_2}\) of weights 6 and 7     (M1)A1

so lower bound is \(3 + 4 + 5 + 6 + 7 = 25\)     A1

[5 marks]

b.

(i)     starting at \({{\text{A}}_1}\) we go \({{\text{A}}_2},{\text{ }}{{\text{A}}_3}{\text{ }} \ldots {\text{ }}{{\text{A}}_n}\)

we now have to take \({{\text{A}}_n}{{\text{A}}_1}\)

thus the cycle is \({{\text{A}}_1}{{\text{A}}_2}{{\text{A}}_3} \ldots {{\text{A}}_{n – 1}}{{\text{A}}_n}{{\text{A}}_1}\)     A1A1

Note: Final A1 is for \({{\text{A}}_n}{{\text{A}}_1}\).

(ii)     smallest edge from \({{\text{A}}_1}\) is \({{\text{A}}_1}{{\text{A}}_2}\) of weight 3, smallest edge from \({{\text{A}}_2}\) (to a new vertex) is \({{\text{A}}_2}{{\text{A}}_3}\) of weight 5, smallest edge from \({{\text{A}}_{n – 1}}\) (to a new vertex) is \({{\text{A}}_{n – 1}}{{\text{A}}_n}\) of weight \(2n – 1\)     (M1)

weight of \({{\text{A}}_n}{{\text{A}}_1}\) is \(n + 1\)

weight is \(3 + 5 + 7 +  \ldots  + (2n – 1) + (n + 1)\)     A1

\( = \frac{{(n – 1)}}{2}(2n + 2) + (n + 1)\)    M1A1

\( = n(n + 1)\) (which is an upper bound)     A1

Note: Follow through is not applicable.

[7 marks]

c.

put a marker on each edge \({{\text{A}}_i}{{\text{A}}_j}\) so that \(i\) of the weight belongs to vertex \({{\text{A}}_i}\) and \(j\) of the weight belongs to vertex \({{\text{A}}_j}\)     M1

the Hamiltonian cycle visits each vertex once and only once and for vertex \({{\text{A}}_i}\) there will be weight \(i\) (belonging to vertex \({{\text{A}}_i}\)) both going in and coming out     R1

so the total weight will be \(\sum\limits_{i = 1}^n {2i = 2\frac{n}{2}(n + 1) = n(n + 1)} \)     A1AG

Note: Accept other methods for example induction.

[3 marks]

d.

Examiners report

[N/A]

a.

[N/A]

b.

[N/A]

c.

[N/A]

d.

Question

The weights of the edges of a graph G with vertices A, B, C, D and E are given in the following table.

 

Starting at A, use the nearest neighbour algorithm to find an upper bound for the travelling salesman problem for G .

[4]
a.

(i)     Use Kruskal’s algorithm to find and draw a minimum spanning tree for the subgraph obtained by removing the vertex A from G .

(ii)     Hence use the deleted vertex algorithm to find a lower bound for the travelling salesman problem for G .

[8]
b.
Answer/Explanation

Markscheme

using the nearest neighbour algorithm, starting with A,

\({\text{A}} \to {\text{E, E}} \to {\text{C}}\)     A1

\({\text{C}} \to {\text{D, D}} \to {\text{B}}\)     A1

\({\text{B}} \to {\text{A}}\)     A1

the upper bound is therefore 9 + 10 + 16 + 13 + 11 = 59     A1

[4 marks]

a.

(i)     the edges are added in the order CE     A1

BD     A1

BE     A1

     A1

(ii)     the weight of the minimum spanning tree is 37     (A1)

we now reconnect A with the 2 edges of least weight     (M1)

i.e. AE and AB     A1

the lower bound is therefore 37 + 9 + 11 = 57     A1

[8 marks]

b.

Examiners report

[N/A]

a.

[N/A]

b.

Leave a Reply