Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged spanning-tree
3
votes
2
answers
31
Spannig trees
For a complete graph with 10 vertices, The number of spanning trees is at least_____?
For a complete graph with 10 vertices, The number of spanning trees is at least_____?
Parshu gate
2.4k
views
Parshu gate
asked
Nov 16, 2017
Graph Theory
spanning-tree
graph-theory
+
–
4
votes
0
answers
32
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 ... respectively. If anyone can state simple proof for above mentioned formula then it will great help.
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...
Chhotu
5.4k
views
Chhotu
asked
Nov 15, 2017
Graph Theory
spanning-tree
algorithms
graph-theory
+
–
1
votes
3
answers
33
UGC NET CSE | December 2008 | Part 2 | Question: 3
The total number of spanning trees that can be drawn using five labeled vertices is: 125 64 36 16
The total number of spanning trees that can be drawn using five labeled vertices is:125 64 36 16
rishu_darkshadow
3.8k
views
rishu_darkshadow
asked
Sep 25, 2017
DS
ugcnetcse-dec2008-paper2
data-structures
spanning-tree
+
–
0
votes
1
answer
34
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(V-1)/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 ?
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(V-1)/2,= E=$c.V^2$= E=$O(V^2)$...
rahul sharma 5
698
views
rahul sharma 5
asked
Sep 16, 2017
Algorithms
spanning-tree
time-complexity
+
–
1
votes
1
answer
35
[Discrete maths] Spanning trees
True/False; 1. Every tree is spanning tree.
True/False;1. Every tree is spanning tree.
rahul sharma 5
726
views
rahul sharma 5
asked
Sep 16, 2017
Graph Theory
algorithms
spanning-tree
minimum-spanning-tree
+
–
2
votes
2
answers
36
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
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 e...
Rakshit Gupta
1.3k
views
Rakshit Gupta
asked
Sep 13, 2017
Graph Theory
graph-theory
graph-matching
graph-connectivity
spanning-tree
+
–
1
votes
3
answers
37
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.
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 ...
dd
5.5k
views
dd
asked
Mar 19, 2017
Graph Theory
spanning-tree
graph-theory
+
–
0
votes
1
answer
38
testbook
Sarvottam Patel
459
views
Sarvottam Patel
asked
Feb 7, 2017
Theory of Computation
spanning-tree
+
–
0
votes
3
answers
39
Virtual Gate Test Series: Algorithms - Minimum Spanning Tree
I think all options are wrong
I think all options are wrong
Purple
1.1k
views
Purple
asked
Jan 11, 2017
Algorithms
algorithms
spanning-tree
minimum-spanning-tree
prims-algorithm
virtual-gate-test-series
+
–
12
votes
4
answers
40
GATE CSE 1989 | Question: 4-vii
In the graph shown above, the depth-first spanning tree edges are marked with a $’ T’$. Identify the forward, backward, and cross edges.
In the graph shown above, the depth-first spanning tree edges are marked with a $’ T’$. Identify the forward, backward, and cross edges.
makhdoom ghaya
2.7k
views
makhdoom ghaya
asked
Nov 30, 2016
Algorithms
gate1989
descriptive
algorithms
graph-algorithms
spanning-tree
depth-first-search
+
–
4
votes
1
answer
41
Spanning Trees
Consider the following adjacency matrix representation of connected graph then find the number of spanning trees are possible for the given graph $\begin{bmatrix} 0&1&1&1&0 \\ 1&0&1&1&0 \\1&1&0&0&1 \\ 1&1&0&0&1 \\0&0&1&1&0 \end{bmatrix}$
Consider the following adjacency matrix representation of connected graph then find the number of spanning trees are possible for the given graph$\begin{bmatrix} 0&1&1&1&...
Rohan Mundhey
1.3k
views
Rohan Mundhey
asked
Nov 11, 2016
Algorithms
numerical-answers
spanning-tree
graph-algorithms
+
–
1
votes
4
answers
42
UGC NET CSE | August 2016 | Part 3 | Question: 33
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$
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 – ...
makhdoom ghaya
1.8k
views
makhdoom ghaya
asked
Oct 1, 2016
DS
ugcnetcse-aug2016-paper3
data-structures
spanning-tree
+
–
2
votes
1
answer
43
#spanningtree
What is the upper bound on the number of edge disjoint spanning trees in a complete graph of n vertices. a. n b. n-1 c. n/2 d. n/3
What is the upper bound on the number of edge disjoint spanning trees in a complete graph of n vertices.a. nb. n-1c. n/2d. n/3
saurabh rai
582
views
saurabh rai
asked
Aug 27, 2016
Algorithms
algorithms
spanning-tree
+
–
1
votes
1
answer
44
Spanning trees
Find the number of spanning trees in the following graph;
Find the number of spanning trees in the following graph;
Amit puri
3.0k
views
Amit puri
asked
Aug 22, 2016
Algorithms
graph-theory
spanning-tree
+
–
0
votes
1
answer
45
Virtual Gate Test Series: Algorithms - Spanning Tree
debanjan sarkar
583
views
debanjan sarkar
asked
Jul 15, 2016
Algorithms
algorithms
spanning-tree
minimum-spanning-tree
virtual-gate-test-series
+
–
7
votes
5
answers
46
ISRO2015-41
The number of spanning trees for a complete graph with seven vertices is $2^5$ $7^5$ $3^5$ $2^{2 \times 5}$
The number of spanning trees for a complete graph with seven vertices is$2^5$$7^5$$3^5$$2^{2 \times 5}$
shivanisrivarshini
6.8k
views
shivanisrivarshini
asked
Jun 5, 2016
Algorithms
isro2015
algorithms
spanning-tree
+
–
1
votes
0
answers
47
ISI2012-PCB-CS-4
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.
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$ v...
go_editor
682
views
go_editor
asked
Jun 2, 2016
Graph Theory
descriptive
isi2012-pcb-cs
graph-theory
spanning-tree
generating-functions
+
–
1
votes
1
answer
48
ISI2014-PCB-CS-3b
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$.
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$.
go_editor
686
views
go_editor
asked
May 31, 2016
Algorithms
descriptive
isi2014-pcb-cs
algorithms
spanning-tree
graph-algorithms
+
–
2
votes
1
answer
49
CMI2015-A-04a
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 ... a spanning tree with minimum number of edges Find a minimal coloring Find a minimum size vertex cover Find a maximum size independent
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 tim...
go_editor
802
views
go_editor
asked
May 27, 2016
Graph Theory
cmi2015
descriptive
graph-theory
spanning-tree
+
–
0
votes
1
answer
50
Upper bound on the number of edge disjoint spanning trees in a complete graph of n vertices?
gshivam63
2.9k
views
gshivam63
asked
May 19, 2016
Algorithms
algorithms
spanning-tree
+
–
37
votes
5
answers
51
GATE CSE 2010 | Question: 51
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\}$ ... 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$
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...
go_editor
14.7k
views
go_editor
asked
Apr 21, 2016
Algorithms
gatecse-2010
normal
algorithms
spanning-tree
+
–
40
votes
6
answers
52
GATE CSE 2011 | Question: 55
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 i-j\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$
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 i-j\mid \leq 2$. Each ...
go_editor
11.6k
views
go_editor
asked
Apr 21, 2016
Algorithms
gatecse-2011
algorithms
graph-algorithms
spanning-tree
normal
+
–
117
votes
6
answers
53
GATE CSE 2016 Set 1 | Question: 40
$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 ... some cycle in $G$, then every MST of $G$ excludes $e$. I only. II only. Both I and II. Neither I nor II.
$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 minimu...
Sandeep Singh
26.0k
views
Sandeep Singh
asked
Feb 12, 2016
Algorithms
gatecse-2016-set1
algorithms
spanning-tree
normal
+
–
85
votes
18
answers
54
GATE CSE 2016 Set 1 | Question: 39
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 __________
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 s...
Sandeep Singh
35.1k
views
Sandeep Singh
asked
Feb 12, 2016
Algorithms
gatecse-2016-set1
algorithms
spanning-tree
normal
numerical-answers
+
–
62
votes
8
answers
55
GATE CSE 2016 Set 1 | Question: 14
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$
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 sta...
Sandeep Singh
22.4k
views
Sandeep Singh
asked
Feb 12, 2016
Algorithms
gatecse-2016-set1
algorithms
spanning-tree
normal
+
–
0
votes
0
answers
56
Calculation of the number of spanning trees
Hi,I just encountered problems about calculation of the number of spanning trees,like this one: https://gateoverflow.in/10154/find-out-the-no-of-spanning-tree-possible I am able to proceed to choose the number of edges.But I am ... calculation of large determinants for such problem,which is not feasible.Are you aware of any other method to do the same?
Hi,I just encountered problems about calculation of the number of spanning trees,like this one:https://gateoverflow.in/10154/find-out-the-no-of-spanning-tree-possibleI am...
Rachit Saxena
566
views
Rachit Saxena
asked
Dec 9, 2015
Algorithms
spanning-tree
+
–
11
votes
3
answers
57
find out the no. of spanning tree possible
How many spanning trees are possible from the graph given below? $24$ $34$ $44$ $54$
How many spanning trees are possible from the graph given below?$24$$34$$44$$54$
Gunjan Rathore
4.7k
views
Gunjan Rathore
asked
May 2, 2015
Algorithms
spanning-tree
graph-algorithms
numerical-answers
+
–
44
votes
5
answers
58
GATE CSE 2015 Set 3 | Question: 40
Let $G$ be a connected undirected graph of $100$ vertices and $300$ edges. The weight of a minimum spanning tree of $G$ is $500$. When the weight of each edge of $G$ is increased by five, the weight of a minimum spanning tree becomes ______.
Let $G$ be a connected undirected graph of $100$ vertices and $300$ edges. The weight of a minimum spanning tree of $G$ is $500$. When the weight of each edge of $G$ is i...
go_editor
10.7k
views
go_editor
asked
Feb 15, 2015
Algorithms
gatecse-2015-set3
algorithms
spanning-tree
easy
numerical-answers
+
–
70
votes
5
answers
59
GATE CSE 2015 Set 1 | Question: 43
The graph shown below has $8$ edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight $36$ and contains the edges: $\{(A, C), (B, C), (B, E), (E, F), (D, F)\}$. The edge weights of only ... which are in the MST are given in the figure shown below. The minimum possible sum of weights of all $8$ edges of this graph is_______________.
The graph shown below has $8$ edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight $36$ and contains the edges: $\{(A, C), (B, C), (B, E...
makhdoom ghaya
17.5k
views
makhdoom ghaya
asked
Feb 13, 2015
Algorithms
gatecse-2015-set1
algorithms
spanning-tree
normal
numerical-answers
+
–
0
votes
3
answers
60
Minimum cost spanning tree
Please explain why the answer is a)
Please explain why the answer is a)
dhingrak
790
views
dhingrak
asked
Dec 12, 2014
Algorithms
algorithms
spanning-tree
minimum-spanning-tree
made-easy-test-series
+
–
Page:
« prev
1
2
3
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register