8,718 views
37 votes
37 votes

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

  1. Hamiltonian cycle
  2. grid
  3. hypercube
  4. tree

7 Answers

Best answer
53 votes
53 votes
  1. Hamiltonian cycle $\Rightarrow$ This is a cycle. A cycle will not only connect all vertices, it will have $1$ extra edge than necessary. So I can just remove that edge & get better cost "subset of edges" which connect all vertices. So, this is FALSE.
  2. grid $\Rightarrow$ A grid graph has cycles and so this is FALSE for same reason as option A.
  3. Hypercube $\Rightarrow$ A hypercube graph also has cycles. So, this also is FALSE.
  4. Tree $\Rightarrow$ This is answer. We need to have Minimum spanning tree to be exact.
    "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 Minimum Spanning Tree". !

(D) is TRUE.

edited by
10 votes
10 votes

Target : Get a subset of edges such that weight is minimum and it connects all vertices.

Since, all weights are positive and we need a subset with minimum weight, then we should avoid cycles, coz we should have only a single path between any pair of vertices in the graph. Having a cycle will unnecessarily add up edge weight and will do no help in accomplishing the target.

This rules out all options A, B and C.

Hence, answer = option D

5 votes
5 votes

Tree is a minimally connected Graph.

 So, Option (D) is Correct.

Answer:

Related questions

43 votes
43 votes
8 answers
2
38 votes
38 votes
4 answers
3
gatecse asked Sep 21, 2014
11,534 views
Let $G$ be a simple graph with $20$ vertices and $100$ edges. The size of the minimum vertex cover of G is $8$. Then, the size of the maximum independent set of $G$ is:$1...
57 votes
57 votes
3 answers
4