0

Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and emin the edge with minimum weight. Which of the following statements is false?
A) Every minimum spanning tree of G must contain emin
B) If emax is in a minimum spanning tree, then its removal must disconnect G
C) No minimum spanning tree contains emax
D) G has a unique minimum spanning tree

0

As minimum spanning tree contains emax and removal of emax might disconnect the graph G. Thus the option [C] is the false option.

0

It's answer should be c. Because this graph is connected and distinct edge so that G has a unique MST and every MST contain emin edge because emin edge have minimum cost So option A and D are true Now for option B we can make a graph in which we have to take a maximum cost edge in MST for eg. Edge with cost (a,b)=1, (b,c)=2, (c,a)=3, and (a,d)=4 if we construct this graph than we have to take a,d edge in MST bcz we don't have choice so this edge removal must disconnect graph so option B also true But option C is false bcz from above eg. We can construct a MST which contains emax edge .

0

I think c option is correct .Think of the case in which you have to find MST of tree whose all edges have same weight.

0

Think of the case when you have to find MST of a tree with all edges of same weight. Ans is c

0

Option C is false , rest all options are true

0

Option c is false , rest options are true

0

A) This is true, because all weights are distinct, so emin will be chosen first (Kruskal's algorithm). B) This is true, because if emax is in min spanning tree, then it definitely must not be part of any cycle in G. Hence it will be a bridge. Removing it will disconnect the graph. C) This statement is false as we see in option B that if emax is a bridge then will have to be included. D) This is true because weights are distinct and hence we will select weights in increasing order excluding the ones that forms cycle (Kruskal's algo). Option C must be the ans.

© 2020 - All rights are reserved- AAIC Technologies pvt ltd