search
Log In

Recent questions tagged minimum-spanning-trees

0 votes
0 answers
2
II. if an edge (u,v) is contained in some minimum spanning tree, then it is a light edge crossing some cut of the graph. III. If (u,v) is a light edge connecting CC(connected component) to some other component in the forest of graph G, then (u, v) ... in the minimum spanning tree. didn't understand the part light edge crossing some cut of the graph can someone explain me with the diagram ??
asked Dec 28, 2018 in Algorithms Magma 93 views
0 votes
1 answer
4
I got 41 as answer please verify
asked Dec 22, 2018 in Graph Theory Prince Sindhiya 81 views
0 votes
0 answers
5
How many of following are correct statements ? (i) A graph where all edge weights are distinct can have more than one shortest path between two vertices u and v (ii)adding a number w on weight of every edge of graph might change the graph's minimum spanning ... by a positive number might change the shortest path between two vertices u and v (Assume that all edge weights of graph are distinct)
asked Dec 21, 2018 in Algorithms Prince Sindhiya 160 views
7 votes
3 answers
7
How many distinct minimum weight spanning trees does the following undirected, weighted graph have ? $8$ $16$ $32$ $64$ None of the above
asked Dec 18, 2018 in Algorithms Arjun 788 views
0 votes
1 answer
9
What we do if graph is complete with 5 vertices and weight are 1,2,3,4,5,6,7,8,9 and 10. than find maximum possible weight that a minimum weight spanning tree of G have..???
asked Dec 14, 2018 in Algorithms Vikas123 342 views
0 votes
0 answers
10
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
11
1 vote
1 answer
12
How to count the number of spanning tree?
asked Nov 9, 2018 in Algorithms Lakshman Patel RJIT 260 views
0 votes
1 answer
13
T/F In a graph G=(V,E) suppose that each edge e ∊ E has an integer weight w(e) such that 1<= W(e) <=n Then there is a an o(mlogn) time algorithm to find a minimum spanning tree in G. Also,Does this "weight w(e) such that 1<= W(e) <=n" has significance on time complexity or we consider it as some edges weights and proceed?
asked Oct 4, 2018 in Algorithms meghna 75 views
0 votes
0 answers
14
Let $T$ be a minimum weight spanning tree of graph $G = (V, E)$, and let $V’$ be a subset of $V$ . Let $T'$ be a sub-graph of $T$ induced by $V'$ and let $G’$ be a sub-graph of $G$ induced by $V'$. Prove that If $T'$ is connected , then $T'$ is a minimum weight spanning tree of graph $G′$
asked Sep 27, 2018 in Algorithms sushmita 86 views
0 votes
2 answers
15
0 votes
3 answers
16
2) An undirected graph G has n nodes. Its adjacency matrix is given by an n n square matrix whose (i) diagonal elements are 0 s and (ii) non-diagonal elements are 1 s. which one of the following is TRUE? (a) Graph G has no minimum spanning tree (MST) (b) ... of cost n-1 (c) Graph G has multiple distinct MSTs, each of cost n-1 (d) Graph G has multiple spanning trees of different costs Expain?
asked Jul 23, 2018 in Algorithms pradeepchaudhary 120 views
1 vote
4 answers
17
Q. State whether the following statements are FALSE. (a). if $e$ is the minimum edge weight in a connected weighted graph,it must be among the edges of at least one minimum spanning tree of the graph. (b). if $e$ is the minimum edge weight in a connected weighted graph,it must be among the edges of each one minimum spanning tree of the graph. which one is correct above two option?
asked May 24, 2018 in Algorithms abhicse 427 views
3 votes
1 answer
18
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 670 views
0 votes
1 answer
19
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?
asked Apr 29, 2018 in Algorithms Durgesh Singh 160 views
1 vote
1 answer
21
5. Consider the graph given below : Use Kruskal’s algorithm to find a minimal spanning tree for the graph. The List of the edges of the tree in the order in which they are choosen is ? (1) AD, AE, AG, GC, GB, BF (2) GC, GB, BF, GA, AD, AE (3) GC, AD, GB, GA, BF, AE (4) AD, AG, GC, AE, GB, BF
asked Mar 29, 2018 in Graph Theory kavikeve 1.8k views
1 vote
2 answers
22
1 vote
0 answers
23
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 289 views
23 votes
7 answers
24
Consider the following undirected graph $G$: Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $G$ for this value of $x$ is ____.
asked Feb 14, 2018 in Algorithms gatecse 6.4k views
2 votes
3 answers
25
1 vote
1 answer
26
Consider a graph G with positive and distinct edge weights : $1)$ The highest weight edge will never be included in any MST : false if its in cut set $2)$ There will be different MST but with equal weights : False again because applying any algorithm either prim or kruskal it will give same MST G'. Please comment on my understanding.
asked Jan 23, 2018 in Algorithms Inspiron 93 views
1 vote
0 answers
28
5 votes
0 answers
29
2 votes
0 answers
30
Consider the following graph and Assume node ‘P’ as the starting vertex for Prim’s algorithm. Which of the following can be the correct order of edges to which they are added to construct Minimum Spanning Tree (MST)? P-Q, Q-R, R-W, R-S, V-X, V-U, W-V, S-T P-Q, Q-R, R-W, W-V, V-X, V-U, R-S, S-T P-Q, P-X, X-V, V-U, U-R, R-S, R-W, S-T P-Q, P-X, X-V, V-U, U-R, R-W, R-S, S-T PLEASE EXPLAIN.
asked Jan 8, 2018 in Algorithms ankit_thawal 362 views
...