IB Mathematics Applications & Interpretation Question Type 3: Applying Minimum Spanning Trees Under Real World Context Exercises

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.