Register

Recent questions tagged minimum-spanning-tree

0 votes
1 answer
92
Self doubt Spanning tree
How many numbers of spanning tree are possible?
How many numbers of spanning tree are possible?
User Avatar
2 votes
1 answer
93
Spanning Tree
How to count the number of spanning tree?
How to count the number of spanning tree?
User Avatar
0 votes
2 answers
96
Algorithm 19
Why 2nd statement false
Why 2nd statement false
User Avatar
0 votes
2 answers
97
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?
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?
User Avatar
1 votes
3 answers
98
Doubt
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_____?
User Avatar
2 votes
1 answer
99
Made Easy algorithms
How many edge disjoint spanning trees are possible for a undirected complete connected graph of n vertices?
How many edge disjoint spanning trees are possible for a undirected complete connected graph of n vertices?
User Avatar
1 votes
2 answers
103
Minimum spanning tree
What would be the maximum weight of minimum spanning tree of a complete connected graph with 6 vertex where each edge is of distinct +ve weights and max weight of edge is 15 1) 25 2) 26 3)27 4) none of these
What would be the maximum weight of minimum spanning tree of a complete connected graph with 6 vertex where each edge is of distinct +ve weights and max weight of edge i...
User Avatar
0 votes
1 answer
105
me wk book
let T be a minimum cost spanning tree of G. suppose that ewe decreased the weight of one of the edge in T.then to check modified T is MST or not how much tym will take??? O(1) or O(n)?????
let T be a minimum cost spanning tree of G. suppose that ewe decreased the weight of one of the edge in T.then to check modified T is MST or not how much tym will take???...
User Avatar
0 votes
1 answer
106
self doubt
Suppose that average edge weight for a graph G is Aavg. Then the minimum spanning tree of G will have weight at most (n-1) Aavg. Where n is number of vertices in graph G. i think think is false but in a solution mannul it is given as true please check it.
Suppose that average edge weight for a graph G is Aavg. Then the minimum spanning tree of G will have weight at most(n-1) Aavg. Where n is number of vertices in graph G.i...
User Avatar
4 votes
1 answer
108
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
1) Kruskal Algorithm2) Prims Algorithm3) Dijkstra Algorithm4) Bellman Ford Algorithm5) Floyd Warshall AlgorithmAmong these which one works for onlyi) Positive edge weight...
User Avatar
0 votes
3 answers
109
#Algorithms #MST Doubt in MST Questions.
Question 1) The shortest-path tree computed by Dijkstra's algorithm is necessarily an MST? Question2 ) Prim's algorithm works with negative weighted edges?
Question 1) The shortest-path tree computed by Dijkstra's algorithm is necessarily an MST?Question2 ) Prim's algorithm works with negative weighted edges?
User Avatar
0 votes
1 answer
110
SELF_DOUBT(MST)
What important point we keep in mind while finding the #(number) of spanning tree ?? from the given graph
What important point we keep in mind while finding the #(number) of spanning tree ?? from the given graph
User Avatar
0 votes
1 answer
111
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?
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?
User Avatar
0 votes
2 answers
113
#Algorithms #MST Self Doubt.
Let G be a connected simple graph with non distinct edge weights. Now, e be the lightest edge in G. So, does this edge e is present in every MST of G? My take - when all edge weights are same then lightest edge e won't be there.
Let G be a connected simple graph with non distinct edge weights. Now, e be the lightest edge in G. So, does this edge e is present in every MST of G?My take - when all e...
User Avatar
0 votes
1 answer
117
#Algorithms MST Question.
A complete, undirected, weighted graph G is given on the vertex {0,1,…,n−1} for a fixed ‘n=4’. Draw the minimum spanning tree of G if the weight of the edge (u,v) is ∣u−v∣ the weight of the edge (u,v) is u+v
A complete, undirected, weighted graph G is given on the vertex {0,1,…,n−1} for a fixed ‘n=4’. Draw the minimum spanning tree of G ifthe weight of the edge (u,v) ...
User Avatar
0 votes
1 answer
119
DAA#MST
what is cut property of minimum spanning tree .?? can somone give an example.
what is cut property of minimum spanning tree .?? can somone give an example.
User Avatar
Page: