menu
search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

TIFR2015-B-2

26 votes
1.6k views

Consider the following undirected connected graph $G$ with weights on its edges as given in the figure below. A minimum spanning tree is a spanning tree of least weight and a maximum spanning tree is one with largest weight. A second best minimum spanning tree whose weight is the smallest among all spanning trees that are not minimum spanning trees in $G$.

Which of the following statements is TRUE in the above graph? (Note that all the edge weights are distinct in the above graph)

  1. There is more than one minimum spanning tree and similarly, there is more than one maximum spanning tree here.
  2. There is a unique minimum spanning tree, however there is more than one maximum spanning tree here.
  3. There is more than one minimum spanning tree, however there is a unique maximum spanning tree here.
  4. There is more than one minimum spanning tree and similarly, there is more than one second-best minimum spanning tree here.
  5. There is unique minimum spanning tree, however there is more than one second-best minimum spanning tree here.
in Algorithms
edited by 1.6k views
0
option e ?
0

I think Algorithms tag should be added in this question. 

8

To see that the second-best minimum spanning tree need not be unique, here is a weighted, undirected graph with a $unique\ MST$ of weight 7 and $two\ second-best\ MST's$ of weight 8:

$Ans: E$

2 Answers

26 votes
 
Best answer

In the graph we have all edge weights are distinct so we will get unique minimum and maximum spanning tree.
Each Cycle must exclude maximum weight edge in minimum spanning tree.
Here, we have two cycle of $3$ edges, $a-d-e$ and $c-g-k.$
For second best minimum spanning tree, exclude $a-e$ edge and include $d-e$ edge

Other way for second best minimum spanning tree: exclude $c-g$ edge and include $g-k$ edge.

So, e should be the answer.


edited by
3
nice ans
0
nice explanation papesh
5 votes
Since, all the edge weights are distinct, we have a unique minimum weight spanning tree and maximum weight spanning tree.
And we can have more than one second best minimum spanning tree because different combinations of edge may give second largest value.

You can also try finding MinST and MaxST from the given graph.

Hence, option 'e' is only possible.
0

And we can have more than one second best minimum spanning tree because different combinations of edge may give second largest value.

Can u give some examples

the second minimum spanning tree wil contain the value +1 of the minimum spanning tree choosen
 

0
second best minimum spanning tree is that whose weight is smallest among all spanning tree that are not minimum spanning trees in G it means to have second largest value we can get many combination of edges here so it will not be unique
0
just refer papesh answer
← Prev. Next →
← Prev. Qn. in Sub. Next Qn. in Sub. →
Answer:

Related questions

17 votes
2 answers
1
1.2k views
TIFR2015-B-11
Let $K_{n}$ be the complete graph on $n$ vertices labeled $\left\{1, 2,\dots ,n\right\}$ with $m=\frac{n (n - 1)}{2}$ edges. What is the number of spanning trees of $K_{n}$? $\frac{m}{n - 1}$ $m^{n - 1}$ $n^{n - 2}$ $n^{n - 1}$ None of the above.
Let $K_{n}$ be the complete graph on $n$ vertices labeled $\left\{1, 2,\dots ,n\right\}$ with $m=\frac{n (n - 1)}{2}$ edges. What is the number of spanning trees of $K_{n}$? $\frac{m}{n - 1}$ $m^{n - 1}$ $n^{n - 2}$ $n^{n - 1}$ None of the above.
asked Dec 8, 2015 in Graph Theory makhdoom ghaya 1.2k views
22 votes
3 answers
2
1.3k views
TIFR2015-B-1
Consider the following recurrence relation: $T(n) = \begin{cases} 2T (\lfloor\sqrt{n}\rfloor)+ \log n & \text{if }n \geq 2 \\ 1& \text{if }n = 1 \end{cases}$ Which of the following statements is TRUE? $T(n)$ is $O(\log n)$. $T(n)$ is $O(\log n. \log \log n)$ ... $O(\log^{3/2} n)$. $T(n)$ is $O(\log^{2} n. \log \log n)$ but not $O(\log^{2} n)$.
Consider the following recurrence relation: $T(n) = \begin{cases} 2T (\lfloor\sqrt{n}\rfloor)+ \log n & \text{if }n \geq 2 \\ 1& \text{if }n = 1 \end{cases}$ Which of the following statements is TRUE? $T(n)$ is $O(\log n)$. $T(n)$ is $O(\log n. \log \log n)$ but not $O(\log n)$. $T(n)$ is ... $O(\log^{2} n)$ but not $O(\log^{3/2} n)$. $T(n)$ is $O(\log^{2} n. \log \log n)$ but not $O(\log^{2} n)$.
asked Dec 5, 2015 in Algorithms makhdoom ghaya 1.3k views
28 votes
4 answers
3
2.7k views
TIFR2014-B-4
Consider the following undirected graph with some edge costs missing. Suppose the wavy edges form a Minimum Cost Spanning Tree for $G$. Then, which of the following inequalities NEED NOT hold? cost$(a, b) \geq 6$. cost$(b, e) \geq 5$. cost$(e, f) \geq 5$. cost$(a, d) \geq 4$. cost$(b, c) \geq 4$.
Consider the following undirected graph with some edge costs missing. Suppose the wavy edges form a Minimum Cost Spanning Tree for $G$. Then, which of the following inequalities NEED NOT hold? cost$(a, b) \geq 6$. cost$(b, e) \geq 5$. cost$(e, f) \geq 5$. cost$(a, d) \geq 4$. cost$(b, c) \geq 4$.
asked Nov 19, 2015 in Algorithms makhdoom ghaya 2.7k views
13 votes
3 answers
4
1.1k views
TIFR2011-B-35
Let $G$ be a connected simple graph (no self-loops or parallel edges) on $n\geq 3$ vertices, with distinct edge weights. Let $e_{1}, e_{2},...,e_{m}$ be an ordering of the edges in decreasing order of weight. Which of the following statements ... weight spanning tree. The edge $e_{m}$ is never present in any maximum weight spanning tree. $G$ has a unique maximum weight spanning tree.
Let $G$ be a connected simple graph (no self-loops or parallel edges) on $n\geq 3$ vertices, with distinct edge weights. Let $e_{1}, e_{2},...,e_{m}$ be an ordering of the edges in decreasing order of weight. Which of the following statements is FALSE? ... weight spanning tree. The edge $e_{m}$ is never present in any maximum weight spanning tree. $G$ has a unique maximum weight spanning tree.
asked Oct 24, 2015 in Algorithms makhdoom ghaya 1.1k views
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...