in Algorithms edited by
12,523 views
56 votes
56 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.
in Algorithms edited by
12.5k views

5 Comments

@vaibhav it is not given in the question that all the edges have different edge weight
0
0
They haven't said anything about Distinct or same edge weight possible, so assume both case & check options for both.
1
1

Your reasoning is absolutely correct for graphs with distinct weights.

But, imagine a graph with a cycle, and all edges weighing 500. The question permits such graphs.

0
0
If MST contains max weight edge e, then e must be a bridge(it is a necessity to include e).

Moreover the cut-set will contain e, but we can now keep on adding other edges in the cut-set and it'll remain a cut-set.

So, there is a possibility that all the max value edges are present in the cut-set.

Hence, A is definitely correct.
0
0

Subscribe to GO Classes for GATE CSE 2022

9 Answers

1 vote
1 vote

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.

1 comment

@, Explain with example diagram

0
0
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.

by

2 Comments

but the heaviest edge will be part of MST if it is not part of a cycle as well.
0
0

@Arjun sir

The first statement: 

  1. There exists a cutset in G having all edges of maximum weight.

Does this mean cutset has only maximum weight edges or cut set has all the edges with maximum wieght?

Because if it is later then counter examples are possible for that.Please clear this point.

0
0
–4 votes
–4 votes
3 will be always true. There is no cycle in a minimum spanning tree ever.

3 Comments

(c) option says whether e is part of a cycle in the original graph- not in the minimum spanning tree.
0
0
not really. Consider the case when all edges in cycle are of same weight.
0
0
maximum weight can be repeated unless edge weights are unique. Options B and C are true but need not be always. A is true always.
1
1
Answer:

Related questions