Questions on minimum spanning trees: Prim and Kruskal

Question 1

Define a minimum spanning tree and state how many edges it has for a network of n nodes.

Accepted Answer

A subset of the edges that connects every node with no cycle, chosen to have the least possible total weight. It always has exactly n − 1 edges: any fewer leaves the network disconnected and any more creates a cycle. B1 for the definition, B1 for n − 1 edges.

Question 2

Describe Prim's algorithm and Kruskal's algorithm in one sentence each, and say what they have in common.

Accepted Answer

Prim: start at any node and repeatedly add the cheapest edge joining the growing tree to a node not yet in it. Kruskal: sort the edges by weight and take them in order, rejecting any that would close a cycle. Both always produce a minimum spanning tree, so the totals always agree. B1 for Prim, B1 for Kruskal, B1 for what they share.

Question 3

A connected network has 12 nodes. State how many arcs its spanning tree has, and state what happens if one more arc of the network is added to that tree.

Accepted Answer

A spanning tree of n nodes has n − 1 arcs, so here it has 11. B1. Adding a twelfth arc joins two nodes the tree already connects, so it closes a cycle and the result is no longer a tree. B1.

Question 4

The adjacency matrix of a simple graph, rows and columns in the order P, Q, R, S, has row P reading 0, 1, 1, 0; row Q reading 1, 0, 1, 1; row R reading 1, 1, 0, 1; and row S reading 0, 1, 1, 0. Write down the order of each node and the number of edges, and check one against the other.

Accepted Answer

Each row sum counts the nodes that node is joined to, so the orders are P 2, Q 3, R 3, S 2. B1.
The orders total 2 + 3 + 3 + 2 = 10, and every edge contributes one to each of its two ends, so the number of edges is 10 ÷ 2 = 5. M1 for halving the total, A1 for 5.
The five edges are PQ, PR, QR, QS and RS, and counting the entries above the leading diagonal gives 5 as well, which is the check. The matrix of a simple graph is symmetric, with zeros all down the leading diagonal because no node is joined to itself; an entry of 2 anywhere would mean a repeated edge and the graph would not be simple.

Question 5

A network has nodes A to F and arcs AB 3, AC 5, BC 4, BD 8, BE 13, CD 9, CE 11, DE 7, DF 12, EF 6. Apply Prim's algorithm starting from A, listing the arcs in the order you add them, and state the weight of the tree.

Accepted Answer

From {A} the choices are AB 3 and AC 5, so take AB.
From {A, B}: AC 5, BC 4, BD 8, BE 13, so take BC (4).
From {A, B, C}: BD 8, CD 9, CE 11, BE 13, so take BD (8). AC has dropped out, because C is already in the tree.
From {A, B, C, D}: DE 7, CE 11, DF 12, BE 13, so take DE (7).
From {A, B, C, D, E}: EF 6 beats DF 12, so take EF.
Order AB, BC, BD, DE, EF, weight 3 + 4 + 8 + 7 + 6 = 28, five arcs for six nodes. M1 for a correct Prim scan, A1 for the order of arcs, A1 for the complete tree, A1 for the weight 28.

Question 6

A network has nodes A to F and arcs AB 3, AC 5, BC 4, BD 8, BE 13, CD 9, CE 11, DE 7, DF 12, EF 6. Apply Kruskal's algorithm, stating clearly any arc you reject and the reason.

Accepted Answer

Sorted: AB 3, BC 4, AC 5, EF 6, DE 7, BD 8, CD 9, CE 11, DF 12, BE 13.
Take AB (3), then BC (4).
Reject AC (5): A and C are already joined through B, so it would close the cycle ABC.
Take EF (6), then DE (7), then BD (8), which joins the two halves.
Five arcs, so stop. Weight 3 + 4 + 6 + 7 + 8 = 28. M1 for sorting the arcs, A1 for the arcs accepted in order, B1 for rejecting AC with a reason, A1 for the weight 28. This is the same tree Prim builds, reached in a different order; the minimum spanning tree is unique here because no two weights are equal.

Question 7

Give one reason for choosing Prim's algorithm rather than Kruskal's when a network is given as a distance matrix.

Accepted Answer

Prim reads straight off the matrix. Delete the row of each node as it joins, then scan the columns of the joined nodes for the smallest remaining entry. Kruskal would need every entry sorted into a single list first, and then a cycle check on each arc in turn. B1 for what Prim does with the matrix, B1 for the extra work Kruskal needs.

Question 8

A computer takes 0.54 seconds to apply Prim's algorithm, whose order is cubic, to a network of 30 nodes. Estimate the time it would take on a network of 90 nodes, justifying the scale factor you use.

Accepted Answer

An order of O(n³) means the work grows with the cube of the number of nodes: Prim runs n − 1 rounds and scans a table of about n² entries in each. So tripling the nodes multiplies the work by 3³ = 27. M1 for cubing the ratio of the sizes, B1 for the justification. The estimate is 0.54 × 27 ≈ 14.6 seconds. A1. The answer is an estimate because the order ignores constant factors and lower-order terms, not because the arithmetic is approximate.

Question 9

Five sites P, Q, R, S, T are to be linked. The cost matrix is symmetric, with PQ 12, PR 18, PS 10, PT 22, QR 15, QS 20, QT 14, RS 16, RT 11 and ST 19. Apply Prim's algorithm starting from P, giving the order in which the sites join and the least total cost.

Accepted Answer

Delete row P and scan column P: the entries are 12, 18, 10, 22 and the smallest is 10, so PS brings in S. M1 for the scan of the joined columns.
Scan columns P and S: 12, 18, 22, 20, 16, 19. The smallest is 12, so PQ brings in Q.
Scan P, S and Q: 18, 22, 16, 19, 15, 14. The smallest is 14, so QT brings in T.
Only R remains, and its cheapest link to {P, Q, S, T} is RT 11, so TR brings in R.
The sites join in the order P, S, Q, T, R, using PS, PQ, QT and TR. A1 for the joining order, A1 for the four arcs.
Least total cost 10 + 12 + 14 + 11 = 47. A1.

Question 10

A network has nodes P to U and arcs PQ 4, PR 6, PU 12, QR 5, QS 9, RS 7, RT 8, ST 3, SU 10, TU 6. Apply Kruskal's algorithm, stating clearly any arc you reject and why, and give the weight of the tree.

Accepted Answer

Sorted by weight: ST 3, PQ 4, QR 5, PR 6, TU 6, RS 7, RT 8, QS 9, SU 10, PU 12. M1 for sorting the arcs.
Take ST (3), then PQ (4), then QR (5).
Reject PR (6): P and R are already joined through Q, so it would close the cycle P, Q, R. B1 for the rejection with the cycle named.
Take TU (6), which is the same weight as the arc just rejected but joins U to a component it was not in. Then take RS (7), which joins {P, Q, R} to {S, T, U}. A1 for the accepted arcs in order.
Five arcs for six nodes, so stop. Weight 3 + 4 + 5 + 6 + 7 = 25. A1.

Question 11

A network of 7 nodes has a minimum spanning tree of weight 34. An arc of that tree, of weight 9, is then removed from the network altogether. The cheapest remaining arc joining the two parts the removal creates weighs 13. Find the weight of the new minimum spanning tree, explaining why the rest of the tree can be kept.

Accepted Answer

Removing one arc from a tree of 7 nodes leaves two pieces, each of them a tree, together holding 5 of the 6 arcs. Every node is still connected to the others in its own piece, so all that is needed is one arc joining the two pieces, and the cheapest such arc is the one to take. B1 for the tree splitting into two parts.
New weight = 34 − 9 + 13 = 38. M1 for the subtraction and addition, A1 for 38.

Question 12

Six villages are to be joined by a single water main. The table is the distance matrix for the villages: each entry is the cost, in thousands of pounds, of laying a pipe directly between that pair of villages. Use Prim's algorithm on the matrix, starting from A, to find the minimum spanning tree. Give the arcs in the order you select them and the total cost, and check the number of arcs you have used against the number of villages.

Accepted Answer

Delete row A and scan column A: the entries are 23, 17, 31, 40, 28, and the smallest is 17, so AC brings in C. M1 for deleting the row of each village as it joins and scanning the columns of the joined villages.
Delete row C and scan columns A and C: the smallest remaining entry is 14, so CD brings in D.
Delete row D and scan columns A, C and D: the entries available are AB 23, AE 40, AF 28, CB 19, CE 29, CF 36, DB 25, DE 18, DF 26, and the smallest is 18, so DE brings in E. A1 for CD and DE.
Delete row E and scan columns A, C, D and E: the smallest is 19, so CB brings in B. Then delete row B: the remaining column entries to F are AF 28, BF 21, CF 36, DF 26, EF 22, and the smallest is 21, so BF brings in F. A1 for CB and BF.
The tree is AC, CD, DE, CB, BF, of total cost 17 + 14 + 18 + 19 + 21 = 89, that is £89 000. A1 for the total.
Six villages need a spanning tree of n − 1 = 5 arcs, and five arcs were selected, so the count agrees. B1 for the check.

Question 13

Six sites A to F are to be linked by cable. The cost matrix is symmetric, with row A reading −, 17, 23, 15, 30, 25; row B reading 17, −, 19, 28, 16, 33; row C reading 23, 19, −, 21, 27, 14; row D reading 15, 28, 21, −, 24, 20; row E reading 30, 16, 27, 24, −, 18; and row F reading 25, 33, 14, 20, 18, −. Apply Prim's algorithm from A, giving the order in which the sites join and the least total cost. The link BE then becomes unavailable. Find the least total cost of connecting the six sites without it.

Accepted Answer

Delete row A and scan column A: the smallest entry is 15, so AD brings in D.
Scan columns A and D: 17, 23, 30, 25, 28, 21, 24, 20. The smallest is 17, so AB brings in B.
Scan A, D and B: the smallest is 16, so BE brings in E.
Scan A, D, B and E: the smallest is 18, so EF brings in F.
Only C remains, and its cheapest link is CF 14, so FC brings in C.
Sites join in the order A, D, B, E, F, C, using AD, AB, BE, EF, FC. Least total cost 15 + 17 + 16 + 18 + 14 = 80.
Now rerun from A with the BE entry struck out. AD 15 and AB 17 are unchanged. From {A, B, D} the cheapest available link is now BC 19, then CF 14, then FE 18. The tree is AD, AB, BC, CF, FE, costing 15 + 17 + 19 + 14 + 18 = 83, so losing BE adds 3 to the bill.
M1 for the Prim scan, A1 for the joining order, A1 for the arcs used, A1 for the cost 80, M1 for rerunning without BE, A1 for the new tree, A1 for the cost 83.
The tempting slip is to keep the first tree and reconnect E by its own next cheapest link, DE 24, giving 80 − 16 + 24 = 88. Deleting BE splits the tree into {A, B, D} and {C, E, F}, and the arc to look for is the cheapest one across that split, not the cheapest one at E. Only one arc of the tree changes, BC replacing BE; E now joins the Prim run from F rather than from B.

Question 14

A student runs Prim's algorithm, then runs Kruskal's on the same network to see whether it finds a cheaper tree. Explain why the second run can never improve on the first, when the two algorithms can nevertheless produce different trees, and what quicker check the student should have made instead.

Accepted Answer

Both algorithms are proved to produce a minimum spanning tree, so the two totals are always equal: there is no cheaper tree for the second run to find, whichever algorithm went first. B1 for both reaching the minimum total. The trees themselves can differ only when two edges share a weight, and then the choice between them is a tie broken differently; every tree produced still has the same least total. B1 for ties as the only source of difference. The check to make instead is structural: a spanning tree of n nodes must have exactly n − 1 edges and no cycle, so counting the edges and looking for a cycle verifies the first run without repeating it. B1 for the n − 1 edge check.

Question 15

A network has nodes P, Q, R, S and arcs PQ 5, PR 5, QR 5, QS 8 and RS 8. Find the weight of a minimum spanning tree, find how many different minimum spanning trees the network has, and explain what this means for a student who runs Prim's algorithm and then Kruskal's on it.

Accepted Answer

A spanning tree of four nodes has three arcs. S is reached only by QS or RS, each weighing 8, so exactly one arc of weight 8 is needed unless both are taken. M1 for three arcs and how S is reached.
Taking one 8 leaves P, Q and R to be connected by two of the three arcs of weight 5, giving 5 + 5 + 8 = 18. Taking both 8s leaves room for only one arc of weight 5, giving 8 + 8 + 5 = 21, which is worse. A1 for a minimum weight of 18.
Counting: two of PQ, PR, QR may be chosen in three ways, and each of those may be joined to S by either QS or RS, so there are 3 × 2 = 6 minimum spanning trees. M1 for counting the choices, A1 for six.
Prim and Kruskal will very likely return different trees here, because each has to break a tie and the two break it in different places. B1 for equal weights being the source of the difference.
Both totals will still be 18, since both algorithms are proved to reach a minimum. B1.

Question 16

Five sites P, Q, R, S, T have symmetric costs PQ 12, PR 18, PS 10, PT 22, QR 15, QS 20, QT 14, RS 16, RT 11, ST 19, and the minimum spanning tree PS, PQ, QT, TR has weight 47. The cost of PR is then reduced from 18 to 8. Find the new minimum spanning tree and its weight, explaining why only one arc has to be exchanged.

Accepted Answer

Add the cheaper arc PR to the existing tree. A tree plus one extra arc contains exactly one cycle, and PR closes P, Q, T, R, P, whose arcs are PQ 12, QT 14, RT 11 and the new PR 8. M1 for adding the arc and finding the cycle, A1 for the cycle.
Any spanning tree using PR must drop one other arc of that cycle, and dropping the heaviest of them is best. The heaviest is QT at 14. M1 for removing the heaviest other arc of the cycle, A1 for QT.
The new tree is PR, PS, RT, PQ, of weight 47 − 14 + 8 = 41. A1.
Rerunning Prim from P confirms it: PR 8, then PS 10, then RT 11, then PQ 12. Only the arcs on the one cycle can change, because every other arc of the old tree is still the cheapest way of bridging the split it makes, so a single exchange is all a reduction can ever force.

village	A	B	C	D	E	F
A	–	23	17	31	40	28
B	23	–	19	25	34	21
C	17	19	–	14	29	36
D	31	25	14	–	18	26
E	40	34	29	18	–	22
F	28	21	36	26	22	–

village	A	B	C	D	E	F
A	–	23	17	31	40	28
B	23	–	19	25	34	21
C	17	19	–	14	29	36
D	31	25	14	–	18	26
E	40	34	29	18	–	22
F	28	21	36	26	22	–

village	A	B	C	D	E	F
A	–	23	17	31	40	28
B	23	–	19	25	34	21
C	17	19	–	14	29	36
D	31	25	14	–	18	26
E	40	34	29	18	–	22
F	28	21	36	26	22	–