# Recent questions tagged mst

1 vote
1
Let G be a complete undirected graph on 5 vertices 10 edges, with weights being 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Let X be the value of the maximum possible weight a MST of G can have. Then the value of x will be_____ the answer to this question is given as 11 but there is no procedure given . Please ,can anyone help me out in understanding the procedure
2
3
A Spanning tree T(V,E) has bottleneck edge, means all edges present in T with the greatest cost would be bottleneck edges. Now they have said, A spanning tree T of G is a minimum bottleneck spanning tree if no spanning tree T' existed with cheaper bottleneck edge- I ... S1 I think if in (A) it was minimum bottleneck spanning tree, then (B) would not have been possible to produce. Please guide.
4
Let us assume that $G$($V$, $E$) is a weighted complete graph such that weight of the edge <$V_K$,$V_L$>=2|$K$-$L$|. The weight MST of $G$ with 100 vertices is ____________________.
5
Which algorithm will be implemented on the weighted graph in which the edges are uniformly distributed over the half-open interval $[0,1)$ to construct MST so that it runs in linear time? $A)$ Kruskal's algorithm $B)$ Prim's algorithm $C)$ Both $(A)$ and $(B)$ $D)$ None of these
6
How many numbers of spanning tree are possible?
1 vote
7
Complexity of Kruskal's algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are unsorted is _______ ______________________________________________________________________________ If elements are sorted we do with Union Find algo with inverse of ... $log^{*}V$ Now from here can we derive it for unsorted edges? for ref: here
–1 vote
8
9
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
10
Question 1) The shortest-path tree computed by Dijkstra's algorithm is necessarily an MST? Question2 ) Prim's algorithm works with negative weighted edges?
11
What important point we keep in mind while finding the #(number) of spanning tree ?? from the given graph
12
In a connected weighted graph with n vertices, all the edges have same positive integer weights. Then, the maximum number of minimum weight spanning trees in the graph is? My take - If it's a cyclic graph and just with one cycle in G then we will get, MST = no of nodes in G ... more than one cycle (and it's not a complete Graph) then you get more than n MST's where n is the number of nodes in G.
13
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.
14
Original question - https://gateoverflow.in/204122/gate2018-47 Consider the following undirected graph G: Choose a value for x that will minimize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is ____ The variance in this ... . So, if it would be what would be minimum value of x for which we get minimum MST's then x=1 would be correct.
15
Link to actual Question - https://gateoverflow.in/3355/gate2008-it-45?show=214096#c214096 For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Span­ning Tree? B) (c, e), (c, f), (f, d ... (c,e) = 7 is chosen before (c,f) which is 3 and that makes it false b/c (c,f) should be chosen first.
16
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
1 vote
17
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is decreased by the same value (constraint is - keeping all edge positive all the time), then is it TRUE or FALSE? Shortest path between any pair of vertices does not change?
18
Time Complexity of Kruskal - O(mlogm + n.O(1) + m.logn) mlogm --> for sorting edges in increasing order. n.O(1) --> n UNIONS as we've n nodes in G and each takes O(1) m.logm --> Find operation takes logn time as height of tree can never me more than logn and we have m such find operations as we have m edges in G. Now my doubt is - is it O(mlogm) or O(mlogn)? I know, given is O(mlogn), but how?
1 vote
19
Given a graph with positive and distinct edge weights. If I double or triple.. the edge weights then:- 1. Shortest path will remain same 2. Mst will remain same Right? Note : Here i am doubling or tripling or four times ..... not increasing by +c
20
......................................................
1 vote
21
can option c also be false,here in the question it is not mentioned that graph has distinct weight so if all have same weight then there may be chance that option c might be false?plsss clarify? Let w be the minimum weight among all edge weights in an undirected ... T, all edges have the same weight. Every minimum spanning tree has an edge of weight w e is present in every minimum spanning tree
22
Kindly justify with an example
23
Which of the following are correct for Minimum Spanning Tree from graph G with unique weights, with the weight function w: E→R (more than one possible) If we divide all weights by some non zero value MST will be unchanged (answer for both positive and negative ... values ) If we add or subtract all weights by some number MST will remain unchanged. (answer for both positive and negative values)
24
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
25
Multiplying all edge weights by a positive number(>1) will always change the cost of minimum spanning tree. True/False
26
Are MST and shortest path tree identical? T/F? with reasoning.
1 vote
27
First statement is False because complexity will be O(E2). I think the second statement is true? But not sure