Description

This mock test of Test: Spanning Tree for GATE helps you for every GATE entrance exam.
This contains 24 Multiple Choice Questions for GATE Test: Spanning Tree (mcq) to study with solutions a complete question bank.
The solved questions answers in this Test: Spanning Tree quiz give you a good mix of easy questions and tough questions. GATE
students definitely take this Test: Spanning Tree exercise for a better result in the exam. You can find other Test: Spanning Tree extra questions,
long questions & short questions for GATE on EduRev as well by searching above.

QUESTION: 1

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.

Solution:

Statement P is true.

For statement Q consider a simple graph with 3 nodes.

Shortest path from A to C is A-B-C = 1 + 2 = 3

Now if the value of each edge is increased by 100,

The shortest path from A to C is A-C = 200, (A-B-C = 101 + 102 = 203)

QUESTION: 2

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 .

Solution:

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

*Multiple options can be correct

QUESTION: 3

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:

Solution:

When Union-Find 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

big-O specifies asymptotic upper bound only.

Ref: http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/

QUESTION: 4

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?

Solution:

QUESTION: 5

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?

Solution:

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.

QUESTION: 6

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:

Solution:

2(n-1) the spanning tree will traverse adjacent edges since they contain the least weight.

QUESTION: 7

**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?

Solution:

Path: 1 -> 0 -> 4 -> 2

Weight: 1 + 4 + 3

QUESTION: 8

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?

Solution:

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.

QUESTION: 9

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?

Solution:

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.

QUESTION: 10

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?

Solution:

in option d b-c with weight 4 is added before a-c 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

QUESTION: 11

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?

Solution:

Answer is (D) 10. The edges of the spanning tree are: 0 - 1, 1 - 3, 3 - 4, 4 - 2. Total Weight = 10

QUESTION: 12

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?

Solution:

QUESTION: 13

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?

Solution:

Answer is (B) 8. The possible path is: 1 - 0, 0 - 4, 4 - 2.

QUESTION: 14

An undirected graph

The length of the path from

Solution:

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(n-1))

=1+(2+ 4+6+....till n-1 terms)

=1+ 2(1+2+3+4+...n-1)

=1+(n-1)*n=n^{2}-n+1

In this case v6 = 6^{2}-6+1 =31

QUESTION: 15

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?

Solution:

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.

QUESTION: 16

Let G be a connected simple graph (no self-loops 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?

Solution:

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.

QUESTION: 17

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

Solution:

There will be unique min weight spanning tree since all weights are distinct.

QUESTION: 18

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)

Solution:

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.

*Answer can only contain numeric values

QUESTION: 19

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 ______.

Solution:

first find no of edges in mst...

mst has n-1 edges where n is no of vertices. 100-1 =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

*Answer can only contain numeric values

QUESTION: 20

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_______________.

Solution:

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

*Answer can only contain numeric values

QUESTION: 21

The number of distinct minimum spanning trees for the weighted graph below is _____

Solution:

*Answer can only contain numeric values

QUESTION: 22

How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to edges).

Solution:

2 only.

{AB,BC,AE,BD} and {AB,BC,AE,CD}.

QUESTION: 23

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

Solution:

*Answer can only contain numeric values

QUESTION: 24

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 __________

Solution:

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

### SPANNING TREE ALGORITHM

Doc | 63 Pages

### Minimum Spanning Trees

Doc | 13 Pages

### Algorithms Minimum Spanning Trees

Doc | 3 Pages

- Test: Spanning Tree
Test | 24 questions | 90 min

- Spanning Tree Protocol, Networking Quiz
Test | 15 questions | 30 min

- Test: Tree Structure
Test | 13 questions | 40 min

- Test: On Killing A Tree
Test | 15 questions | 20 min

- Tree (Basic Level) - 1
Test | 10 questions | 30 min