The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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
Recent questions tagged spanningtree
+1
vote
1
answer
1
CMI2019A7
An interschool basketball tournament is being held at the Olympic sports complex. There are multiple basketball courts. Matches are scheduled in parallel, with staggered timings, to ensure that spectators always have some match or other available to watch. Each match ... solve? Find a minimal colouring. Find a minimal spanning tree. Find a minimal cut. Find a minimal vertex cover.
asked
Sep 13, 2019
in
Graph Theory
by
gatecse
Boss
(
17.5k
points)

68
views
cmi2019
graphtheory
graphcoloring
spanningtree
vertexcover
descriptive
+1
vote
1
answer
2
MadeEasy Test Series 2019: Algorithms  Spanning Tree
Consider a simple undirected weighted graph G(V, E) with 10 vertices and 45 edge, assume (u, v) are two vertices weight of a edge is =4lu vl then the minimum cost of the spanning tree of G_ 36
asked
Jan 30, 2019
in
Algorithms
by
Ram Swaroop
Loyal
(
5.4k
points)

259
views
algorithms
spanningtree
madeeasytestseries2019
madeeasytestseries
0
votes
3
answers
3
Ace test series question on number of spanning trees possible
asked
Jan 24, 2019
in
Algorithms
by
Shankar Kakde
(
195
points)

154
views
spanningtree
0
votes
2
answers
4
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
(
205
points)

190
views
minimumspanningtrees
spanningtree
graphtheory
graphalgorithms
algorithms
+1
vote
3
answers
5
Doubt
For a complete graph with 10 vertices, The number of spanning trees is at least_____?
asked
Aug 23, 2018
in
Graph Theory
by
Rishav Kumar Singh
Loyal
(
5.7k
points)

145
views
spanningtree
+1
vote
1
answer
6
Made Easy algorithms
How many edge disjoint spanning trees are possible for a undirected complete connected graph of n vertices?
asked
Aug 13, 2018
in
Algorithms
by
Sambhrant Maurya
Active
(
3.9k
points)

155
views
algorithms
spanningtree
graphtheory
+5
votes
1
answer
7
Number of spanning tress
How do we come up with this formula for number of spanning tree of a n vertex complete graph Kn= $n^{n2}$
asked
Mar 18, 2018
in
Algorithms
by
Mahendra Singh Kanya
(
379
points)

319
views
spanningtree
algorithms
graphtheory
0
votes
4
answers
8
trees
Given a preorder, postorder and inorder traversal of a tree, is it always possible to obtain a tree that satisfies each of the three conditions? Or is it possible to not obtain a tree at all?
asked
Feb 19, 2018
in
DS
by
Parimal Paritosh
(
243
points)

256
views
binarytree
algorithms
spanningtree
binarysearchtree
+3
votes
1
answer
9
#distinct MSTs
......................................................
asked
Jan 28, 2018
in
Algorithms
by
Tuhin Dutta
Boss
(
10.7k
points)

204
views
algorithms
mst
spanningtree
+6
votes
2
answers
10
Number of minimum spanning trees
asked
Jan 18, 2018
in
Graph Theory
by
vishal chugh
Active
(
1.7k
points)

808
views
spanningtree
graphtheory
minimumspanningtrees
+2
votes
0
answers
11
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
(
1.4k
points)

286
views
primsalgorithm
spanningtree
minimumspanningtrees
greedyalgorithm
+2
votes
0
answers
12
Ace Test series: Algorithms  Spanning Tree
Am getting 7. The answer given is 10. A  B , A  D , D  E , E  C are the edges i have included.
asked
Jan 6, 2018
in
Algorithms
by
smsubham
Boss
(
11.8k
points)

128
views
acetestseries
graphalgorithms
algorithms
spanningtree
minimumspanningtrees
+5
votes
1
answer
13
How many MST is possible?
Given graph using Prim’s or Kruskal’s algorithm, find out that how many distinct minimum cost spanning trees are possible___? My answer was 1 and given is 2 ,what I am missing ? Edit:I had confirmed with it and answer is only one tree possible.
asked
Jan 2, 2018
in
Algorithms
by
sunil sarode
Active
(
1.2k
points)

492
views
algorithms
spanningtree
kruskalsalgorithm
primsalgorithm
+1
vote
0
answers
14
MadeEasy Test Series: Algorithms  Spanning Tree
can someone provide a detailed solution of this??
asked
Jan 1, 2018
in
Algorithms
by
Kalpataru Bose
(
413
points)

267
views
madeeasytestseries
algorithms
graphalgorithms
spanningtree
minimumspanningtrees
greedyalgorithm
+3
votes
1
answer
15
Spannig trees
For a complete graph with 10 vertices, The number of spanning trees is at least_____?
asked
Nov 17, 2017
in
Graph Theory
by
Parshu gate
Active
(
3.1k
points)

505
views
spanningtree
graphtheory
+3
votes
0
answers
16
Number of spanning Trees
Hi, As all of us knows number of spanning tree of simple labeled graph could be computed by the Kirchhoff's theorem. But is there any other method (other than Brute force) to compute the number of spanning tree of given general graph ? Formula for number ... respectively. If anyone can state simple proof for above mentioned formula then it will great help.
asked
Nov 15, 2017
in
Graph Theory
by
Chhotu
Boss
(
13.7k
points)

1.5k
views
spanningtree
algorithms
graphtheory
0
votes
1
answer
17
UGCNETdec2008ii3
The total number of spanning trees that can be drawn using five labeled vertices is: (A) 125 (B) 64 (C) 36 (D) 16
asked
Sep 25, 2017
in
DS
by
rishu_darkshadow
Loyal
(
7.3k
points)

553
views
ugcnetdec2008ii
datastructures
spanningtree
0
votes
1
answer
18
Basic Doubt in spanning tree complexity
Let us say Simple graph has V vertices and E edges. Now i am trying to find relation between E and V. If it is a complete graph ,then E=V(V1)/2, => E=$c.V^2$ => E=$O(V^2)$ => taking log of both sides. => $\log E$=$O(\log V)$ ... .(3) Can someone confirm if the 1 ,2 and the result of them i.e the 3rd equation is valid ?
asked
Sep 16, 2017
in
Algorithms
by
rahul sharma 5
Boss
(
25.6k
points)

199
views
spanningtree
timecomplexity
+1
vote
1
answer
19
[Discrete maths] Spanning trees
True/False; 1. Every tree is spanning tree.
asked
Sep 16, 2017
in
Graph Theory
by
rahul sharma 5
Boss
(
25.6k
points)

217
views
algorithms
spanningtree
minimumspanningtrees
+2
votes
2
answers
20
Graph Theory
Consider a 'reversed Kruskal' Algorithm for computing a MST. Initialize T to be the set of all edges in the graph. Now consider edges from largest to smallest cost. For each edge, delete it from T if that edge belongs to a cycle in T. Assuming all the edge costs are distinct, does this new algorithm correctly compute a MST? a) Yes b) no c) cant say
asked
Sep 14, 2017
in
Graph Theory
by
Rakshit Gupta
(
21
points)

237
views
graphtheory
graphmatching
graphconnectivity
spanningtree
+1
vote
1
answer
21
How many Spanning Trees are possible from the graph?
How many Spanning Trees are possible from the graph given below? (a) 24 (b) 34 (c) 44 (d) 54
asked
May 3, 2017
in
Algorithms
by
targate2018
Active
(
1.8k
points)

1k
views
algorithms
spanningtree
+1
vote
2
answers
22
No of spanning Trees
Let $K_n$ denote the complete undirected graph with $n$ vertices where n is an even number. Find the maximum number of spanning trees of $K_n$ that can be formed in such a way that no two of these spanning trees have a common edge.
asked
Mar 19, 2017
in
Graph Theory
by
dd
Veteran
(
57.2k
points)

801
views
spanningtree
graphtheory
0
votes
1
answer
23
testbook
asked
Feb 7, 2017
in
Theory of Computation
by
Sarvottam Patel
Junior
(
993
points)

128
views
spanningtree
–1
vote
3
answers
24
Virtual Gate Test Series: Algorithms  Minimum Spanning Tree
I think all options are wrong
asked
Jan 11, 2017
in
Algorithms
by
Purple
Active
(
3k
points)

309
views
algorithms
spanningtree
minimumspanningtrees
primsalgorithm
virtualgatetestseries
+2
votes
2
answers
25
GATE19894vii
Provide short answers to the following questions: In the graph shown above, the depthfirst spanning tree edges are marked with a 'T'. Identify the forward, backward and cross edges.
asked
Nov 30, 2016
in
Graph Theory
by
makhdoom ghaya
Boss
(
30.8k
points)

375
views
gate1989
descriptive
graphtheory
spanningtree
dfs
+1
vote
1
answer
26
UGCNETAUG2016III33
Consider a weighted complete graph $G$ on the vertex set $\left\{ν_{1} , ν_{2},.... ν_{n} \right\}$ such that the weight of the edge $(ν_{i} , ν_{j})$ is $4  i – j$. The weight of minimum cost spanning tree of $G$ is : $4n^{2}$ $n$ $4n – 4$ $2n – 2$
asked
Oct 1, 2016
in
Others
by
makhdoom ghaya
Boss
(
30.8k
points)

333
views
ugcnetaug2016iii
datastructures
spanningtree
0
votes
0
answers
27
Virtual Gate Test Series: Algorithms  Spanning Tree
asked
Jul 15, 2016
in
Algorithms
by
debanjan sarkar
Active
(
3.8k
points)

182
views
algorithms
spanningtree
minimumspanningtrees
virtualgatetestseries
+5
votes
4
answers
28
ISRO201541
The number of spanning trees for a complete graph with seven vertices is $2^5$ $7^5$ $3^5$ $2^{2 \times 5}$
asked
Jun 5, 2016
in
Algorithms
by
shivanisrivarshini
Boss
(
13.9k
points)

3.6k
views
isro2015
graphtheory
spanningtree
+1
vote
0
answers
29
ISI2012PCBCS4
A fan of order $n$ is a graph on the vertices $\{0, 1, \dots, n\}$ with $2n − 1$ edges defined as follows: vertex $0$ is connected by an edge to each of the other $n$ vertices, and vertex $i$ ... the number of spanning trees of the fan of order $n$. Calculate $f_4$. Write a recurrence for $f_n$. Solve for fn using ordinary generating functions.
asked
Jun 2, 2016
in
Graph Theory
by
jothee
Veteran
(
105k
points)

216
views
descriptive
isi2012pcbcs
graphtheory
spanningtree
generatingfunctions
+1
vote
1
answer
30
ISI2014PCBCS3b
Let $G = (V, E)$ be an undirected weighted graph with all edge weights being positive. Design an efficient algorithm to find the maximum spanning tree of $G$.
asked
May 31, 2016
in
Algorithms
by
jothee
Veteran
(
105k
points)

229
views
descriptive
isi2014pcbcs
algorithms
spanningtree
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged spanningtree
Recent Blog Comments
Has anyone else challenged the questions on...
@nkg_master9  For getting selected for the...
Nowhere it's mentioned.
@bond  Is it mentioned that you have to score at...
I think cutoff won't cross 85
50,737
questions
57,385
answers
198,548
comments
105,363
users