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

Given the complete graph $K_4$ with vertices $1,2,3,4$ and edge weights: $12=1$, $13=2$, $14=3$, $23=4$, $24=5$, $34=6$, find the minimum spanning tree and its weight.

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

In a project to connect remote outposts $W,X,Y,Z$, the following possible connections and costs ($ext{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 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 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$.

Use Prim’s algorithm starting at vertex $1$ on the graph with adjacency matrix:

to find a minimum spanning tree and its total weight.

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.

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.

A road planner has five towns $A,B,C,D,E$ with possible roads and construction costs: $AB=10$, $AC=6$, $AD=5$, $BC=15$, $BD=4$, $CD=12$, $CE=8$, $DE=7$. Use Prim’s algorithm starting at $E$ to find a minimum spanning tree and the total cost.

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.

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

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