The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
1.6k views

Let $w$ be the minimum weight among all edge weights in an undirected connected graph. Let $e$ be a specific edge of weight $w$. Which of the following is FALSE?

  1. There is a minimum spanning tree containing $e$

  2. If $e$ is not in a minimum spanning tree $T$, then in the cycle formed by adding $e$ to $T$, all edges have the same weight.

  3. Every minimum spanning tree has an edge of weight $w$

  4. $e$ is present in every minimum spanning tree

asked in Algorithms by Veteran (59.6k points) | 1.6k views

1 Answer

+19 votes
Best answer

D is the false statement.

A minimum spanning tree must have the edge with the smallest weight (In Kruskal's algorithm we start from the smallest weight edge). So, C is TRUE.

If e is not part of a minimum spanning tree, then all edges which are part of a cycle with e, must have weight $\leq e$, as otherwise we can interchange that edge with $e$ and get another minimum spanning tree of lower weight. So, B and A are also TRUE.

D is false because, suppose a cycle is there with all edges having the same minimum weight $w$. Now, any one of them can be avoided in any minimum spanning tree. 

answered by Veteran (359k points)
edited by
+4
what the difference between third and fourth statement?
+5
@ankyAS
a minor difference.
'e' is the specific edge of weight "W".
but there may be more edges of weight 'W'.
so the 4th statement is talking only about specific edge 'e'. while 3rd is about all the edges having minimum weight 'w'.
0
consider a triangle with all edge weights 1(all weights are minimum) then at least one edge will not be present in the minimum spanning tree even though it's weight is minimum.
+1
whats option b want to express i can't understand
0

@arjun sir,you mentioned 

If e is not part of a minimum spanning tree, then all edges which are part of a cycle with e, must have weight ≤ e,

The highlighted <=e should be =e,because e is the minimum edge and no edge weight can be less than that.

0
Yes but they are talking about specific edge weight e of w
0

 Sandeep Suri

any example for b part

+1
If e is not part of a minimum spanning tree, then all edges which are part of a cycle with e, must have weight ≤ e, as otherwise we can interchange that edge with e and get another minimum spanning tree of lower weight. So, B is true

 

@set2018
0

A minimum spanning tree must have the edge with the smallest weight (In Kruskal's algorithm we start from the smallest weight edge). So, C is TRUE. 
this is a nice point given by arjun sir

0
Why D) is wrong ? Please explain with a example.
0
Added that.
0
Thank you Sir
0
What does it means when we say `..minimum weight among all edge weights..`

What is the other word for a unique minimum in case if such thing comes in GATE?


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

40,903 questions
47,558 answers
146,289 comments
62,305 users