# Recent questions tagged minimum-spanning-trees

1
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 ??
3
4
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)
6
How to solve such type of questions ?
7
How many distinct minimum weight spanning trees does the following undirected, weighted graph have ? $8$ $16$ $32$ $64$ None of the above
8
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..???
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
11
How many numbers of spanning tree are possible?
1 vote
12
How to count the number of spanning tree?
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 ﬁnd 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?
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′$
15
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?
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?
1 vote
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?
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
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?
20
Some say answer is 2n and someplace else it's been told 2n-1-1. So, what's the corrent one?
1 vote
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
1 vote
22
1 vote
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
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 ____.
25
How to approach such questions ? Please provide detailed solution. Answer given is option C
1 vote
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.