Test: Spanning Tree - Computer Science Engineering (CSE) MCQ

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)

I. If e is the lightest edge of some cycle in G, then every MST of G includes e  (INCORRECT)

Let G = (V, E) is a graph with 4 vertices and 5 edges. 

Here, cycle contains the edge weights (3, 4, 5) but edge weight 3 is not included in the MST.

So, according to the cut-property of MST if is the lightest edge of some cycle in G, then every MST of G may or may not include e.

II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e          (CORRECT)

According to the cycle property of MST, same example as above. Here, cycle contains the edge weights (1, 2, 3)  and 3 is the heaviest so edge weight 3 is excluded in the MST.

If there is heaviest edge in cycle, then we will exclude it from the MST because there are other low-cost edges are available to include in MST (because edge weights are distinct here).

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/

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. 

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.

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

Path: 1 -> 0 -> 4 -> 2
Weight: 1 + 4 + 3

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.

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.

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

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

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₁ 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²-n+1
In this case v6 = 6²-6+1 =31

When the edge weights are squared the minimum spanning tree won't change.

t'< t² 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. 

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.

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

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.

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

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

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

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