Question

pictured here is the graph g.
the edges have the following weights:

• ( w(ab) = 6 )
• ( w(bc) = 7 )
• ( w(ad) = 4 )
• ( w(dg) = 13 )
• ( w(gh) = 13 )
• ( w(hi) = 10 )
• ( w(fi) = 4 )
• ( w(cf) = 4 )
• ( w(ag) = 6 )
• ( w(eg) = 1 )
• ( w(be) = 11 )
• ( w(eh) = 8 )
• ( w(bi) = 3 )
• ( w(ci) = 1 )

what is the total weight of a minimum spanning tree for this graph?

Explanation:

Step1: Identify Minimum Edges

Use Kruskal's algorithm: sort edges by weight. Edges with weight 1: \( eg \), \( ci \); weight 3: \( bi \); weight 4: \( ad \), \( fi \), \( cf \); weight 6: \( ab \), \( ag \); weight 7: \( bc \); weight 8: \( eh \); weight 10: \( hi \); weight 11: \( be \); weight 13: \( dg \), \( gh \).

Step2: Select Edges (Avoid Cycles)

- Weight 1: Add \( eg \), \( ci \) (no cycle).
- Weight 3: Add \( bi \) (no cycle).
- Weight 4: Add \( ad \), \( fi \), \( cf \) (no cycles). Now nodes: \( a,d,g,e \); \( b,i,c,f \); \( h \) (from \( ci \), \( bi \) connects \( b - i - c \), \( fi \) connects \( f - i \), \( cf \) connects \( c - f \); \( ad \) connects \( a - d \), \( ag \) connects \( a - g \), \( eg \) connects \( e - g \)).
- Weight 6: Add \( ab \) (connects \( a - b \), no cycle). Now \( a - b - i - c - f \); \( a - d - g - e \).
- Weight 8: Add \( eh \) (connects \( e - h \), no cycle). Now \( g - e - h \).
- Weight 10: Add \( hi \) (connects \( h - i \), no cycle). Now all nodes connected.

Step3: Sum Weights

Sum: \( 1(eg) + 1(ci) + 3(bi) + 4(ad) + 4(fi) + 4(cf) + 6(ab) + 8(eh) + 10(hi) \)? Wait, no—wait, let's list all selected edges:
- \( eg \): 1
- \( ci \): 1
- \( bi \): 3
- \( ad \): 4
- \( fi \): 4
- \( cf \): 4
- \( ab \): 6
- \( eh \): 8
- \( hi \): 10? Wait, no, after \( ab \) (connects \( a - b \)), \( eh \) connects \( e - h \), then \( hi \) connects \( h - i \) (already \( i \) is connected to \( b,c,f \)). Wait, maybe better to count nodes: 9 nodes (a,b,c,d,e,f,g,h,i), so 8 edges.

Correct selection (Kruskal's):
1. \( eg \) (1)
2. \( ci \) (1)
3. \( bi \) (3)
4. \( ad \) (4)
5. \( fi \) (4)
6. \( cf \) (4)
7. \( ab \) (6)
8. \( eh \) (8)
9. Wait, no—9 nodes need 8 edges. Oops, mistake. Let's redo:

Nodes: a,b,c,d,e,f,g,h,i (9 nodes → 8 edges).

Sort edges by weight:
1. \( eg \) (1) - connects e-g
2. \( ci \) (1) - connects c-i
3. \( bi \) (3) - connects b-i (now b connected to i-c)
4. \( ad \) (4) - connects a-d
5. \( fi \) (4) - connects f-i (now f connected to i-c-b)
6. \( cf \) (4) - connects c-f (already c-f via i? Wait, c-i-f, so \( cf \) is redundant? Oh right! Cycle: c-i-f-c. So don't add \( cf \). Oops, that's the error. So weight 4: add \( ad \), \( fi \) (not \( cf \) as it creates cycle c-i-f-c).

So correct steps:
1. \( eg \) (1) - e-g
2. \( ci \) (1) - c-i
3. \( bi \) (3) - b-i (b-c-i)
4. \( ad \) (4) - a-d
5. \( fi \) (4) - f-i (f-c-i-b)
6. \( ab \) (6) - a-b (a-d-g-e; a-b-i-c-f)
7. \( eh \) (8) - e-h (e-g; h connected)
8. \( hi \) (10) - h-i (h-i-b-c-f; e-h-i-b-a-d-g)

Wait, no, 8 edges:

1. \( eg \): 1
2. \( ci \): 1
3. \( bi \): 3
4. \( ad \): 4
5. \( fi \): 4
6. \( ab \): 6
7. \( eh \): 8
8. \( hi \): 10

Wait, but \( cf \) is weight 4, but adding \( cf \) would create cycle (c-i-f-c), so we skip \( cf \). Now sum: 1+1+3+4+4+6+8+10? No, that's 37. But wait, maybe another selection.

Alternative: Use Prim's algorithm (start at a node, say a).

- Node a: neighbors \( ad(4) \), \( ab(6) \), \( ag(6) \). Select \( ad(4) \).
- Nodes a,d: neighbors \( ad(4) \), \( ab(6) \), \( ag(6) \), \( dg(13) \). Select \( ag(6) \) (connects a-g).
- Nodes a,d,g: neighbors \( ag(6) \), \( ab(6) \), \( dg(13) \), \( eg(1) \). Select \( eg(1) \) (connects g-e).
- Nodes a,d,g,e: neighbors \( eg(1) \), \( ab(6) \), \( be(11) \), \( eh(8) \). Select \( eh(8) \) (connects e-h).
- Nodes a,d,g,e,h: neighbors \( eh(8) \), \( hi(10) \), \( gh(13) \). Select \( hi(10) \) (connects h-i).
- Nodes a,d,g,e,h,i: neighbors \( hi(10) \), \( bi(3) \), \( ci(1) \), \( fi(4) \), \( cf(4) \), \( bc(7) \). Select \( ci(1) \) (connects i-c).
- Nodes a,d,g,e,h,i,c: neighbors \( ci(1) \), \( bi(3) \), \( fi(4) \), \( cf(4) \), \( bc(7) \), \( ab(6) \). Select \( bi(3) \) (connects i-b).
- Nodes a,d,g,e,h,i,c,b: neighbors \( bi(3) \), \( fi(4) \), \( cf(4) \), \( ab(6) \), \( bc(7) \). Select \( ab(6) \) (connects b-a, already a is connected). Wait, no, a is connected, so select \( fi(4) \) (connects i-f).
- Now all nodes: a,d,g,e,h,i,c,b,f.

Edges selected: \( ad(4) \), \( ag(6) \), \( eg(1) \), \( eh(8) \), \( hi(10) \), \( ci(1) \), \( bi(3) \), \( fi(4) \).

Sum: 4 + 6 + 1 + 8 + 10 + 1 + 3 + 4 = 37? Wait, no: 4(ad) + 6(ag) + 1(eg) + 8(eh) + 10(hi) + 1(ci) + 3(bi) + 4(fi) = 4+6=10, +1=11, +8=19, +10=29, +1=30, +3=33, +4=37.

Wait, but earlier mistake with \( cf \). Let's check another way:

Minimum spanning tree edges (correct selection with 8 edges):

- Weight 1: \( eg \), \( ci \) (2 edges, total 2)
- Weight 3: \( bi \) (1 edge, total 5)
- Weight 4: \( ad \), \( fi \) (2 edges, total 13)
- Weight 6: \( ab \) (1 edge, total 19)
- Weight 8: \( eh \) (1 edge, total 27)
- Weight 10: \( hi \) (1 edge, total 37)

Wait, but let's count nodes:

- \( eg \): e-g
- \( ci \): c-i
- \( bi \): b-i (b-c-i)
- \( ad \): a-d
- \( fi \): f-i (f-c-i-b)
- \( ab \): a-b (a-d-g-e; a-b-c-i-f)
- \( eh \): e-h (e-g-h)
- \( hi \): h-i (h-i-b-c-f; e-h-i-b-a-d-g)

Yes, all 9 nodes connected. Sum: 1+1+3+4+4+6+8+10 = 37? Wait, no: 1+1=2, +3=5, +4=9, +4=13, +6=19, +8=27, +10=37. Wait, but where is \( ag \)? Oh, no, \( ag \) is weight 6, but we used \( ab \) (6) to connect a and b. \( ag \) is redundant if we use \( ab \). Wait, \( ad \) connects a-d, \( ag \) connects a-g, but \( eg \) connects g-e, so a-d-g-e is connected. Then \( ab \) connects a-b, which connects to b-i-c-f, and \( eh \) connects e-h, \( hi \) connects h-i. So yes, that's 8 edges.

Wait, but another correct sum: let's list all edges with their weights:

1. \( eg \): 1
2. \( ci \): 1
3. \( bi \): 3
4. \( ad \): 4
5. \( fi \): 4
6. \( ab \): 6
7. \( eh \): 8
8. \( hi \): 10

Sum: 1+1=2; 2+3=5; 5+4=9; 9+4=13; 13+6=19; 19+8=27; 27+10=37.

Wait, but I think I missed \( cf \) earlier, but \( cf \) creates a cycle (c-i-f-c), so it's not included. Alternatively, maybe \( cf \) is included and another edge excluded, but \( cf \) is weight 4, same as \( fi \), but \( fi \) connects f to i (which is connected to c), so \( cf \) is a cycle. So correct sum is 37? Wait, no, let's check again with Kruskal's:

Nodes: 9, so 8 edges.

Sort edges by weight:

1. \( eg \) (1) - add
2. \( ci \) (1) - add
3. \( bi \) (3) - add
4. \( ad \) (4) - add
5. \( fi \) (4) - add
6. \( cf \) (4) - cycle (c-i-f-c) → skip
7. \( ab \) (6) - add (connects a-b, no cycle)
8. \( ag \) (6) - cycle (a-d-g-e; a-b-i-c-f; ag connects a-g, already a is connected to g via d? No, a-d-g, so ag is a cycle (a-g-d-a)? Wait, no: a-d-g, ag would be a-a? No, a to g: a-d-g and a-g, so cycle. So skip \( ag \).
9. \( eh \) (8) - add (connects e-h, no cycle)
10. \( hi \) (10) - add (connects h-i, no cycle)
11. \( bc \) (7) - cycle (b-i-c-b) → skip
12. \( be \) (11) - cycle → skip
13. \( dg \) (13) - cycle → skip
14. \( gh \) (13) - cycle → skip

Now edges: \( eg, ci, bi, ad, fi, ab, eh, hi \) (8 edges). Sum: 1+1+3+4+4+6+8+10 = 37.

Wait, but another approach: use Prim's starting at node e.

- e: neighbors \( eg(1) \), \( eh(8) \), \( be(11) \). Select \( eg(1) \) (connects e-g).
- e,g: neighbors \( eg(1) \), \( eh(8) \), \( be(11) \), \( ag(6) \), \( dg(13) \), \( gh(13) \). Select \( ag(6) \) (connects g-a).
- e,g,a: neighbors \( eg(1) \), \( ag(6) \), \( eh(8) \), \( be(11) \), \( ad(4) \), \( dg(13) \), \( gh(13) \). Select \( ad(4) \) (connects a-d).
- e,g,a,d: neighbors \( ad(4) \), \( ag(6) \), \( eg(1) \), \( eh(8) \), \( be(11) \), \( dg(13) \), \( gh(13) \), \( ab(6) \). Select \( ab(6) \) (connects a-b).
- e,g,a,d,b: neighbors \( ab(6) \), \( be(11) \), \( bi(3) \), \( bc(7) \), \( hi(10) \), \( ci(1) \), \( fi(4) \), \( cf(4) \). Select \( bi(3) \) (connects b-i).
- e,g,a,d,b,i: neighbors \( bi(3) \), \( bc(7) \), \( hi(10) \), \( ci(1) \), \( fi(4) \), \( cf(4) \), \( eh(8) \). Select \( ci(1) \) (connects i-c).
- e,g,a,d,b,i,c: neighbors \( ci(1) \), \( fi(4) \), \( cf(4) \), \( bc(7) \), \( hi(10) \), \( eh(8) \). Select \( fi(4) \) (connects c-f).
- e,g,a,d,b,i,c,f: neighbors \( fi(4) \), \( cf(4) \), \( bc(7) \), \( hi(10) \), \( eh(8) \). Select \( eh(8) \) (connects e-h).
- e,g,a,d,b,i,c,f,h: neighbors \( eh(8) \), \( hi(10) \). Select \( hi(10) \) (connects h-i).

Edges: \( eg(1), ag(6), ad(4), ab(6), bi(3), ci(1), fi(4), eh(8), hi(10) \)? Wait, no, 9 nodes need 8 edges. Wait, e,g,a,d,b,i,c,f,h: 9 nodes? No, e,g,a,d,b,i,c,f,h,i? Wait, no, nodes are a,b,c,d,e,f,g,h,i (9). So after e,g,a,d,b,i,c,f, we need to connect h. So e,g,a,d,b,i,c,f,h: 9 nodes? No, h is 9th. So edges: \( eg(1), ag(6), ad(4), ab(6), bi(3), ci(1), fi(4), eh(8), hi(10) \) is 9 edges—no, mistake. Prim's: 9 nodes, 8 edges. So correct Prim's:

1. e - g (1)
2. g - a (6)
3. a - d (4)
4. a - b (6)
5. b - i (3)
6. i - c (1)
7. i - f (4)
8. e - h (8)
9. h - i (10) → no, 8 edges. Wait, h is connected via e-h, then h-i connects to i (already connected). So 8 edges: \( eg, ag, ad, ab, bi, ci, fi, eh \) → no, h is not connected. Wait, I'm confused. Let's use the correct edge count: 9 nodes, 8 edges. The earlier Kruskal's is correct: 8 edges, sum 37.

Answer:

37