Gate2018 cs Q38

38Consider the following undirected graph G:

Choose a value of x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is ___________.

Note – Numerical Type question

Option : A
Explanation :
ü Edges with weights 1 and 3 will be selected first,
ü Now bottom edge with weight 4 will not be selected as will cause cycle on MST,
ü both corner vertices have two-two choices to select the vertices, so these corner edges with weights 4 and 5 will resultant 2*2 = 4 MSTs.
So, total number of MSTs are 2*2 = 4, which is answer.
Option (A) is correct.

Forgot your password?

I agree with the Terms.