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.
Recent questions tagged spanningtree
+4
votes
1
answer
1
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
in
Algorithms
by
Mahendra Singh Kanya
(
397
points)

94
views
spanningtree
algorithms
graphtheory
0
votes
4
answers
2
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
in
DS
by
Parimal Paritosh
(
169
points)

103
views
binarytree
algorithms
spanningtree
binarysearchtree
+3
votes
1
answer
3
#distinct MSTs
......................................................
asked
Jan 28
in
Algorithms
by
Tuhin Dutta
Loyal
(
7.6k
points)

86
views
algorithms
mst
spanningtree
+3
votes
0
answers
4
Number of minimum spanning trees
asked
Jan 18
in
Graph Theory
by
vishal chugh
Active
(
1.6k
points)

159
views
spanningtree
graphtheory
minimumspanningtrees
+2
votes
0
answers
5
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)

94
views
primsalgorithm
spanningtree
minimumspanningtrees
greedyalgorithm
+5
votes
1
answer
6
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
in
Algorithms
by
sunil sarode
Active
(
1.1k
points)

137
views
algorithms
spanningtree
kruskalsalgorithm
primsalgorithm
+1
vote
0
answers
7
Test Series
can someone provide a detailed solution of this??
asked
Jan 1
in
Algorithms
by
Kalpataru Bose
(
317
points)

94
views
madeeasytestseries
gateforumtestseries
algorithms
graphalgorithms
spanningtree
minimumspanningtrees
+2
votes
1
answer
8
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
(
4.8k
points)

324
views
spanningtree
graphtheory
+3
votes
0
answers
9
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 ... $n^{m1}m^{n1}$ 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
(
10.3k
points)

246
views
spanningtree
algorithms
graphtheory
0
votes
1
answer
10
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)$ ... 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
(
22.7k
points)

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

111
views
algorithms
spanningtree
minimumspanningtrees
+2
votes
2
answers
12
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
(
33
points)

156
views
graphtheory
graphmatching
graphconnectivity
spanningtree
+1
vote
1
answer
13
How many Spanning Trees are possible from the graph?
asked
May 3, 2017
in
Algorithms
by
targate2018
Active
(
1.8k
points)

433
views
algorithms
spanningtree
+2
votes
2
answers
14
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
Debashish Deka
Veteran
(
56.2k
points)

461
views
spanningtree
graphtheory
0
votes
1
answer
15
testbook
asked
Feb 7, 2017
in
Theory of Computation
by
Sarvottam Patel
Active
(
1.1k
points)

87
views
spanningtree
0
votes
2
answers
16
virtualgate2015 algorithm
I think all options are wrong
asked
Jan 11, 2017
in
Algorithms
by
Purple
Active
(
3.5k
points)

170
views
virtualgate
testseries
spanningtree
minimumspanningtrees
primsalgorithm
+2
votes
1
answer
17
DAA: number of spanning Trees
I am getting 128 as answer: 8 Spanning trees in first part(LHS) * 2 choice in middle Part * 8 Spanning trees in Second part(RHS), but given answer is 256:
asked
Jan 2, 2017
in
Algorithms
by
Vijay Thakur
Boss
(
17k
points)

241
views
spanningtree
algorithms
0
votes
1
answer
18
GATE19894vii
Provide short answers to the following questions: In the graph shown in Fig.3 below, 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
(
39.7k
points)

181
views
gate1989
descriptive
graphtheory
spanningtree
+5
votes
4
answers
19
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
(
14k
points)

2.8k
views
isro2015
graphtheory
spanningtree
+1
vote
0
answers
20
ISI2012CS4
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$ is connected by an edge to vertex ... 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 fuctions.
asked
Jun 2, 2016
in
Graph Theory
by
jothee
Veteran
(
98.8k
points)

154
views
descriptive
isi2012
graphtheory
spanningtree
generatingfunctions
+2
votes
1
answer
21
ISI2014CS3b
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
(
98.8k
points)

150
views
descriptive
isi2014
algorithms
spanningtree
graphalgorithms
+2
votes
0
answers
22
CMI2015A04a
A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint timings. Course registration has been completed and the administration now knows ... audience. In this setting, the graph theoretic question to be answered is: Find a spanning tree with minimum number of edges.
asked
May 27, 2016
in
Graph Theory
by
jothee
Veteran
(
98.8k
points)

80
views
cmi2015
descriptive
graphtheory
spanningtree
+19
votes
4
answers
23
GATE201051
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 & 1 & 8 & 1 & 4 \\ 1 & 0 & 12 & ... What is the minimum possible weight of a path $P$ from vertex $1$ to vertex $2$ in this graph such that $P$ contains at most $3$ edges? $7$ $8$ $9$ $10$
asked
Apr 21, 2016
in
Algorithms
by
jothee
Veteran
(
98.8k
points)

1.9k
views
gate2010
normal
algorithms
spanningtree
+21
votes
3
answers
24
GATE201155
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 ij\mid \leq 2$. Each edge $(v_i,v_j)$ is assigned a weight $i+j$. A sample graph with $n=4$ is shown below. The length of the path from $v_5$ to $v_6$ in the MST of previous question with $n=10$ is $11$ $25$ $31$ $41$
asked
Apr 21, 2016
in
Algorithms
by
jothee
Veteran
(
98.8k
points)

1.7k
views
gate2011
algorithms
graphalgorithms
spanningtree
normal
+47
votes
5
answers
25
GATE 2016140
$G=(V, E)$ is an undirected simple graph in which each edge has a distinct weight, and $e$ is a particular edge of $G$. Which of the following statements about the minimum spanning trees $(MSTs)$ of $G$ is/are TRUE? If $e$ is the lightest edge of some cycle in $G$, ... edge of some cycle in $G$, then every MST of $G$ excludes $e$. I only. II only. Both I and II. Neither I nor II.
asked
Feb 12, 2016
in
Algorithms
by
Sandeep Singh
Loyal
(
7.7k
points)

5.1k
views
gate20161
algorithms
spanningtree
normal
+38
votes
15
answers
26
GATE 2016139
Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3, 4, 5,$ and $6$. The maximum possible weight that a minimum weight spanning tree of $G$ can have is __________
asked
Feb 12, 2016
in
Algorithms
by
Sandeep Singh
Loyal
(
7.7k
points)

6.6k
views
gate20161
algorithms
spanningtree
normal
numericalanswers
+29
votes
4
answers
27
GATE 2016114
Let $G$ be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE? $P$: Minimum spanning tree of $G$ does not change. $Q$: Shortest path between any pair of vertices does not change. $P$ only $Q$ only Neither $P$ nor $Q$ Both $P$ and $Q$
asked
Feb 12, 2016
in
Algorithms
by
Sandeep Singh
Loyal
(
7.7k
points)

4k
views
gate20161
algorithms
spanningtree
normal
0
votes
0
answers
28
Calculation of the number of spanning trees
asked
Dec 9, 2015
in
Algorithms
by
Rachit Saxena
(
11
points)

173
views
spanningtree
+12
votes
2
answers
29
TIFR2015B11
Let $K_{n}$ be the complete graph on $n$ vertices labelled $\left\{1, 2,\dots ,n\right\}$ with $m=\frac{n (n  1)}{2}$ edges. What is the number of spanning trees of $K_{n}$? $\frac{m}{n  1}$ $m^{n  1}$ $n^{n  2}$ $n^{n  1}$ None of the above.
asked
Dec 8, 2015
in
Graph Theory
by
makhdoom ghaya
Boss
(
39.7k
points)

389
views
tifr2015
graphtheory
spanningtree
+14
votes
2
answers
30
TIFR2015B2
Consider the following undirected connected graph $G$ with weights on its edges as given in the figure below. A minimum spanning tree is a spanning tree of least weight and a maximum spanning tree is one with largest weight. A second best minimum ... spanning tree here. There is unique minimum spanning tree, however there is more than one secondbest minimum spanning tree here.
asked
Dec 7, 2015
in
Algorithms
by
makhdoom ghaya
Boss
(
39.7k
points)

412
views
tifr2015
spanningtree
algorithms
graphalgorithms
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
barc result
Suggestion for IIITH exam
Placement Statistics for Computer Science
IIT Bombay Admission
ISRO 2018
Follow @csegate
Gatecse
Recent questions tagged spanningtree
Recent Blog Comments
...
link? not getting it
Declared!
got it :) thanks man
JUST VIST "important date" under barc login
34,782
questions
41,758
answers
118,940
comments
41,401
users