Register

Recent questions tagged minimum-spanning-tree

2 votes
1 answer
122
Minimum Spanning tree
If a simple undirected graph with positive weighted edges has 10 vertices and 30 edges, such that the cost of the Minimum Spanning tree is 59. Now, if all the edges weights are increased by 2, then the cost of the new MST is
If a simple undirected graph with positive weighted edges has 10 vertices and 30 edges, such that the cost of the Minimum Spanning tree is 59. Now, if all the edges weigh...
User Avatar
9 votes
2 answers
124
TIFR CSE 2018 | Part B | Question: 3
How many distinct minimum weight spanning trees does the following undirected, weighted graph have ? $1$ $2$ $4$ $6$ $8$
How many distinct minimum weight spanning trees does the following undirected, weighted graph have ?$1$$2$$4$$6$$8$
User Avatar
0 votes
2 answers
125
Minimum Spanning Tree
Multiplying all edge weights by a positive number(>1) will always change the cost of minimum spanning tree. True/False
Multiplying all edge weights by a positive number(>1) will always change the cost of minimum spanning tree.True/False
User Avatar
0 votes
1 answer
126
Test Series
Are MST and shortest path tree identical? T/F? with reasoning.
Are MST and shortest path tree identical?T/F? with reasoning.
User Avatar
0 votes
1 answer
127
minimum spanning tree
A complete graph G with 5 nodes has positive weight edge ,each node has distinct weight with an integer value and maximum weight is equal to the number of edges in G.What can be the maximum weight of minimum spanning tree for graph G?
A complete graph G with 5 nodes has positive weight edge ,each node has distinct weight with an integer value and maximum weight is equal to the number of edges in G.What...
User Avatar
1 votes
0 answers
130
MST Kruskal
First statement is False because complexity will be O(E2). I think the second statement is true? But not sure
First statement is False because complexity will be O(E2).I think the second statement is true? But not sure
User Avatar
2 votes
1 answer
131
Kruskal
Can Anyone provide all the data structure that we can used and time complexity that we get for Kruskal algorithm of finding the minimum spanning tree.
Can Anyone provide all the data structure that we can used and time complexity that we get for Kruskal algorithm of finding the minimum spanning tree.
User Avatar
0 votes
0 answers
132
Spanning Tree
User Avatar
1 votes
1 answer
133
Algorithm kruskal algorithm MST
Which algorithm does kruskal uses for detecting every cycle and what is the time complexity?
Which algorithm does kruskal uses for detecting every cycle and what is the time complexity?
User Avatar
1 votes
1 answer
134
[Discrete maths] Spanning trees
True/False; 1. Every tree is spanning tree.
True/False;1. Every tree is spanning tree.
User Avatar
3 votes
0 answers
136
cormen
Show that a graph has a unique minimum spanning tree if, for every cut of the graphs, there is a unique line edge crossing the cut. Show that the converse is not true by giving a counter example. I'm more interested in the converse. Please explain in detail.
Show that a graph has a unique minimum spanning tree if, for every cut of the graphs, there is a unique line edge crossing the cut. Show that the converse is not true by ...
User Avatar
0 votes
1 answer
139
Minimum number of spanning tree
For finding minimum number of spanning tree using kirchoff rule we construct adjacency matrix and find cofactors. so my question is what if we have 6*6 matrix or more than that then how to solve it .
For finding minimum number of spanning tree using kirchoff rule we construct adjacency matrix and find cofactors.so my question is what if we have 6*6 matrix or more than...
User Avatar
1 votes
1 answer
140
Minimum spanning tree
In given graph G if only AC and BC belong to its minimum spanning tree, then what can be the minimum sum of weights of all edges in the graph G? A. 13 B. 14 C. 20 D. 21
In given graph G if only AC and BC belong to its minimum spanning tree, then what can be the minimum sum of weights of all edges in the graph G?A. 13B. 14C. 20D. 21
User Avatar
2 votes
0 answers
141
Minimum Spanning Tree
Show the different minimum spanning Trees Possible in each of the following Algorithms Prims Algorithm Kruskal
Show the different minimum spanning Trees Possible in each of the following AlgorithmsPrims AlgorithmKruskal
User Avatar
1 votes
1 answer
143
Graph MST
For a simple, undirected, weighted graph each edge havind distinct weight, How is it possible that there can be more than $1$ second best minimum spanning tree?
For a simple, undirected, weighted graph each edge havind distinct weight, How is it possible that there can be more than $1$ second best minimum spanning tree?
User Avatar
1 votes
2 answers
145
number of spanning trees
Find the no. of minimum cost spanning tree using Kruskal’s or Primus algorithm i am getting "4" but the answer is given "5" ...verify please
Find the no. of minimum cost spanning tree using Kruskal’s or Primus algorithmi am getting "4" but the answer is given "5" ...verify please
User Avatar
9 votes
1 answer
147
maximum weight of minimum spanning tree??
A complete graph G with 5 nodes has positive weight edges,each edge has a distinct weight with an integer value and maximum weight is equal to number of edges in G. What can be maximum weight of minimum spanning tree for graph G?
A complete graph G with 5 nodes has positive weight edges,each edge has a distinct weight with an integer value and maximum weight is equal to number of edges in G.What c...
User Avatar
4 votes
2 answers
148
MST..
Let G(V, E) be an undirected graph with positive edge weights. What is the worst case time complexity to find minimum spanning tree using Kruskal algorithm is implemented using array data structure ? a) O(|E|+|V log V|) b) O(|V| |log V|) c) O(|V2|) d) O(|V| |log2V|)
Let G(V, E) be an undirected graph with positive edge weights. What is the worst case time complexity to find minimum spanning tree using Kruskal algorithm is implemented...
User Avatar
Page: