Recent questions tagged spanning-tree / GATE Overflow for GATE CSE

71 votes

9 answers

61

GATE IT 2005 | Question: 52
Let $G$ be a weighted undirected graph and e be an edge with maximum weight in $G$. Suppose there is a minimum weight spanning tree in $G$ containing the edge $e$. Which of the following statements is always TRUE? There exists a cutset in $G$ having ... $e$ cannot be contained in a cycle. All edges in $G$ have the same weight.

Let $G$ be a weighted undirected graph and e be an edge with maximum weight in $G$. Suppose there is a minimum weight spanning tree in $G$ containing the edge $e$. Which ...

Ishrat Jahan

20.7k views

Ishrat Jahan asked Nov 3, 2014

30 votes

5 answers

62

GATE IT 2008 | Question: 45
For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Spanning Tree? $\text{(a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)}$ ... $\text{(h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)}$

For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Span...

Ishrat Jahan

13.4k views

Ishrat Jahan asked Oct 28, 2014

26 votes

1 answer

63

GATE CSE 1996 | Question: 16
A complete, undirected, weighted graph $G$ is given on the vertex $\{0, 1,\dots, n -1\}$ for any fixed ‘n’. Draw the minimum spanning tree of $G$ if the weight of the edge $(u, v)$ is $\mid u-v\mid$ the weight of the edge $(u, v)$ is $u + v$

A complete, undirected, weighted graph $G$ is given on the vertex $\{0, 1,\dots, n -1\}$ for any fixed ‘n’. Draw the minimum spanning tree of $G$ ifthe weight of the ...

Kathleen

5.2k views

Kathleen asked Oct 9, 2014

16 votes

1 answer

64

GATE CSE 1995 | Question: 22
How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to edges).

How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to edges).

Kathleen

5.1k views

Kathleen asked Oct 8, 2014

43 votes

8 answers

65

GATE CSE 2010 | Question: 50
Consider a complete undirected graph with vertex set $\{0, 1, 2, 3, 4\}$. Entry $W_{ij}$ in the matrix $W$ below is the weight of the edge $\{i, j\}$ ... possible weight of a spanning tree $T$ in this graph such that vertex $0$ is a leaf node in the tree $T$? $7$ $8$ $9$ $10$

Consider a complete undirected graph with vertex set $\{0, 1, 2, 3, 4\}$. Entry $W_{ij}$ in the matrix $W$ below is the weight of the edge $\{i, j\}$$$W=\begin{pmatrix} 0...

go_editor

23.9k views

go_editor asked Sep 30, 2014

33 votes

4 answers

66

GATE CSE 1997 | Question: 9
Consider a graph whose vertices are points in the plane with integer co-ordinates $(x,y)$ such that $1 \leq x \leq n$ and $1 \leq y \leq n$, where $n \geq 2$ is an integer. Two vertices $(x_1, y_1)$ ... only the answer without any explanations. What is the weight of a maximum weight-spanning tree in this graph? Write only the answer without any explanations.

Consider a graph whose vertices are points in the plane with integer co-ordinates $(x,y)$ such that $1 \leq x \leq n$ and $1 \leq y \leq n$, where $n \geq 2$ is an intege...

Kathleen

6.5k views

Kathleen asked Sep 29, 2014

52 votes

10 answers

67

GATE CSE 2011 | Question: 54
An undirected graph $G(V,E)$ contains $n \: (n>2)$ nodes named $v_1,v_2, \dots, v_n$. Two nodes $v_i, v_j$ are connected if and only if $ 0 < \mid i-j\mid \leq 2$. Each edge $(v_i,v_j)$ is assigned a weight $i+j$. A sample graph with $n=4$ is shown below. ... spanning tree (MST) of such a graph with $n$ nodes? $\frac{1}{12} (11n^2 - 5 n)$ $n^2-n+1$ $6n-11$ $2n+1$

An undirected graph $G(V,E)$ contains $n \: (n>2)$ nodes named $v_1,v_2, \dots, v_n$. Two nodes $v_i, v_j$ are connected if and only if $ 0 < \mid i-j\mid \leq 2$. Each ...

go_editor

17.2k views

go_editor asked Sep 29, 2014

47 votes

3 answers

68

GATE CSE 2014 Set 2 | Question: 52
The number of distinct minimum spanning trees for the weighted graph below is _____

The number of distinct minimum spanning trees for the weighted graph below is _____

go_editor

13.6k views

go_editor asked Sep 28, 2014

21 votes

2 answers

69

GATE CSE 2006 | Question: 47
Consider the following graph: Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm? $(a-b),(d-f),(b-f),(d-c),(d-e)$ $(a-b),(d-f),(d-c),(b-f),(d-e)$ $(d-f),(a-b),(d-c),(b-f),(d-e)$ $(d-f),(a-b),(b-f),(d-e),(d-c)$

Consider the following graph:Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm? $(a-...

Rucha Shelke

9.6k views

Rucha Shelke asked Sep 26, 2014

36 votes

2 answers

70

GATE CSE 2005 | Question: 6
An undirected graph $G$ has $n$ nodes. its adjacency matrix is given by an $n \times n$ square matrix whose (i) diagonal elements are 0's and (ii) non-diagonal elements are 1's. Which one of the following is TRUE? Graph $G$ has no minimum ... cost $n-1$ Graph $G$ has multiple distinct MSTs, each of cost $n-1$ Graph $G$ has multiple spanning trees of different costs

An undirected graph $G$ has $n$ nodes. its adjacency matrix is given by an $n \times n$ square matrix whose (i) diagonal elements are 0’s and (ii) non-diagonal elements...

Kathleen

13.9k views

Kathleen asked Sep 22, 2014

25 votes

3 answers

71

GATE CSE 2009 | Question: 38
Consider the following graph: Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm? $\text{(b, e) (e, f) (a, c) (b, c) (f, g) (c, d)}$ $\text{(b, e) (e, f) (a, c) (f, g) (b, c) (c, d)}$ $\text{(b, e) (a, c) (e, f) (b, c) (f, g) (c, d)}$ $\text{(b, e) (e, f) (b, c) (a, c) (f, g) (c, d)}$

Consider the following graph:Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?$\text{(b, e) (e, f) (...

Kathleen

9.0k views

Kathleen asked Sep 22, 2014

37 votes

3 answers

72

GATE CSE 2007 | Question: 49
Let $w$ be the minimum weight among all edge weights in an undirected connected graph. Let $e$ be a specific edge of weight $w$. Which of the following is FALSE? There is a minimum spanning tree containing $e$ If $e$ is not in a minimum ... edges have the same weight. Every minimum spanning tree has an edge of weight $w$ $e$ is present in every minimum spanning tree

Let $w$ be the minimum weight among all edge weights in an undirected connected graph. Let $e$ be a specific edge of weight $w$. Which of the following is FALSE?There is ...

Kathleen

12.0k views

Kathleen asked Sep 21, 2014

25 votes

3 answers

73

GATE CSE 2003 | Question: 68
What is the weight of a minimum spanning tree of the following graph? $29$ $31$ $38$ $41$

What is the weight of a minimum spanning tree of the following graph?$29$$31$$38$$41$

Kathleen

7.6k views

Kathleen asked Sep 17, 2014

32 votes

7 answers

74

GATE CSE 2006 | Question: 11
Consider a weighted complete graph $G$ on the vertex set $\{v_1,v_2,.....v_n\}$ such that the weight of the edge $(v_i, v_j)$ is $2|i-j|$. The weight of a minimum spanning tree of $G$ is: $n-1$ $2n-2$ $\begin{pmatrix} n \\ 2 \end{pmatrix}$ $n^2$

Consider a weighted complete graph $G$ on the vertex set $\{v_1,v_2,.....v_n\}$ such that the weight of the edge $(v_i, v_j)$ is $2|i-j|$. The weight of a minimum spanni...

Rucha Shelke

14.8k views

Rucha Shelke asked Sep 16, 2014

59 votes

5 answers

75

GATE CSE 2012 | Question: 29
Let $G$ be a weighted graph with edge weights greater than one and $G'$ be the graph constructed by squaring the weights of edges in $G$. Let $T$ and $T'$ be the minimum spanning trees of $G$ and $G'$, respectively, with total weights $t$ ... $t' < t^2$ $T' \neq T$ but total weight $t' = t^2$ None of the above

Let $G$ be a weighted graph with edge weights greater than one and $G'$ be the graph constructed by squaring the weights of edges in $G$. Let $T$ and $T'$ be the minimum ...

gatecse

16.5k views

gatecse asked Sep 15, 2014

29 votes

3 answers

76

GATE CSE 2001 | Question: 15
Consider a weighted undirected graph with vertex set $V = \{n1, n2, n3, n4, n5, n6 \}$ ... all possible minimum spanning trees of a graph? Is the maximum among the edge weights of a minimum spanning tree unique over all possible minimum spanning tree of a graph?

Consider a weighted undirected graph with vertex set $V = \{n1, n2, n3, n4, n5, n6 \}$ and edge set $E = \{(n1,n2,2), (n1,n3,8), (n1,n6,3), (n2,n4,4), (n2,n5,12), (n3,n4,...

Kathleen

4.5k views

Kathleen asked Sep 14, 2014

38 votes

5 answers

77

GATE CSE 2000 | Question: 2.18
Let $G$ be an undirected connected graph with distinct edge weights. Let $e_{max}$ be the edge with maximum weight and $e_{min}$ the edge with minimum weight. Which of the following statements is false? Every minimum spanning tree of $G$ must ... , then its removal must disconnect $G$ No minimum spanning tree contains $e_{max}$ $G$ has a unique minimum spanning tree

Let $G$ be an undirected connected graph with distinct edge weights. Let $e_{max}$ be the edge with maximum weight and $e_{min}$ the edge with minimum weight. Which of th...

Kathleen

15.6k views

Kathleen asked Sep 14, 2014

37 votes

10 answers

78

GATE CSE 1992 | Question: 01,ix
Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is _______

Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is _______

Kathleen

17.5k views

Kathleen asked Sep 12, 2014

43 votes

3 answers

79

GATE CSE 1991 | Question: 03,vi
Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph $G$ with $n$ vertices and $m$ edges has the time complexity of: $O(n^{2})$ $O(mn)$ $O(m+n)$ $O(m \log n)$ $O(m^2)$

Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph $G$ with $n$ vertices and $m$ edges has the time complexity of:$O(n^{2})$$O(mn)$$O(m+n)$$O(m...

Kathleen

13.9k views

Kathleen asked Sep 12, 2014

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true