﻿ GATE CS Applied Course

## ALGORITHM

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

##### abhishek ashok fulzele Posted on Sep 13, 2019 11:47 AM

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

0

##### Anshul Kumar Posted on Sep 13, 2019 03:40 PM

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

##### Alok Tripathi Posted on Sep 14, 2019 02:16 AM

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

##### Alok Tripathi Posted on Sep 14, 2019 02:18 AM

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

0

##### Asif Khan Posted on Sep 16, 2019 10:40 AM

Option C is false , rest all options are true

0

##### Asif Khan Posted on Sep 16, 2019 10:41 AM

Option c is false , rest options are true

0

##### Apoorv Panse Posted on Sep 17, 2019 09:13 PM

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