1 Crore+ students have signed up on EduRev. Have you? 
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?
P: Minimum spanning tree of does not change.
Q: Shortest path between any pair of vertices does not change.
Statement P is true.
For statement Q consider a simple graph with 3 nodes.
Shortest path from A to C is ABC = 1 + 2 = 3
Now if the value of each edge is increased by 100,
The shortest path from A to C is AC = 200, (ABC = 101 + 102 = 203)
is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G . Whichof the following statements about the minimum spanning trees
I. If e is the lightest edge of some cycle in G, then every MST of G includes .
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e .
I think answer is option B
Statement 2 is correct absolutely. if e is the heaviest edge in cycle every mst excludes it. Regarding statement 1, It is not fully right i think. When we think of a complete graph with 4 vertices and edge weights 1,2,5,6 in non diagonal and diagonal edges 3 and 4. 4,5,6 will create a cycle and we can exclude the lighest edge e (4)
from it, in a MST
So i think answer could be B
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:
Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph G with n vertices and edges has the time complexity of:
When UnionFind algorithm is used to detect cycle while constructing the MST time complexity is where m is the number of edges, and n is the number of vertices. Since in a graph, options B and E are also correct as
bigO specifies asymptotic upper bound only.
Ref: http://www.geeksforgeeks.org/greedyalgorithmsset2kruskalsminimumspanningtreemst/
Let G be an undirected connected graph with distinct edge weights. Let e_{max} be the edge with maximum weight and the edge with minimum weight. Which of the following statements is false?
In kruskal’s algorithm, we pick the edges in ascending order and add them to the forest if no cycle is formed. Option A is True because first edge could never create a cycle.
The only reason for emax to be present in the minimum spanning tree could be that it is the only possible edge to cover a particular vertex in a tree since all vertices have to be present in a spanning tree by definition.
Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always TRUE?
Option a is always true
Option b is not true when e is not part of a cycle.
Option c is not true when e is part of a cycle and all edge weights are same in that cycle
Option d is need not be true when e is not part of a cycle
Option a is always true as only the min weight edge in a cut set will be part of a minimum spanning tree.
Consider a weighted complete graph G on the vertex set {v1,v2,.....vn} such that the weight of the edge (vi, vj) is . The weight of a minimum spanning tree of G is:
2(n1) the spanning tree will traverse adjacent edges since they contain the least weight.
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.
In the graph given in above question, what is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?
Path: 1 > 0 > 4 > 2
Weight: 1 + 4 + 3
Let ω be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight ω . Which of the following is FALSE?
D is the false statement.
A minimum spanning tree must have the edge with the smallest weight (In Kruskal's algorithm we start from the smallest weight edge). So, C is TRUE.
If e is not part of a minimum spanning tree, then all edges which are part of a cycle with e, must have weight ≤ e, as otherwise we can interchange that edge with e and get another minimum spanning tree of lower weight. So, B and A are also TRUE.
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 Spanning Tree?
Prim's algorithm starts with from any vertex and expands the MST by adding one vertex in each step which is close to the Intermediate MST(made till previous step).
Therefore correct answer would be (C).
(A): (d,f) is chosen but neither d nor f vertices are part of the previous MST(MST made till previous step).
(B): (g,h) is chosen but neither g or h vertices are part of the previous MST(MST made till previous step).
(D): (f,c) is chosen but at that point (f,d) is close to the intermediate MST.
Consider the following graph:
Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?
in option d bc with weight 4 is added before ac with weight 3 is added. In kruskal's algorithm edges should be added in non decreasing order of weight
So option D may be correct
Consider a complete undirected graph with vertex set
What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?
Answer is (D) 10. The edges of the spanning tree are: 0  1, 1  3, 3  4, 4  2. Total Weight = 10
An undirected graph G (V,E) contains n(n>2) nodes named v_{1},v_{2},.......v_{n.} Two nodes v_{i},v_{j} are connected if and only if Each edge (v_{i},v_{j}) is assigned a weight i=+j. A sample graph with n=4 is shown below.
What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?
Consider a complete undirected graph with vertex set Entry W_{ij} in the matrix W below is the weight of the edge
What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?
Answer is (B) 8. The possible path is: 1  0, 0  4, 4  2.
There is no direct edge between V_{i} and V_{i+1} vertex in mst except V1 to V2 so path from V_{i} and V_{i+1} includes all edges from v_{1} to V_{i+1} which are in mst:
edge weights in mst:
=3 + 4 + 6 + 8 + 10 + 12 +...+*(2(n1))
=1+(2+ 4+6+....till n1 terms)
=1+ 2(1+2+3+4+...n1)
=1+(n1)*n=n^{2}n+1
In this case v6 = 6^{2}6+1 =31
Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G', respectively, with total weights t and t'. Which of the following statements is TRUE?
When the edge weights are squared the minimum spanning tree won't change.
t'< t^{2 }because sum of squares is always less than the square of the sums except for a single element case.
Hence, B is the general answer and A is also true for a single edge graph.
Let G be a connected simple graph (no selfloops or parallel edges) on n ≥ 3vertices, with distinct edge weights. Let e_{1},e_{2}........e_{m} be an ordering of the edges in decreasing order of weight. Which of the following statements is FALSE?
a) & c) are trivially true. Edge with max value e1 must be present in Maximum spanning tree & same with minimum.
e) This is true, because all egde weights are distinct. maximum spanning tree is unique.
b) e1 & e2 must be present in Maximum spanning tree. I'll prove it using Kruskal Algorithm.
We will first insert weight with biggest value, e1. Then we insert e2 (second highest) . 2 edges do not create cycle. Then
we can go on from there inserting edges according to edge weights.As they have just asked for top 2 edges, using Kruskal
Algo we can say that top 2 edges must be in Maximum spanning tree.
d)
This is false. There are chances that this em weight edge is cut edge(Bridge) Then it must be inserted to from any spanning tree.
We can not say the same for Top 3 as they can create cycle & They we can not take a3 to make spanning tree.
In a connected weighted graph with vertices, all the edges have distinct positive integer weights. Then, the maximum number of minimum weight spanning trees in the graph is
There will be unique min weight spanning tree since all weights are distinct.
Consider the following undirected connected graph G with weights on its edges as given in the figure below. A minimum spanning tree is a spanning tree of least weight and a maximum spanning tree is one with largest weight. A second best minimum spanning tree whose weight is the smallest among all spanning trees that are not minimum spanning trees in G.
Which of the following statements is TRUE in the above graph? (Note that all the edge weights are distinct in the above graph)
In the graph we have all edge weights are distinct so we will get unique minimum and maximum spanning tree.
Each Cycle must exclude maximum weight edge in minimum spanning tree.
Here we have two cycle of 3 edges , ade and cgk .
for second best minimum spanning tree = exclude ae edge and include de edge
other way : second best minimum spanning tree= exclude cg edge and include gk edge.
so e should be the ans.
Let be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of is 500. When the weight of each edge of is increased by five, the weight of a minimum spanning tree becomes ______.
first find no of edges in mst...
mst has n1 edges where n is no of vertices. 1001 =99 edges
each 99 edges in mst increases by 5 so weight in mst increased 99*5=495
now total weight of mst =500+495=995
The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is_______________.
Consider the cycle ABC. AC and AB are part of minimum spanning tree. So, AB should be greater than max(AC, BC) (greater and not equal as edge weights are given to be distinct), as otherwise we could add AB to the minimum spanning tree and removed the greater of AC, BC and we could have got another minimum spanning tree. So, AB > 9.
Similarly, for the cycle DEF, ED > 6.
And for the cycle BCDE, CD > 15.
So, minimum possible sum of these will be 10 + 7 + 16 = 33. Adding the weight of spanning tree, we get the total sum of
edge weights
= 33 + 36 = 69
The number of distinct minimum spanning trees for the weighted graph below is _____
How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to edges).
2 only.
{AB,BC,AE,BD} and {AB,BC,AE,CD}.
An undirected graph G(V, E) contains n ( n > 2 ) nodes named v_{1} , v_{2} ,….v_{n}. Two nodes v_{i }, v_{j} are connected if and only if 0 < i – j <= 2. Each edge (v_{i}, v_{j} ) is assigned a weight i + j. A sample graph with n = 4 is shown below.
The length of the path from v5 to v6 in the MST of previous question with n = 10 is
Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is __________
it is said maximum weight pssbl.
draw a triangle. 3 sides weight 1 2 3. and 4th point is in center. join it with tringle vertices.. got more 3 sides. new side weight 4 5 6. now draw mst. take 1 take 2. cant take 3, so take 4. 1+2+4=7
136 docs165 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
136 docs165 tests








