Register

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

• retagged by
264 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

293
views
1 answers
3 votes
GO Classes asked Apr 30, 2023
293 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 ALWAYS o( $f(n))$. where $o$ is small-oh. $\text{S2:}$ If $f(n)<g(n)$ ... $\mathrm{S} 2$ is incorrect $\text{S1}$ is incorrect but $\mathrm{S} 2$ is correct Both are correct Both are incorrect
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 ALWAYS o( $f(n))$. where $o$ is small-oh.$\text{S2:...
User Avatar
300
views
1 answers
2 votes
GO Classes asked Apr 30, 2023
300 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 breadth-first search. Dijkstra's algorithm is an example of a greedy algorithm. ... $x$ and then $y$ into a binary search tree leaves the same tree as inserting $y$ and then $x$.
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 breadth-firs...
User Avatar
253
views
1 answers
2 votes
GO Classes asked Apr 30, 2023
253 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 complexity to find FIRST negative value of set? If values are stored in an array ... in a linked list (only head is known) and arranged in descending order then it takes $\theta(n)$ in worst case.
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 complexity to fin...
User Avatar
211
views
1 answers
1 votes
GO Classes asked Apr 30, 2023
211 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 $\text{G}$ from $s$ to $x$. A breadth-first search (BFS) is performed starting at ... edge $(u, v)$, we have $d[v]=d[u]+1$ For each cross edge $(u, v)$, we have $d[v]=d[u]+1$
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 distanc...
User Avatar
Link Copied!