Open In App

GATE | GATE IT 2006 | Question 11

Like Article
Like
Save
Share
Report

If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a

 
(A) Hamiltonian cycle
(B) grid
(C) hypercube
(D) tree


Answer: (D)

Explanation:  

As here we want subset of edges that connects all the vertices and has minimum total weight i.e. Minimum Spanning Tree
Option A – includes cycle, so may or may not connect all edges.
Option B – has no relevance to this question.
Option C – includes cycle, so may or may not connect all edges.

Related:
https://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/
https://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/

This solution is contributed by Mohit Gupta.

 

Quiz of this Question


Last Updated : 28 Jun, 2021
Like Article
Save Article
Previous
Next
Share your thoughts in the comments
Similar Reads