Minimum-spanning-Tree

Question 1
Consider the following undirected graph with edge weights as shown:

The number of minimum-weight spanning trees of the graph is _______
A
3
Question 1 Explanation: 

To find the number of spanning trees using 2 methods:

  1. If graph is complete, use n^n-2 formula
  2. If graph is not complete, then use kirchhoff theorem.

Steps in Kirchoff’s Approach:

(i) Make an Adjacency matrix.

(ii) Replace all non-diagonal is by – 1.

(iii) Replace all diagonal zero’s by the degree of the corresponding vertex.

(iv) Co-factors of any element will give the number of spanning trees.  

Using the Kirchhoff theorem will take lot of time because the number of vertices are 9. 

So, we use brute force technique to solve the problem with the help of Kruskal's algorithm.

Question 2

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

A
Theory Explanation.
Question 3

Let G = (V,E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u,v) ∈ V×V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is

A
θ(|E|+|V|)
B
θ(|E| log|V|)
C
θ(|E||V|)
D
θ(|V|)
Question 3 Explanation: 
Method-1:
• As T is a minimum spanning tree and we need to add a new edge to existing spanning tree.
• Later we need to check still T is a minimum spanning tree or not, So we need to check all vertices whether there is any cycle present after adding a new edge.
• All vertices need to traverse to confirm minimum spanning tree after adding new edge then time complexity is O(V).
Method-2:
Time Complexity:
Total vertices: V, Total Edges : E
• O(logV) – to extract each vertex from the queue. So for V vertices – O(VlogV)
• O(logV) – each time a new pair object with a new key value of a vertex and will be done at most once for each edge. So for total E edge – O(ElogV)
• So overall complexity: O(VlogV) + O(ElogV) = O((E+V)logV) = O(ElogV)
Note: Method-1 is the most appropriate answer for giving a question.
Question 4

Consider a graph G = (V, E), where V = {v1, v2, …, v100}, E = {(vi, vj) | 1 ≤ i < j ≤ 100}, and weight of the edge (vi, vj) is |i - j|. The weight of the minimum spanning tree of G is ______.

A
99
Question 4 Explanation: 
• If there are n vertices in the graph, then each spanning tree has n − 1 edges.
• N =100
• Edge weight is |i-j| for Edge (vi,vj) {1<=i<=100}
• The weight of edge(v1,v2) is 1 , edge(v5,v6) is 1.
• So, 99 edges of weight is 99.
Question 5

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?

A
T' = T with total weight t' = t2
B
T' = T with total weight t'2
C
T' ≠ T but total weight t' = t2
D
None of the above
Question 5 Explanation: 
Let graph G be

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 (t1) < (t2).
So option (D) is correct answer.
Question 6

A complete, undirected, weighted graph G is given on the vertex {0, 1,...., n−1} for any fixed ‘n’. Draw the minimum spanning tree of G if
(a) the weight of the edge (u,v) is ∣u − v∣
(b) the weight of the edge (u,v) is u + v

A
Theory Explanation.
Question 7

Let G be an undirected connected graph with distinct edge weight. Let emax be the edge with maximum weight and  emin the edge with minimum weight. Which of the following statements is false?

A
Every minimum spanning tree of G must contain emin
B
If emax is in a minimum spanning tree, then its removal must disconnect G
C
No minimum spanning tree contains emax
D
G has a unique minimum spanning tree
Question 7 Explanation: 

Minimum Spanning Tree:
Question 8

Consider a weighted undirected graph with vertex set V = {n1,n2,n3,n4,n5,n6} and edge set

 E = {(n1,n2,2),(n1,n3,8),(n1,n6,3),(n2,n4,4),(n2,n5,12),(n3,n4,7),(n4,n5,9), 
     (n4,n6,4)}. The third value in each tuple represents the weight of the edge 
     specified in the tuple. 

(a) List the edges of a minimum spanning tree of the graph.
(b) How many distinct minimum spanning trees does this graph have?
(c) Is the minimum among the edge weights of a minimum spanning tree unique overall possible minimum spanning trees of a graph?
(d) Is the maximum among the edge weights of a minimum spanning tree unique over all possible minimum spanning trees of a graph?

A
Theory Explanation is given below.
Question 8 Explanation: 
(b) 2 distinct MST's.
(c) Yes, it always. Because 'the edge weight 2 is unique'.
(d) Yes, it always. Because 'the edge weight 9 is unique'.
Question 9

What is the weight of a minimum spanning tree of the following graph ?

A
29
B
31
C
38
D
41
Question 9 Explanation: 

1+2+3+2+8+4+4+2+5 =31
Question 10
Let G be a connected undirected weighted graph. Consider the following two statements.
S1: There exists a minimum weighted edge in G which is present in every minimum spanning tree of G.
S2:If every edge in G has distinct weight, then G has a unique minimum spanning tree.
Which of the following options is correct?
A
S1is false and S2is true.
B
S1is true and S2is false.
C
Both S1 and S2are false.
D
Both S1 and S2are true.
Question 10 Explanation: 

Statement-1: FALSE: The given statement is not valid for all the cases because they are not mentioned, edge weights are in distinct or duplicate. So, we can take any random edge weights for the given statement. 

Example:


Statement-2: TRUE: Using the kruskal’s (or) prim's algorithm we get a unique MST when there is a unique edge weight. 

Example:


Based on the above graph, we get the MST is
Question 11
 In a directed acyclic graph with a source vertex s, the quality-score of s directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex v other than s, the quality-score of v is defined to be the maximum among the quality-scores of all the paths from s to v. The quality-score of s is assumed to be 1.

The sum of the quality-scores of all the vertices in the graph shown above is _________.
A
929
Question 12

What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?

A
1
B
2
C
3
D
n
Question 12 Explanation: 
If graph is connected and contains n vertices and n edges means there is possibility of only one cycle.
→ If we create a different spanning tree by removing one edge at a time.
→ For cycle required 3 minimum edges. So there is at least 3 spanning trees in such a graph.
There are 12 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access