The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged minimumspanningtrees
0
votes
0
answers
1
Minimum spanning tree implementation in other way
asked
Nov 10
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
14.4k
points)

28
views
algorithms
graphalgorithms
minimumspanningtrees
mst
0
votes
1
answer
2
Self doubt Spanning tree
How many numbers of spanning tree are possible?
asked
Nov 9
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
14.4k
points)

78
views
algorithms
mst
minimumspanningtrees
0
votes
1
answer
3
Spanning Tree
How to count the number of spanning tree?
asked
Nov 9
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
14.4k
points)

51
views
algorithms
minimumspanningtrees
0
votes
0
answers
4
#self doubt #minimum spanning tree
T/F In a graph G=(V,E) suppose that each edge e ∊ E has an integer weight w(e) such that 1<= W(e) <=n Then there is a an o(mlogn) time algorithm to ﬁnd a minimum spanning tree in G. Also,Does this "weight w(e) such that 1<= W(e) <=n" has significance on time complexity or we consider it as some edges weights and proceed?
asked
Oct 4
in
Algorithms
by
meghna
Active
(
1.9k
points)

12
views
minimumspanningtrees
algorithms
0
votes
0
answers
5
Cormen
Let $T$ be a minimum weight spanning tree of graph $G = (V, E)$, and let $V’$ be a subset of $V$ . Let $T'$ be a subgraph of $T$ induced by $V'$ and let $G’$ be a subgraph of $G$ induced by $V'$. Prove that If $T'$ is connected , then $T'$ is a minimum weight spanning tree of graph $G′$
asked
Sep 27
in
Algorithms
by
sushmita
Boss
(
15k
points)

40
views
algorithms
timecomplexity
minimumspanningtrees
0
votes
1
answer
6
GATE Minimum Spanning Trees
Q1) Why is the path between a pair of vertices in a minimum Spanning tree of an undirected graph not the shortest( minimum weight) path?
asked
Aug 31
in
Mathematical Logic
by
Nidhi Budhraja
(
159
points)

58
views
minimumspanningtrees
spanningtree
graphtheory
graphalgorithms
algorithms
0
votes
2
answers
7
Spanning Tree
2) An undirected graph G has n nodes. Its adjacency matrix is given by an n n square matrix whose (i) diagonal elements are 0 s and (ii) nondiagonal elements are 1 s. which one of the following is TRUE? (a) Graph G has no minimum spanning tree (MST) ... n1 (c) Graph G has multiple distinct MSTs, each of cost n1 (d) Graph G has multiple spanning trees of different costs Expain?
asked
Jul 23
in
Algorithms
by
pradeepchaudhary
Junior
(
749
points)

42
views
minimumspanningtrees
algorithms
graphalgorithms
0
votes
3
answers
8
madeeasy work book
Q. State whether the following statements are FALSE. (a). if $e$ is the minimum edge weight in a connected weighted graph,it must be among the edges of at least one minimum spanning tree of the graph. (b). if $e$ is the minimum edge weight in ... weighted graph,it must be among the edges of each one minimum spanning tree of the graph. which one is correct above two option?
asked
May 24
in
Algorithms
by
abhicse
(
39
points)

129
views
graphtheory
minimumspanningtrees
+2
votes
1
answer
9
Minimum Spanning Tree
1) Kruskal Algorithm 2) Prims Algorithm 3) Dijkstra Algorithm 4) Bellman Ford Algorithm 5) Floyd Warshall Algorithm Among these which one works for only i) Positive edge weight ii) Negative edge weight iii) Negative weight cycle
asked
Apr 30
in
Algorithms
by
srestha
Veteran
(
101k
points)

182
views
minimumspanningtrees
algorithms
graphalgorithms
mst
0
votes
1
answer
10
Spanning trees
Suppose that a graph G has a minimum spanning tree already computed. How quickly can we update the minimum spanning tree if we add a new vertex and incident edges to G?
asked
Apr 29
in
Algorithms
by
Durgesh Singh
Junior
(
887
points)

62
views
algorithms
graphtheory
minimumspanningtrees
0
votes
0
answers
11
#Algorithms How many cuts are possible are in a graph with n nodes?
asked
Apr 19
in
Algorithms
by
iarnav
Loyal
(
9k
points)

73
views
graphtheory
algorithms
graphalgorithms
minimumspanningtrees
+1
vote
1
answer
12
UGC NET NOV 2017 PAPER 2 Q5
5. Consider the graph given below : Use Kruskal’s algorithm to find a minimal spanning tree for the graph. The List of the edges of the tree in the order in which they are choosen is ? (1) AD, AE, AG, GC, GB, BF (2) GC, GB, BF, GA, AD, AE (3) GC, AD, GB, GA, BF, AE (4) AD, AG, GC, AE, GB, BF
asked
Mar 29
in
Graph Theory
by
kavikeve
(
485
points)

748
views
ugcnetnov2017ii
datastructure
minimumspanningtrees
+1
vote
2
answers
13
Minimum Spanning Tree Problem
asked
Mar 19
in
Algorithms
by
pankaj_vir
Loyal
(
9.7k
points)

152
views
minimumspanningtrees
graphalgorithms
+1
vote
0
answers
14
Minimum Spanning Tree Problem
Given a graph with positive and distinct edge weights. If I double or triple.. the edge weights then: 1. Shortest path will remain same 2. Mst will remain same Right? Note : Here i am doubling or tripling or four times ..... not increasing by +c
asked
Feb 19
in
Algorithms
by
Na462
Loyal
(
6.9k
points)

155
views
minimumspanningtrees
algorithms
mst
graphalgorithms
+12
votes
6
answers
15
GATE201847
Consider the following undirected graph $G$: Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $G$ for this value of $x$ is ____.
asked
Feb 14
in
Algorithms
by
gatecse
Boss
(
18.3k
points)

2.6k
views
gate2018
algorithms
graphalgorithms
minimumspanningtrees
numericalanswers
+2
votes
3
answers
16
Spanning tree
How to approach such questions ? Please provide detailed solution. Answer given is option C
asked
Feb 2
in
Graph Theory
by
kapilbk1996
(
379
points)

460
views
minimumspanningtrees
graphalgorithms
acetestseries
+5
votes
2
answers
17
Number of minimum spanning trees
asked
Jan 18
in
Graph Theory
by
vishal chugh
Active
(
1.7k
points)

405
views
spanningtree
graphtheory
minimumspanningtrees
+1
vote
0
answers
18
Minimum Spanning tree
Kindly clarify B)
asked
Jan 15
in
Algorithms
by
Pawan Kumar 2
Active
(
4.6k
points)

64
views
minimumspanningtrees
+5
votes
0
answers
19
minimum spanning tree
asked
Jan 10
in
DS
by
Lakshman Patel RJIT
Boss
(
14.4k
points)

84
views
minimumspanningtrees
graphalgorithms
+2
votes
0
answers
20
TEST SERIES
Consider the following graph and Assume node ‘P’ as the starting vertex for Prim’s algorithm. Which of the following can be the correct order of edges to which they are added to construct Minimum Spanning Tree (MST)? PQ, QR, RW, RS, VX, VU, WV, ST PQ, QR, RW, WV, VX, VU, RS, ST PQ, PX, XV, VU, UR, RS, RW, ST PQ, PX, XV, VU, UR, RW, RS, ST PLEASE EXPLAIN.
asked
Jan 8
in
Algorithms
by
ankit_thawal
Active
(
2.1k
points)

178
views
primsalgorithm
spanningtree
minimumspanningtrees
greedyalgorithm
+2
votes
0
answers
21
ace test series
asked
Jan 6
in
Algorithms
by
smsubham
Loyal
(
8.1k
points)

68
views
acetestseries
minimumspanningtrees
graphalgorithms
algorithms
+1
vote
0
answers
22
Test Series
can someone provide a detailed solution of this??
asked
Jan 1
in
Algorithms
by
Kalpataru Bose
(
487
points)

148
views
madeeasytestseries
gateforumtestseries
algorithms
graphalgorithms
spanningtree
minimumspanningtrees
+1
vote
1
answer
23
algorithm
asked
Dec 31, 2017
in
Algorithms
by
nikkey123
Active
(
1.5k
points)

69
views
algorithms
minimumspanningtrees
+2
votes
0
answers
24
Self Doubt Minimum Spanning Tree
Which of the following are correct for Minimum Spanning Tree from graph G with unique weights, with the weight function w: E→R (more than one possible) If we divide all weights by some non zero value MST will be unchanged (answer for both ... ) If we add or subtract all weights by some number MST will remain unchanged. (answer for both positive and negative values)
asked
Dec 25, 2017
in
Algorithms
by
smsubham
Loyal
(
8.1k
points)

106
views
algorithms
minimumspanningtrees
mst
gate
graphalgorithms
+2
votes
1
answer
25
Minimum Spanning tree
If a simple undirected graph with positive weighted edges has 10 vertices and 30 edges, such that the cost of the Minimum Spanning tree is 59. Now, if all the edges weights are increased by 2, then the cost of the new MST is
asked
Dec 13, 2017
in
Algorithms
by
VIKAS TIWARI
Junior
(
579
points)

196
views
algorithms
minimumspanningtrees
mst
gate
0
votes
1
answer
26
Test Series
Are MST and shortest path tree identical? T/F? with reasoning.
asked
Dec 5, 2017
in
Algorithms
by
targate2018
Active
(
1.8k
points)

47
views
graph
graphtheory
mst
minimumspanningtrees
+1
vote
0
answers
27
NET2017
Use kruskal's algorithm to find a minimal spanning tree for the graph.the list of edges of the tree in the order in which they are chosen is ? (1)AD,AE,AG,GC,GB,BF (2)GC,GB,BF,GA,AD,AE (3)GC,AD,GB,GA,BF,AE (4)AD,AG,GC,AE,GB,BF
asked
Nov 15, 2017
in
Algorithms
by
Lavanya 2017
(
17
points)

288
views
ugcnetnov2017ii
datastructure
minimumspanningtrees
0
votes
1
answer
28
minimum spanning tree
A complete graph G with 5 nodes has positive weight edge ,each node has distinct weight with an integer value and maximum weight is equal to the number of edges in G.What can be the maximum weight of minimum spanning tree for graph G?
asked
Nov 11, 2017
in
Algorithms
by
set2018
Loyal
(
8.1k
points)

97
views
minimumspanningtrees
algorithms
0
votes
0
answers
29
ugc net November 2017
An undirected graph G(V,E) contains n(n>2) nodes named v1,v2,....vn. Two nodes vi and vj are connected if and only if o< i  j  ≤ 2. Each edge (vi, vj) is assigned a weight i+j. The cost of the minimum spanning tree of such a graph with 10 nodes is:
asked
Nov 8, 2017
in
Graph Theory
by
iarnav
Loyal
(
9k
points)

289
views
minimumspanningtrees
0
votes
0
answers
30
Spanning Tree
asked
Oct 15, 2017
in
Algorithms
by
ashwina
Active
(
2.1k
points)

50
views
algorithms
minimumspanningtrees
Page:
1
2
next »
Quick search syntax
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
Recent Posts
Basic LaTeX guide
IIT Madras Phd
Databases GO Classroom
Happy Birthday Sir Arjun
NIELIT EXAM DATE 2018
Follow @csegate
Gatecse
Recent questions tagged minimumspanningtrees
Recent Blog Comments
Sir for final year student who have exam in...
I guess you meant while chasing :) Anyway those...
I'll write a post on how to best...
@Gaurav Go through all the previous yr questions,...
42,557
questions
48,550
answers
155,295
comments
63,510
users