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

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.

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.

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$, $DE=2$. Find the minimum spanning tree using Kruskal’s algorithm and its total cable length.

Four towns X, Y, Z and W are connected by roads with distances: $X\!–\!Y=4$, $Y\!–\!Z=3$, $Z\!–\!W=2$, $X\!–\!W=6$, $X\!–\!Z=5$. Find the minimum spanning tree and its total distance. Then a new road $Y\!–\!W=1$ is built. Determine the new minimum spanning tree and its total distance.

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.

Six oil wells labelled 1–6 require a pipeline network. The potential pipe lengths (km) are: $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 its total length.

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$, $CE=4$. The minimum spanning tree uses edges $AB$, $BC$, $CD$ and $DE$. If road $CD$ is closed, determine which replacement road should be used from the available roads and give the new total 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: $V\!–\!W=6$, $V\!–\!X=3$, $W\!–\!X=2$, $W\!–\!Y=5$, $X\!–\!Y=4$, $X\!–\!Z=7$, $Y\!–\!Z=1$. Start the algorithm at node V. List the edges in the order added and give the total weight.

Seven power stations A through G must be interconnected. The possible line costs (in units) are: $B\!–\!D=1$, $A\!–\!B=2$, $A\!–\!D=3$, $B\!–\!C=4$, $C\!–\!D=5$, $D\!–\!E=6$, $C\!–\!E=7$, $D\!–\!F=8$, $E\!–\!F=9$, $E\!–\!G=10$, $F\!–\!G=11$. Find the minimum spanning tree and its total cost.

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.

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 (km) are: $W\!–\!X=5$, $W\!–\!Y=3$, $X\!–\!Y=4$, $X\!–\!Z=6$, $Y\!–\!Z=2$, $Y\!–\!U=7$, $Z\!–\!U=1$, $Z\!–\!V=8$, $U\!–\!V=9$. List the edges as they are added and give the total distance.

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.