Register

GO Classes 2024 | IIITH Mock Test 5 | Question: 13

• retagged by
297 views
1 votes
1 votes
Let $\text{G = (V, E)}$ be a connected, undirected graph with edge weights $w: \text{E} \rightarrow \mathbb{Z}$. Suppose $\text{G}$ has a unique minimum spanning tree. What can you conclude about $\text{G}?$
  1. $\text{G}$ contains no cycles
  2. $\text{G}$ contains at most one cycle
  3. All edge weights are different
  4. None of the above
• retagged by
User Avatar

1 Answer

2 votes
2 votes
We cannot conclude any of A, B, C.

$\mathrm{G}$ may have cycle and still may have unique minimum spanning tree. $\mathrm{G}$ may have any number of cycles and still may have unique minimum spanning tree. For instance, if ALL edge weights are distinct, we can only have unique MST.

If $\mathrm{G}$ does not have distinct weights then it does not imply that we have more than one minimum spanning tree.
• edited by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

322
views
1 answers
3 votes
GO Classes asked Apr 30, 2023
322 views
GO Classes 2024 | IIITH Mock Test 5 | Question: 15
Let $n$ be a positive integer.Consider the two statements below:$\text{S1:}$ If $f(n)>g(n)$ for all $n$ then $g(n)$ ... is incorrect$\text{S1}$ is incorrect but $\mathrm{S} 2$ is correctBoth are correctBoth are incorrect
User Avatar
337
views
1 answers
2 votes
GO Classes asked Apr 30, 2023
337 views
GO Classes 2024 | IIITH Mock Test 5 | Question: 23
Which of the following is/are TRUE?In the worst case, merge sort runs in $O\left(n^2\right)$ time.Depth-first search of a graph is asymptotically faster than ... a binary search tree leaves the same tree as inserting $y$ and then $x$.
User Avatar
294
views
1 answers
2 votes
GO Classes asked Apr 30, 2023
294 views
GO Classes 2024 | IIITH Mock Test 5 | Question: 31
Suppose we have a set of $n$ values. There are always at least one negative value and at least one positive value in the set.What is the worst case time ... known) and arranged in descending order then it takes $\theta(n)$ in worst case.
User Avatar
250
views
1 answers
1 votes
GO Classes asked Apr 30, 2023
250 views
GO Classes 2024 | IIITH Mock Test 5 | Question: 32
Let $\text{G = (V, E)}$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in \text{V},$ let $d(x)$ denote the shortest distance in ... $(u, v)$, we have $d[v]=d[u]+1$
User Avatar
Link Copied!