Register

GO Classes DPP | GATE CS, DA | Algorithms | Minimum Spanning Trees

107 views
4 4 votes

Consider the statement:

The minimum spanning tree of a connected weighted graph $G$ is unique if and only if all edge weights in $G$ are distinct.

  1. True
     
  2. False

1 Answer

1 1 vote

It is true that:

$\text{all edge weights distinct}\Rightarrow\text{unique MST}$

But the converse is not always true.

Consider a graph that is already a tree:

The graph has equal edge weights.

However, there is only one possible spanning tree because the graph itself is already a tree.

Therefore, its MST is unique despite repeated weights.

Hence:

$\text{unique MST}\not\Rightarrow\text{distinct edge weights}$

So the "if and only if" statement is false.


Answer : B

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes GATE DA |...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

3 3 votes
1 1 answer
163
163 views
GO Classes asked Aug 24
163 views
GO Classes DPP | GATE CS, DA | Algorithms | Dijkstra's Algorithm
Consider the following code executed while processing vertex $v$:for each edge e in G.adj(v): w = e.to() if dist[w] dist[v] + e.weight(): dist[w] = dist[v] + e.weight() ...
1 1 vote
1 1 answer
134
134 views
GO Classes asked Aug 24
134 views
GO Classes DPP | GATE CS, DA | Algorithms | Divide & Conquer
Consider three recursive algorithms.Algorithm $\mathbf{1}$Divides a problem of size $N$ into two subproblems of size $N/2$ and performs constant additional work.$T_1(N)=2...
2 2 votes
1 1 answer
104
104 views
GO Classes asked Aug 24
104 views
GO Classes DPP | GATE CS, DA | Algorithms | Selection Algorithms
Let, $L=\langle r_1,r_2,\ldots,r_n\rangle$ be an arbitrary list of integers, not necessarily distinct.Which of the following statements is incorrect?There exists an optim...
2 2 votes
1 1 answer
105
105 views
GO Classes asked Aug 24
105 views
GO Classes DPP | GATE CS, DA | Algorithms | Complexity Analysis
Consider the following recursive function $\texttt{Pot}$, which computes $x^n$, where $x$ is real and $n$ is an integer.Pot(x, n): if x == 0: return 0 if n == 0: return 1...