GATE Overflow Test Series | Algorithms | Test 2 | Question: 23

Question

Number of possible Minimum Spanning Trees for the following graph is $\_\_\_\_\_\_\_.$

Answer 1

Applying Kruskal's algorithm we will select edges $(b,c)$ and $(e,f).$ Then we'll choose $2$ from the $3$ edges with weights $7$ each  - $3$ choices. Then either $(a,b)$ or $(a,f)$ is selected to complete the MST. Thus we have $3 \times 2 = 6$ possible MSTs.

Comments

gatecse sir,

same analysis can be applied on left triangle of 9 weight each.so shouldn’t it be 6+6=12 ??

moreover the possibility u have stated in qsn is missing the one which incldes edge bf.also I’ve checked manually each 12 graphs,there is no intersection.

please reply

---

why u r applying condition on left side 9 weight ?

question is  asking about minimum spanning tree .

 

@mrinmoyh

---

yes yo are right.I was wrong.It should be 6.

---

6 will be the answer left side 3 choice and right hand side 2 choice