Register

GATE CSE 2024 | Set 2 | Question: 49

• edited by
2,312 views

1 Answer

1 votes
1 votes

Correct Answer:   9

As we know, for the Min-Weight Spanning Tree of given graph, we will have 6 edges as the number of vertices are 7.
We want to find all the possible number of MSTs. So, in all the MSTs, "1" weights will be included making 4 edges. 
Now, for the remaining 2 edges we have 6 choices respectively but these 6 choices will be as 3 choices for one edge and 3 choices for the other edge.

So, we will have 3C1 * 3C1 number of MSTs giving us answer as 3*3 = 9.

Note: 3 won't be included in MSTs because we always look for smallest weights.

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2.8k
views
2 answers
2 votes
Arjun asked Feb 16
2,840 views
GATE CSE 2024 | Set 2 | Question: 25
Let $\text{A}$ be an array containing integer values. The distance of $\text{A}$ is defined as the minimum number of elements in $\text{A}$ that must be replaced with ano...
User Avatar
10.0k
views
4 answers
8 votes
Arjun asked Feb 12, 2020
9,992 views
GATE CSE 2020 | Question: 49
Consider a graph $G = (V,E)$, where $V = \{v_1,v_2, \dots ,v_{100}\}$, $E = \{(v_i,v_j) \mid 1\leq i < j \leq 100\}$, and weight of the edge $(v_i,v_j)$ is $\mid i – j ...
User Avatar
2.7k
views
2 answers
3 votes
Arjun asked Feb 16
2,692 views
GATE CSE 2024 | Set 2 | Question: 24
Let $\text{P}$ be the partial order defined on the set $\{1,2,3,4\}$ as follows\[P=\{(x, x) \mid x \in\{1,2,3,4\}\} \cup\{(1,2),(3,2),(3,4)\}\]The number of total orders ...
User Avatar
2.2k
views
1 answers
4 votes
Arjun asked Feb 16
2,220 views
GATE CSE 2024 | Set 2 | Question: 43
Consider a disk with the following specifications: rotation speed of $6000$ RPM, average seek time of $5$ milliseconds, $500$ sectors/track, $512$-byte sectors. A file ha...
User Avatar
Link Copied!