Exercises for Question Type 1: Finding minimum spanning trees by applying Prim's algorithm - IB | RevisionDojo

Question Type 1: Finding minimum spanning trees by applying Prim's algorithm Exercises

Question 1

This question assesses the application of Prim's algorithm to find a Minimum Spanning Tree (MST) for a weighted undirected graph and the calculation of its total weight. Students are expected to show the step-by-step selection of vertices and edges.

A road planner has five towns $A, B, C, D, E$ with possible roads and construction costs as follows: $AB = 10$ , $AC = 6$ , $AD = 5$ , $BC = 15$ , $BD = 4$ , $CD = 12$ , $CE = 8$ , $DE = 7$ .

Use Prim’s algorithm starting at town $E$ to find the edges of the minimum spanning tree and its total cost.

[6]

Question 2

A network of six sensors forms a weighted graph: edges and distances (in metres) are $AB = 3$ , $AC = 1$ , $AD = 4$ , $BC = 2$ , $BD = 5$ , $CE = 6$ , $DE = 7$ , $DF = 8$ , $EF = 9$ . Find the minimum spanning tree using Kruskal’s algorithm and compute its total length.

[4]

Question 3

A rail network must connect five cities $A, B, C, D, E$ . Possible link costs are: $AB=14$ , $AC=9$ , $AD=22$ , $BC=18$ , $BD=3$ , $CE=16$ , $DE=7$ .

Determine the minimum spanning tree and total cost using Kruskal’s method.

[6]

Question 4

Consider the complete graph $K_4$ with vertices $\{1, 2, 3, 4\}$ and edge weights given by:

$12 = 1, \quad 13 = 2, \quad 14 = 3, \quad 23 = 4, \quad 24 = 5, \quad 34 = 6$

Find the edges of the minimum spanning tree and calculate its total weight.

[3]

Question 5

A telecommunications company must connect five relay stations $P, Q, R, S, T$ . The cost (in thousands) of laying cable between each pair is given: $PQ=4, PR=8, PS=5, QT=7, RS=6, RT=3, ST=2$ .

Model this as a graph and determine the minimum cost to connect all stations using Kruskal’s algorithm.

[5]

Question 6

In a project to connect remote outposts $W, X, Y, Z$ , the following possible connections and costs (units) exist: $WX=10$ , $WY=6$ , $WZ=5$ , $XY=4$ , $XZ=15$ , $YZ=2$ .

Use Prim’s algorithm starting at $W$ to find the minimum spanning tree and its total cost.

[4]

Question 7

The question requires the application of Kruskal's algorithm to find the Minimum Spanning Tree (MST) for a connected weighted graph representing an office network. Students must demonstrate knowledge of sorting edges, selecting the lowest-weight edges without forming cycles, and calculating the total weight of the resulting tree.

A company needs to lay fibre between seven offices, labelled $1$ through $7$ . The connection costs are given by the weighted edges:

\{(1,2,2),(1,3,3),(2,4,5),(2,5,4),(3,5,6),(4,6,7),(5,6,8),(5,7,9),(6,7,1)\}

Use Kruskal’s algorithm to find the minimum spanning tree and its total cost.

[5]

Question 8

A utility company plans to connect four substations $A, B, C, D$ with cables. The cost of connecting each pair is given: $AB=4, AC=1, AD=3, BC=2, BD=5, CD=6$ .

Illustrate the graph and determine the minimum spanning tree using Prim’s algorithm, starting at $A$ .

[6]

Question 9

In designing a countryside electrical grid, five farms $P, Q, R, S, T$ must be connected with minimal wiring cost. The terrain dictates the following possible connections: $PQ=11$ , $PR=7$ , $PS=9$ , $QT=5$ , $RT=4$ , $ST=8$ . Use Kruskal’s algorithm to find the minimum wiring cost.

[6]

Question 10

Use Prim’s algorithm, starting at vertex $1$ , on the graph represented by the following adjacency matrix to find a minimum spanning tree and its total weight:

\begin{bmatrix} 0 & 7 & 3 & 0 & 0 \\ 7 & 0 & 1 & 2 & 0 \\ 3 & 1 & 0 & 4 & 5 \\ 0 & 2 & 4 & 0 & 6 \\ 0 & 0 & 5 & 6 & 0 \end{bmatrix}

[4]

Question 11

Given the weighted graph with vertices $A, B, C, D$ and edges with weights $AB=2$ , $AC=3$ , $AD=6$ , $BC=5$ , $BD=4$ , and $CD=1$ , use Kruskal’s algorithm to find a minimum spanning tree and its total weight.

[6]