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
1
answer
1
Gateforum Test Series: Algorithms  Minimum Spanning Trees
asked
Jan 20
in
Algorithms
by
Prince Sindhiya
Loyal
(
6.3k
points)

47
views
gateforumtestseries
algorithms
minimumspanningtrees
0
votes
0
answers
2
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
(
13.7k
points)

42
views
selfdoubt
minimumspanningtrees
0
votes
1
answer
3
Gateforum Test Series: Algorithms  Minimum Spanning Trees
asked
Dec 23, 2018
in
Algorithms
by
Gupta731
Active
(
4.8k
points)

124
views
gateforumtestseries
algorithms
minimumspanningtrees
0
votes
1
answer
4
GAte zeal mock
I got 41 as answer please verify
asked
Dec 22, 2018
in
Graph Theory
by
Prince Sindhiya
Loyal
(
6.3k
points)

35
views
minimumspanningtrees
0
votes
0
answers
5
Zeal Test Series 2019: Algorithms  Minimum Spanning Trees
How many of following are correct statements ? (i) A graph where all edge weights are distinct can have more than one shortest path between two vertices u and v (ii)adding a number w on weight of every edge of graph ... number might change the shortest path between two vertices u and v (Assume that all edge weights of graph are distinct)
asked
Dec 21, 2018
in
Algorithms
by
Prince Sindhiya
Loyal
(
6.3k
points)

92
views
algorithms
minimumspanningtrees
zeal
zeal2019
0
votes
0
answers
6
MadeEasy Test Series: Algorithms  Minimum Spanning Trees
How to solve such type of questions ?
asked
Dec 21, 2018
in
Algorithms
by
Avijit Shaw
(
145
points)

108
views
madeeasytestseries
algorithms
minimumspanningtrees
+2
votes
2
answers
7
TIFR2019B2
How many distinct minimum weight spanning trees does the following undirected,weighted graph have ? $8$ $16$ $32$ $64$ None of the above
asked
Dec 18, 2018
in
Algorithms
by
Arjun
Veteran
(
396k
points)

186
views
tifr2019
algorithms
minimumspanningtrees
0
votes
1
answer
8
MadeEasy Test Series: Algorithms  Minimum Spanning Trees
asked
Dec 18, 2018
in
Algorithms
by
mitesh kumar
(
337
points)

110
views
madeeasytestseries
algorithms
greedyalgorithm
minimumspanningtrees
0
votes
1
answer
9
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
(
367
points)

129
views
minimumspanningtrees
0
votes
0
answers
10
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
(
34.6k
points)

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

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

119
views
algorithms
minimumspanningtrees
0
votes
0
answers
13
#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.3k
points)

20
views
minimumspanningtrees
algorithms
0
votes
0
answers
14
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
(
17k
points)

55
views
algorithms
timecomplexity
minimumspanningtrees
0
votes
1
answer
15
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
(
263
points)

119
views
minimumspanningtrees
spanningtree
graphtheory
graphalgorithms
algorithms
0
votes
2
answers
16
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
(
1.2k
points)

68
views
minimumspanningtrees
algorithms
graphalgorithms
0
votes
3
answers
17
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
(
49
points)

206
views
graphtheory
minimumspanningtrees
+2
votes
1
answer
18
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
(
111k
points)

247
views
minimumspanningtrees
algorithms
graphalgorithms
mst
0
votes
1
answer
19
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
(
917
points)

89
views
algorithms
graphtheory
minimumspanningtrees
0
votes
0
answers
20
#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.7k
points)

80
views
graphtheory
algorithms
graphalgorithms
minimumspanningtrees
+1
vote
1
answer
21
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
Junior
(
507
points)

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

193
views
minimumspanningtrees
graphalgorithms
+1
vote
0
answers
23
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.7k
points)

203
views
minimumspanningtrees
algorithms
mst
graphalgorithms
+15
votes
6
answers
24
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.2k
points)

3.9k
views
gate2018
algorithms
graphalgorithms
minimumspanningtrees
numericalanswers
+2
votes
3
answers
25
Ace Test Series: Graph Theory  Number Of Spanning Trees
How to approach such questions ? Please provide detailed solution. Answer given is option C
asked
Feb 2, 2018
in
Graph Theory
by
kapilbk1996
(
469
points)

728
views
minimumspanningtrees
graphalgorithms
acetestseries
+1
vote
0
answers
26
MadeEasy CBT Test 2018: Algorithms  Minimum Spanning Trees
Consider a graph G with positive and distinct edge weights : $1)$ The highest weight edge will never be included in any MST : false if its in cut set $2)$ There will be different MST but with equal weights : False again because applying any algorithm either prim or kruskal it will give same MST G'. Please comment on my understanding.
asked
Jan 23, 2018
in
Algorithms
by
Inspiron
Active
(
1.5k
points)

44
views
algorithms
minimumspanningtrees
madeeasytestseries
+5
votes
2
answers
27
Number of minimum spanning trees
asked
Jan 18, 2018
in
Graph Theory
by
vishal chugh
Active
(
1.8k
points)

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

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

94
views
minimumspanningtrees
graphalgorithms
Page:
1
2
3
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
IIT Madras Interview Experience
IIT Kanpur Interview Experience
IIIT Hderabad Interview Experience
IIT Delhi Interview Experience
IIT Hyderabad Interview Experience
Follow @csegate
Recent questions tagged minimumspanningtrees
Recent Blog Comments
10000 to <2000 is really kind of achievement , my...
THey removed it this year... I did not check it,...
even though i am not going for iiit , can you...
I don't think IIITD requires any codechef...
Will apply for IIITB. IIIT D requires a codechef...
50,132
questions
53,252
answers
184,792
comments
70,509
users