Register

GATE IT 2006 | Question: 11

9,141 views
38 votes
38 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

Best answer
55 votes
55 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
User Avatar
11 votes
11 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

User Avatar
5 votes
5 votes

Tree is a minimally connected Graph.

 So, Option (D) is Correct.

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

Related questions

13.7k
views
9 answers
64 votes
Ishrat Jahan asked Oct 31, 2014
13,699 views
GATE IT 2006 | Question: 25
Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ ... $\left(\frac{3}{n}\right)$
User Avatar
9.6k
views
8 answers
44 votes
go_editor asked Apr 24, 2016
9,556 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 ... $ is:$n$n + 2$2^{\frac{n}{2}}$\frac{2^{n}}{n}$
User Avatar
12.1k
views
4 answers
39 votes
gatecse asked Sep 21, 2014
12,148 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$
User Avatar
10.9k
views
3 answers
60 votes
Ishrat Jahan asked Nov 3, 2014
10,872 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$ ... $ from vertex $1$ to vertex $100$ is$4$7$23$99$
User Avatar
Link Copied!