IB Mathematics Applications & Interpretation Question Type 1: Finding Minimum Spanning Trees by Applying Prim's Algorithm Exercises

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.

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.

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.

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

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

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

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.

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.

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.

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

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.

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:

$$\left[\begin{array}{ccccc}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{array}\right]$$

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.