Consider the weighted, connected, undirected graph H in the attached file: Note

ID: 3685797 • Letter: C

Question

Consider the weighted, connected, undirected graph H in the attached file:

Note that H has 9 vertices and hence the minimum spanning tree of H will have 8 edges.

If we run Kruskal’s algorithm on H

1.What is the first to eighth edge added to the minimum spanning tree (MST)?

If we run Prim’s algorithm on H starting from the vertex 9

2.What is the first to eighth edge added to the MST?

a.(1,3) b.(4,7) c.(5,3) d.(5,7) e.(6,7) f.(6,8) g.(3,9) h.(5,9) i.(7,8) j.(4,2) k.(1,2) i.(9,4) m.(4,6) n.(2,3)

3.The toal weight of the MST of H is [x]?

2 13 3 9 12 1 6 10 Figure 1: Graph H

Ans1. If we run Kruskal's algorithm on H then it will make MST like this:

First we will choose least weight edge i.e. a. (6,7) =1

Again find least edge which is either 1 or more than 1 i.e. b. (1,2)=2

Follow the same process to make MST

a. (6,7) b. (1,2) c.(4,9) d.(4,7) e.(1,3) f.(3,5) g.(2,4) h.(6,8)

Ans2. If we run Prim's algorithm then first to eight edge will be:

When starting from vertex 9

i.(9,4) b.(4,7) e.(6,7) d.(5,7) c.(5,3) a.(3,1) k.(1,2) f.(6,8)

Ans3. Total weight of te MST of H is 3+4+1+10+6+5+2+13 = 44