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

Given the weighted undirected graph with vertices $A,B,C,D$ and edges with weights: $(A,B)=1,(A,C)=3,(A,D)=4,(B,C)=2,(C,D)=5$. Use Kruskal's algorithm to find the minimum spanning tree (MST). List the edges in the MST and its total weight.

Apply Kruskal's algorithm to find the minimum spanning tree (MST) for the graph. State the edges in the order they are considered, indicating whether each is included or rejected, and find the total weight of the MST.

A complete graph has vertices $A,B,C,D,E$ and edge weights as follows:

$(A,B)=2$ $(A,C)=9$ $(A,D)=3$ $(A,E)=6$ $(B,C)=1$ $(B,D)=7$ $(B,E)=8$ $(C,D)=4$ $(C,E)=5$ $(D,E)=10$

Find the minimum spanning tree (MST) using Kruskal's algorithm and state its total weight.

The vertices $1,2,3,4,5,6,7$ of a graph are connected by edges with the following weights:

$(1,2)=4$ $(1,3)=2$ $(2,3)=1$ $(2,4)=7$ $(3,5)=5$ $(4,5)=3$ $(4,6)=6$ $(5,7)=8$ $(6,7)=9$

Find the minimum spanning tree (MST) for this graph using Kruskal's algorithm and state its total weight.

A weighted graph has vertices $A,B,C,D,E$. The weights of the edges are given in the following table:

$$\begin{array}{lcccccccc}\text{Edge}& (A,B)& (A,C)& (A,D)& (B,C)& (B,E)& (C,D)& (C,E)& (D,E)\\ \text{Weight}& 3& 2& 4& 1& 5& 6& 7& 8\end{array}$$

Apply Kruskal's algorithm to determine the minimum spanning tree (MST) and its total weight. Show your working clearly.

A weighted graph has vertices $P,Q,R,S,T,U,V$ and the following edges with their respective weights:

$$(P,Q)=3,(P,R)=2,(Q,R)=1,(Q,S)=4,(R,T)=5,(S,T)=6,(S,U)=7,(T,V)=8,(U,V)=9$$

Use Kruskal's algorithm to determine the edges in the minimum spanning tree (MST) and calculate its total weight.

A graph with vertices $\{A,B,C,D,E,F,G\}$ has the following edges and weights:

• $(A,B)=2$
• $(A,C)=4$
• $(B,C)=1$
• $(B,D)=5$
• $(C,E)=3$
• $(D,E)=6$
• $(D,F)=7$
• $(E,G)=8$
• $(F,G)=9$

Find the minimum spanning tree (MST) using Kruskal's algorithm and state its total weight.

Consider the graph with vertices $\{1,2,3,4,5\}$ and edge weights: $(1,2)=10,(1,3)=8,(1,4)=5,(2,3)=7,(2,5)=6,(3,4)=9,(4,5)=2,(3,5)=3$.

Use Kruskal's algorithm to find the minimum spanning tree and its total weight.

A graph on vertices $A,B,C,D,E,F$ has edges and weights:

$(A,B)=2,(A,C)=5,(B,C)=1,(B,D)=4,(C,E)=3,(D,E)=6,(D,F)=7,(E,F)=8$.

Use Kruskal's algorithm to derive the Minimum Spanning Tree (MST) and its overall weight.

A graph has vertices $A,B,C,D,E$ and the following weighted edges:

$$(A,B)=2,(A,C)=4,(B,D)=3,(C,D)=5,(B,C)=1,(D,E)=6,(C,E)=7$$

Apply Kruskal's algorithm to determine the minimum spanning tree (MST) for this graph and compute its total weight. Show the steps of the algorithm, including which edges are selected or rejected.

Consider the graph with vertices $V=\{1,2,3,4,5,6\}$ and weighted edges $E$:

• $(1,2)=3$
• $(1,3)=1$
• $(2,3)=7$
• $(2,4)=5$
• $(3,5)=4$
• $(4,5)=2$
• $(4,6)=6$
• $(5,6)=8$

Use Kruskal's algorithm to find the minimum spanning tree (MST) of the graph and state its total weight.