edited by
20,441 views
71 votes
71 votes

Let $G$ be a weighted undirected graph and e be an edge with maximum weight in $G$. Suppose there is a minimum weight spanning tree in $G$ containing the edge $e$. Which of the following statements is always TRUE?

  1. There exists a cutset in $G$ having all edges of maximum weight.
  2. There exists a cycle in $G$ having all edges of maximum weight.
  3. Edge $e$ cannot be contained in a cycle.
  4. All edges in $G$ have the same weight.
edited by

9 Answers

2 votes
2 votes

question is asking for the case which remains always true....let we take each option:

(b)This may be the case but not for always. If edge 'e max' incident on a pendant vertex then MST must consider 'emax' bcoz thats the only way to reach at that vertex....so this rejects option (b)

(c)  'emax' can be there in cycle but not always. when it is in cycle and in MST also then all cycle edges will be of weight  'emax'.

(d)obviously false

Ans option(a): assuming explanation of (b) above, we see that if we MST considering  'emax' then it implies that, that's only the weight of edge to reach at that vertex(v). So there may be such multiple edges but will be having same weight only i.e.  'emax' . Removal of all these edges will disconnect 'v' from G which is the cutset for 'v'.

1 votes
1 votes

ALL the edges in a MST are "light edges" crossing some cut.

For e to be included in the MST, it has to be the light edge crossing the cut.

For e to be a light edge, all edges should weigh equal to e here, because e is the max weight here.

So, Option A is True.


This question can, however, easily be solved via counter examples.


PS: Note that all the edges in MST are light edges (minimum-weight edges) crossing the cut. But that doesn't mean if any edge is a light edge crossing some cut, it must be in MST.

Eg: Light edges crossing the cut = {A,B,C,D,E,F,G}

Edges included in MST = {A,B,C,D}

 

PPS: Read CLRS 3rd edition pages 625 to 630. You could solve probably every GATE MST question through those five pages.

0 votes
0 votes

 I have seen all the answers ...and truly I am not satisfied with the best answer and I also think that option A is not always correct.

So, my explanation will be for option A, as options B, C, and D  are correctly demonstrated in the above answers.

 WHAT IS THE CUT SET?

   – The Cut set of a connected graph in G is a set S of edges with the following properties:

  1.        The removal of all edges in S disconnects G.
  2.        The removal of some (but not all) edges in S does not disconnect G.

 If we consider a triangle or cycle graph with 3 vertices with all edge weights are same. Then clearly cut set will contain two edges. If we go along with option A and take all the edges-, then it is violating the “cut set” definition (point number 2) because by taking two edges already we can disconnect the graph G into two partitions.

So, I think the correct option would be for A “There exists a cutset in G having edges of maximum weight”

–3 votes
–3 votes

ans is B)

For each possible simple cycle in a connected weighted graph G with
distinct edge weights, the heaviest edge in the cycle does not belong to a MST of G. Bcz we can select a minimum weight edge from the cycle to be in MST.

Hence,If the heaviest edge belongs to MST then there exist a cycle having all edges with maximum weight.

Answer:

Related questions

25 votes
25 votes
3 answers
4
Ishrat Jahan asked Nov 3, 2014
8,923 views
What is the output printed by the following program?#include <stdio.h int f(int n, int k) { if (n == 0) return 0; else if (n % 2) return f(n/2, 2*k) + k; else return f(n/...