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

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
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
DOUBT ON MINIMAL SPANNING TREE
II. if an edge (u,v) is contained in some minimum spanning tree, then it is a light edge crossing some cut of the graph. III. If (u,v) is a light edge connecting CC(connected component) to some other component in the forest of graph ... spanning tree. didn't understand the part light edge crossing some cut of the graph can someone explain me with the diagram ??
asked
Dec 28, 2018
in
Algorithms
by
Magma
Boss
(
13k
points)

35
views
selfdoubt
minimumspanningtrees
0
votes
1
answer
2
GAte zeal mock
I got 41 as answer please verify
asked
Dec 22, 2018
in
Graph Theory
by
Prince Sindhiya
Loyal
(
6.1k
points)

27
views
minimumspanningtrees
0
votes
1
answer
3
Made easy test series
What we do if graph is complete with 5 vertices and weight are 1,2,3,4,5,6,7,8,9 and 10. than find maximum possible weight that a minimum weight spanning tree of G have..???
asked
Dec 14, 2018
in
Algorithms
by
Vikas123
(
361
points)

112
views
minimumspanningtrees
0
votes
0
answers
4
Minimum spanning tree implementation in other way
Which algorithm will be implemented on the weighted graph in which the edges are uniformly distributed over the halfopen interval $[0,1)$ to construct MST so that it runs in linear time? $A)$ Kruskal's algorithm $B)$ Prim's algorithm $C)$ Both $(A)$ and $(B)$ $D)$ None of these
asked
Nov 10, 2018
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
26.9k
points)

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

140
views
algorithms
mst
minimumspanningtrees
+1
vote
1
answer
6
Spanning Tree
How to count the number of spanning tree?
asked
Nov 9, 2018
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
26.9k
points)

102
views
algorithms
minimumspanningtrees
0
votes
0
answers
7
#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, 2018
in
Algorithms
by
meghna
Active
(
2.2k
points)

18
views
minimumspanningtrees
algorithms
0
votes
0
answers
8
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, 2018
in
Algorithms
by
sushmita
Boss
(
16.6k
points)

50
views
algorithms
timecomplexity
minimumspanningtrees
0
votes
1
answer
9
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, 2018
in
Mathematical Logic
by
Nidhi Budhraja
(
213
points)

93
views
minimumspanningtrees
spanningtree
graphtheory
graphalgorithms
algorithms
0
votes
2
answers
10
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, 2018
in
Algorithms
by
pradeepchaudhary
Active
(
1k
points)

52
views
minimumspanningtrees
algorithms
graphalgorithms
0
votes
3
answers
11
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 ... connected 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, 2018
in
Algorithms
by
abhicse
(
39
points)

154
views
graphtheory
minimumspanningtrees
+2
votes
1
answer
12
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, 2018
in
Algorithms
by
srestha
Veteran
(
107k
points)

214
views
minimumspanningtrees
algorithms
graphalgorithms
mst
0
votes
1
answer
13
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, 2018
in
Algorithms
by
Durgesh Singh
Junior
(
897
points)

75
views
algorithms
graphtheory
minimumspanningtrees
0
votes
0
answers
14
#Algorithms How many cuts are possible are in a graph with n nodes?
Some say answer is 2n and someplace else it's been told 2n11. So, what's the corrent one?
asked
Apr 19, 2018
in
Algorithms
by
iarnav
Loyal
(
9.4k
points)

77
views
graphtheory
algorithms
graphalgorithms
minimumspanningtrees
+1
vote
2
answers
15
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, 2018
in
Graph Theory
by
kavikeve
(
493
points)

934
views
ugcnetnov2017ii
datastructure
minimumspanningtrees
+1
vote
2
answers
16
Minimum Spanning Tree Problem
asked
Mar 19, 2018
in
Algorithms
by
pankaj_vir
Boss
(
10k
points)

178
views
minimumspanningtrees
graphalgorithms
+1
vote
0
answers
17
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, 2018
in
Algorithms
by
Na462
Loyal
(
8.1k
points)

177
views
minimumspanningtrees
algorithms
mst
graphalgorithms
+14
votes
6
answers
18
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, 2018
in
Algorithms
by
gatecse
Boss
(
18.3k
points)

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

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

513
views
spanningtree
graphtheory
minimumspanningtrees
+1
vote
0
answers
21
Minimum Spanning tree
Kindly clarify B)
asked
Jan 15, 2018
in
Algorithms
by
Pawan Kumar 2
Active
(
4.7k
points)

67
views
minimumspanningtrees
+5
votes
0
answers
22
minimum spanning tree
asked
Jan 10, 2018
in
DS
by
Lakshman Patel RJIT
Boss
(
26.9k
points)

88
views
minimumspanningtrees
graphalgorithms
+2
votes
0
answers
23
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, 2018
in
Algorithms
by
ankit_thawal
Active
(
2.1k
points)

212
views
primsalgorithm
spanningtree
minimumspanningtrees
greedyalgorithm
+2
votes
0
answers
24
ace test series
asked
Jan 6, 2018
in
Algorithms
by
smsubham
Loyal
(
8.9k
points)

70
views
acetestseries
minimumspanningtrees
graphalgorithms
algorithms
+1
vote
0
answers
25
Test Series
can someone provide a detailed solution of this??
asked
Jan 1, 2018
in
Algorithms
by
Kalpataru Bose
(
497
points)

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

72
views
algorithms
minimumspanningtrees
+2
votes
0
answers
27
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.9k
points)

118
views
algorithms
minimumspanningtrees
mst
gate
graphalgorithms
+2
votes
1
answer
28
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
(
641
points)

220
views
algorithms
minimumspanningtrees
mst
gate
0
votes
1
answer
29
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)

51
views
graph
graphtheory
mst
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
question on digital electronics
PSU's
Decidability Slides
AAI JE IT results out! Adv no 02/2018
Graph Theory Slides for GATECSE
Follow @csegate
Gatecse
Recent questions tagged minimumspanningtrees
Recent Blog Comments
love you sir and great work Subarna and...
18th jan was the last date
anyone from west bengal plss solve above query as...
in the home page of GO, the deadline for WBSEDCL...
47,108
questions
51,358
answers
177,863
comments
66,688
users