Question

use kruskals algorithm to find the minimum spanning tree for the weighted graph.
give the total weight of the minimum spanning tree.

75
202
119
164

Explanation:

List and sort all edge weights in ascending order

$$ 19, 21, 37, 38, 42, 45 $$

Apply Kruskal's algorithm to select edges without forming cycles

$$
LATEXBLOCK0
$$

Calculate the total weight of the minimum spanning tree

$$ \text{Total Weight} = 19 + 21 + 37 + 38 = 115 $$

Wait, let's re-examine the graph structure and vertices to ensure connectivity.
The graph has 5 vertices:

• Left-top, Left-bottom, Middle, Right-top, Right-bottom.

Edges:

• Left-top to Left-bottom: weight 38
• Left-top to Middle: weight 21
• Left-bottom to Middle: weight 19
• Left-top to Right-top: weight 42
• Left-bottom to Right-bottom: weight 45
• Right-top to Right-bottom: weight 37

Let's trace Kruskal's algorithm for 5 vertices (needs exactly 4 edges):

1. Edge with weight 19 (Left-bottom to Middle) - Selected.
2. Edge with weight 21 (Left-top to Middle) - Selected.

• Now Left-top, Middle, Left-bottom are connected.

1. Edge with weight 37 (Right-top to Right-bottom) - Selected.
2. Edge with weight 38 (Left-top to Left-bottom) - Reject, because Left-top and Left-bottom are already connected via Middle (19 + 21).
3. Edge with weight 42 (Left-top to Right-top) - Selected.

• This connects the left component to the right component.

1. Edge with weight 45 (Left-bottom to Right-bottom) - Reject, as all 5 vertices are now connected.

Let's recalculate the selected edges:

• 19
• 21
• 37
• 42

Total weight:

$$ \text{Total Weight} = 19 + 21 + 37 + 42 = 119 $$

Answer:

• 75
• 202
• 119 (Correct answer)
• 164