search
Log In

Recent questions tagged mst

1 vote
0 answers
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
asked Jan 26, 2019 in Graph Theory Nandkishor3939 170 views
0 votes
0 answers
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.
asked Nov 17, 2018 in Algorithms Ayush Upadhyaya 240 views
0 votes
0 answers
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 ____________________.
asked Nov 10, 2018 in Algorithms Naveen Kumar 3 137 views
0 votes
0 answers
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
asked Nov 10, 2018 in Algorithms Lakshman Patel RJIT 141 views
0 votes
1 answer
6
1 vote
1 answer
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
asked Jun 30, 2018 in Algorithms srestha 394 views
3 votes
1 answer
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
asked Apr 30, 2018 in Algorithms srestha 648 views
0 votes
3 answers
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?
asked Apr 29, 2018 in Algorithms iarnav 209 views
0 votes
1 answer
11
What important point we keep in mind while finding the #(number) of spanning tree ?? from the given graph
asked Apr 29, 2018 in Algorithms air1ankit 109 views
0 votes
1 answer
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.
asked Apr 28, 2018 in Algorithms iarnav 283 views
0 votes
2 answers
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.
asked Apr 28, 2018 in Algorithms iarnav 107 views
0 votes
1 answer
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.
asked Apr 28, 2018 in Algorithms iarnav 252 views
0 votes
1 answer
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.
asked Apr 25, 2018 in Algorithms iarnav 125 views
0 votes
1 answer
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
asked Apr 23, 2018 in Algorithms iarnav 146 views
1 vote
1 answer
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?
asked Apr 11, 2018 in Algorithms iarnav 273 views
0 votes
0 answers
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?
asked Apr 11, 2018 in Algorithms iarnav 123 views
1 vote
0 answers
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
asked Feb 19, 2018 in Algorithms Na462 284 views
3 votes
1 answer
20
......................................................
asked Jan 28, 2018 in Algorithms Tuhin Dutta 238 views
1 vote
0 answers
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
asked Jan 26, 2018 in Algorithms Rajeev Kumar 1 66 views
2 votes
0 answers
22
Kindly justify with an example
asked Jan 15, 2018 in Algorithms Pawan Kumar 2 95 views
2 votes
0 answers
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)
asked Dec 25, 2017 in Algorithms smsubham 162 views
2 votes
1 answer
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
asked Dec 13, 2017 in Algorithms VIKAS TIWARI 450 views
0 votes
2 answers
25
Multiplying all edge weights by a positive number(>1) will always change the cost of minimum spanning tree. True/False
asked Dec 8, 2017 in Algorithms VS 821 views
0 votes
1 answer
26
Are MST and shortest path tree identical? T/F? with reasoning.
asked Dec 5, 2017 in Algorithms targate2018 79 views
1 vote
0 answers
27
First statement is False because complexity will be O(E2). I think the second statement is true? But not sure
asked Nov 2, 2017 in Algorithms Shivam Chauhan 197 views
2 votes
1 answer
28
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.
asked Oct 29, 2017 in Algorithms junaid ahmad 146 views
1 vote
1 answer
29
Which algorithm does kruskal uses for detecting every cycle and what is the time complexity?
asked Sep 27, 2017 in Algorithms rahul sharma 5 205 views
3 votes
2 answers
30
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|)
asked Jan 16, 2017 in Algorithms srestha 151 views
...