Gate CS-2016-1 Question Paper With Solutions

Q. 50 G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE

I.  If e is the lightest edge of some cycle in G, 
    then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, 
    then every MST of G excludes e

(A) I only

(B) II only

(C) both I and II

(D) neither I nor II

Answer: (B)

Explanation:

Gate CS-2016-1 Question Paper With Solutions

Learn More:   Gate EE-2017-1 Question Paper With Solutions

LEAVE A REPLY

Please enter your comment!
Please enter your name here