RevisionDojo

Question 1

This question assesses the application of Kruskal’s algorithm to determine the minimum spanning tree (MST) of a weighted graph and the calculation of the MST's total weight.

Five substations $A, B, C, D$ and $E$ must be connected by cables. The cable lengths (in km) are: $AB=10$ , $AC=8$ , $AD=5$ , $BC=7$ , $BD=6$ , $BE=9$ , $CD=4$ , $CE=3$ , and $DE=2$ .

Find the minimum spanning tree using Kruskal’s algorithm and determine its total cable length.

[5]

Question 2

Four towns $X, Y, Z$ and $W$ are connected by roads with the following distances:

$XY = 4$
$YZ = 3$
$ZW = 2$
$XW = 6$
$XZ = 5$

1.

Find the minimum spanning tree and its total distance for the original network.

[3]

2.

A new road $YW = 1$ is built. Determine the new minimum spanning tree and its total distance.

[3]

Question 3

Use Prim’s algorithm to find a minimum spanning tree for the network with nodes $V, W, X, Y$ and $Z$ and weighted edges: $VW=6$ , $VX=3$ , $WX=2$ , $WY=5$ , $XY=4$ , $XZ=7$ , $YZ=1$ .

Start the algorithm at node $V$ . List the edges in the order added and give the total weight.

[5]

Question 4

Five villages $A, B, C, D$ and $E$ are connected by the roads: $AB = 4$ , $BC = 3$ , $CD = 5$ , $DE = 2$ , $AC = 6$ , $BD = 7$ , and $CE = 4$ . A spanning tree for this network uses edges $AB, BC, CD$ and $DE$ .

If road $CD$ is closed, determine which replacement road should be used to reconnect the villages into a spanning tree with the minimum possible total weight, and calculate the new total length.

[4]

Question 5

Six cities $P, Q, R, S, T$ and $U$ must be connected by telecommunication links. The costs (in units) of possible links are: $PS=1$ , $PQ=2$ , $QS=2$ , $TU=2$ , $PR=3$ , $RT=3$ , $QR=4$ , $RS=5$ , $SU=6$ .

Determine the minimum spanning tree and its total cost.

[4]

Question 6

Seven power stations A through G must be interconnected. The possible line costs (in units) are: $BD=1, AB=2, AD=3, BC=4, CD=5, DE=6, CE=7, DF=8, EF=9, EG=10, FG=11$ .

Find the minimum spanning tree and its total cost.

[4]

Question 7

The question asks to find the minimum spanning tree (MST) of a weighted graph representing mountain towns and roads using an algorithm such as Kruskal's or Prim's, and to calculate the total weight of the MST.

Five mountain towns numbered 1 to 5 need roads. The difficulty ratings for roads are: $1-2=12$ , $1-3=10$ , $2-3=8$ , $2-4=15$ , $3-4=6$ , $3-5=7$ , $4-5=9$ . Find the minimum spanning tree that minimizes total difficulty and state its difficulty sum.

[4]

Question 8

Six computer labs A, B, C, D, E and F require cable connections. Possible cable lengths (m) are: $AB=8$ , $AC=6$ , $AD=7$ , $BC=3$ , $BE=5$ , $CD=4$ , $CF=9$ , $DF=2$ , $EF=1$ .

Find the minimum spanning tree and its total cable length.

[5]

Question 9

Starting from warehouse $W$ , use Prim’s algorithm to connect six warehouses $W, X, Y, Z, U$ and $V$ with minimum total distance. The distances (in km) are: $WX = 5, WY = 3, XY = 4, XZ = 6, YZ = 2, YU = 7, ZU = 1, ZV = 8, UV = 9$ .

List the edges as they are added and give the total distance.

[6]

Question 10

Five sensors $A, B, C, D$ and $E$ in a wireless network must be connected. The energy costs for links are: $AB=1$ , $AC=4$ , $BC=2$ , $BD=5$ , $CD=3$ , $CE=6$ , $DE=7$ .

Determine the minimum spanning tree and its total energy cost.

[4]

Question 11

Six oil wells, labelled 1 to 6, require a pipeline network. The potential pipe lengths (in km) between the wells are as follows:

$1-2 = 4$ ; $1-3 = 6$ ; $1-4 = 5$ ; $2-3 = 7$ ; $2-5 = 3$ ; $3-5 = 8$ ; $4-5 = 2$ ; $4-6 = 9$ ; $5-6 = 4$

Determine the minimum spanning tree and calculate its total length.

[4]

Question 12

Five villages $A, B, C, D$ and $E$ need to be connected by roads. The lengths (in km) of possible roads are: $AB=4$ , $AC=2$ , $AD=5$ , $BC=1$ , $BD=3$ , $CD=6$ , $CE=7$ , $DE=4$ .

Determine the minimum spanning tree and its total length.

[4]

Question Type 3: Applying minimum spanning trees under real world context Exercises