## Minimum-Spanning-Tree

Question 1 |

I. G has a unique minimum spanning tree, if no two edges of G have the same weight.

II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut.

Which of the above statements is/are TRUE?

I only | |

II only | |

Both I and II | |

Neither I nor II |

I. TRUE: G Graph is unique, no two edges of the graph is same.

Step-1: Using Kruskal's algorithm, arrange each weights in ascending order.

17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30

Step-2:

Step-3: 17 + 18 + 20 + 21 + 22 + 23 + 26 = 147

Step-4: Here, all the elements are distinct. So, the possible MCST is 1.

II. TRUE: As per the above graph, if we are cut the edge, that should the be the minimum edge.

Because we are already given, all minimum edge weights if graph is distinct.

Question 2 |

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

4 | |

5 | |

6 | |

7 |

If x = 5 then the total number of MWSTs are 4.

If r = 1

If r = 2

If r = 3

If r = 4

If r = 5

Question 3 |

*G = (V, E)*be any connected undirected edge-weighted graph. The weights of the edges in

*E*are positive and distinct. Consider the following statements:

(I) Minimum Spanning Tree of

*G*is always unique.

(II) Shortest path between any two vertices of

*G*is always unique.

Which of the above statements is/are necessarily true?

(I) only | |

(II) only | |

both (I) and (II) | |

neither (I) nor (II) |

Let us take an example

Step 1:

Using kruskal’s algorithm, arrange each weights in ascending order.

17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30

Step 2:

Step 3:

17+18+20+21+22+23+26 = 147

Step 4:

Here, all the elements are distinct. So the possible MCST is 1.

Statement-II: May or may not happen, please take an example graph and try to solve it. This is not correct always.

So, we have to pick most appropriate answer.

Question 4 |

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

7 | |

8 | |

9 | |

10 |

Now consider vertex A to make Minimum spanning tree with Maximum weights.

As weights are 1, 2, 3, 4, 5, 6. AB, AD, AC takes maximum weights 4, 5, 6 respectively.

Next consider vertex B, BA = 4, and minimum spanning tree with maximum weight next is BD & BC takes 2, 3 respectively.

And the last edge CD takes 1.

So, 1+2+4 in our graph will be the Minimum spanning tree with maximum weights.

Question 5 |

*G = (V,E)*is an undirected simple graph in which each edge has a distinct weight, and

*e*is a particular edge of

*G*. Which of the following statements about the minimum spanning trees (MSTs) of

*G*is/are

**TRUE**?

I. If

*e*is the lightest edge of some cycle in

*G*, then every MST of

*G*

__includes__

*e*

II. If

*e*is the heaviest edge of

__some__cycle in

*G*, then every MST of

*G*

__excludes__

*e*

I only | |

II only | |

both I and II | |

neither I nor II |

The MSTs of G may or may not include the lightest edge.

Take rectangular graph labelled with P,Q,R,S.

Connect with P-Q = 5, Q-R = 6, R-S = 8, S-P = 9, P-R = 7.

When we are forming a cycle R-S-P-R. P-R is the lightest edge of the cycle.

The MST abcd with cost 11

P-Q + Q-R + R-S does not include it.

Statement-2: True

Suppose there is a minimum spanning tree which contains e. If we add one more edge to the spanning tree we will create a cycle.

Suppose we add edge e to the spanning tree which generated cycle C.

We can reduce the cost of the minimum spanning tree if we choose an edge other than e from C for removal which implies that e must not be in minimum spanning tree and we get a contradiction.

Question 6 |

The graph shown below 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 ______________.

69 | |

70 | |

71 | |

72 |

⇒ Total sum = 10 + 9 + 2 + 15 + 7 + 16 + 4 + 6 = 69

--> First we compare A-C and A-B we find 9 at A-C it means A-B must greater than A-C and for minimum possible greater value than 9 will be 10

-> Second we compare B-E and C-D in which we select B-E is 15 which C-D possible weight 16.

-> Third, we compare E-D and F-D in which we select F-D 6 means E-D must be greater than 6 so possible value greater than 6 is 7 .

Note: Add First+Second+Third=(A-B=10)+(C-D=16)+(E-D=7)

Question 7 |

Let G be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes __________.

995 | |

996 | |

997 | |

998 |

Question 8 |

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

6 | |

7 | |

8 | |

9 |

Minimum Spanning Tree:

From the diagram, CFDA gives the minimum weight so will not disturb them, but in order to reach BE=1 we have 3 different ways ABE/ DBE/ DEB and we have HI=1, the shortest weight, we can reach HI=1 through GHI/ GIH.

So 3*2=6 ways of forming Minimum Spanning Tree with sum as 11.

Question 9 |

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

T' = T with total weight t' = t ^{2} | |

T' = T with total weight t' | |

T' ≠ T but total weight t' = t ^{2} | |

None of the above |

Then MST for G is,

Now let's square the weights,

Then MST for G' is,

So, from above we can see that T is not necessarily equal to T' and moreover (t

^{1}) < (t

^{2}).

So option (D) is correct answer.

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

What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?

1/12(11n ^{2}-5n) | |

n ^{2} – n + 1 | |

6n – 11 | |

2n + 1 |

Cost of MST,

= 3+4+6+8 = 21

Only option (B) satisfies it.

Question 11 |

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 v_{5} to v_{6} in the MST of previous question with n =10 is

11 | |

25 | |

31 | |

41 |

Now MST of above graph is,

∴ The length of path from v

_{5}to v

_{6}in the MST is,

8+4+3+6+10 = 31