Minimum-Spanning-Tree
Question 1 |
The number of minimum-weight spanning trees of the graph is _______
3 |
To find the number of spanning trees using 2 methods:
- If graph is complete, use n^n-2 formula
- 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).
Theory Explanation. |
Question 3 |
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 ______.
99 |
• 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 4 |
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
θ(|E|+|V|) | |
θ(|E| log|V|) | |
θ(|E||V|) | |
θ(|V|) |
• 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 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?
T' = T with total weight t' = t2 | |
T' = T with total weight t' | |
T' ≠ T but total weight t' = t2 | |
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 (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
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?
Every minimum spanning tree of G must contain emin | |
If emax is in a minimum spanning tree, then its removal must disconnect G | |
No minimum spanning tree contains emax | |
G has a unique minimum spanning tree |
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?
Theory Explanation is given below. |
(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 ?
29 | |
31 | |
38 | |
41 |
1+2+3+2+8+4+4+2+5 =31
Question 10 |
The sum of the quality-scores of all the vertices in the graph shown above is _________.
929 |
Question 11 |
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?
S1is false and S2is true.
| |
S1is true and S2is false. | |
Both S1 and S2are false. | |
Both S1 and S2are true. |
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 12 |
16 | |