GATE CSE 2018 | Question: 47

Question

Consider the following undirected graph $G$:

Choose a value for $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 ____.

Comments

kruskal or prime which should take?

---

We can use Kruskal algo.i.e. keep selecting min weight edges and if a cycle occurs then ignore that edge. Do this until you select $n-1$ edges.

$\therefore$ $4$ is correct.

---

Value of $x = 5$
$\therefore 4 \;\text{MWSTs}$ possible.

Answer 1

When x = 5, we get maximum 4 MWSTs

Answer 2

So if we apply kruskal'salgorithm edge weight 1 and edge weight 3 will be selected now as per question 

choose a value of x that will maximize the number of minimum weight spanning trees of G

so x=5 gives us two option to reach that particular node. any other value gives us only single option.

Number of MWSTs of G for that value of x  

so for x=5 we get 4 Minimum weight spanning tree, thus 4 is correct answer 

Answer 3

MST is "minimum wt. Spanning tree" that means only one mst is possible for every graph. But this does'nt hold for every case. If graph has repeating edge wt then more than one mst's are possible as edges with common weights provides choice to take or not to take in mst. Here, edge wt are repearing so multiple mst is possible. Now we have to make a value of x for which we can have maximum choices.

Making x=5 creates 4 choices.

2 choices for edge with wt. 4 & 2 choices for edge with wt. 5.

So 4 MST'S will be possible which is maximum.

Answer 4

Any value of x greater than 5 will eliminate x from the cycle to which x belongs to. So we will be left with only two possible MST to include edge cost:4 of the extreme left node.

Similary, any value of x less than 5, will eliminate edge cost 5. So we will be again left with only two possible MSTs to include edge cost:4 as above.

Let's take the value of x=5, so this will give us

1. Two possible MSTs to include edge cost:4 for extreme left node.

ALSO

2 Two possible MSTs to include edge cost:5 for the extreme right node.

So total possible MSTs would be 4