Register

GATE IT 2006 | Question: 11

8,847 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
User Avatar

7 Answers

3 votes
3 votes

A minimum spanning tree is a spanning tree of a connected, undirected graph. It connects all the vertices together with the minimal total weighting for its edges.

answer is D

User Avatar
1 votes
1 votes

The correct answer is Tree as explained above.

Now some people may get confused regarding the correctness of this option as a tree may not necessarily connect all the vertices, which is true indeed. However, here we are not asked about the definition of tree. We are just given a scenario where we have a subset of edges that connects all the vertices and has minimum total weight. This is clearly a Minimum Spanning Tree and not any tree in general. However, an MST is still a tree (with some special properties) and so among the given options, Tree is correct. 

Sometimes questions like this are given, where none of the options are 100% correct, so we have to choose the option which is closest to being correct.

User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

43 votes
43 votes
8 answers
2
go_editor asked Apr 24, 2016
8,716 views
GATE CSE 2006 | Question: 73
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in $G$ is: $n$ $n + 2$ $2^{\frac{n}{2}}$ $\frac{2^{n}}{n}$
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding set...
User Avatar
38 votes
38 votes
4 answers
3
gatecse asked Sep 21, 2014
11,683 views
GATE CSE 2005 | Question: 11
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: $12$ $8$ less than $8$ more than $12$
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...
User Avatar
57 votes
57 votes
3 answers
4
Ishrat Jahan asked Nov 3, 2014
10,562 views
GATE IT 2005 | Question: 56
Let $G$ be a directed graph whose vertex set is the set of numbers from $1$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ iff either $j = i + 1$ or $j = 3i$. The minimum number of edges in a path in $G$ from vertex $1$ to vertex $100$ is $4$ $7$ $23$ $99$
Let $G$ be a directed graph whose vertex set is the set of numbers from $1$ to $100$. There is an edge from a vertex $i$ to a vertex $j$ iff either $j = i + 1$ or $j = 3i...
User Avatar
Link Copied!