Minimum Spanning Tree
Q21.
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 ___________.Q22.
Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w . Which of the following is FALSE?Q24.
Consider a weighted complete graph G on the vertex set {v_{1},v_{2},...,v_{n}} such that the weight of the edge (v_{i},v_{j}) is 2|i-j|. The weight of a minimum spanning treeQ25.
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?Q26.
Consider the undirected graph below:Using Prim's algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?Q27.
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W_{ij} in the matrix W below is the weight of the edge {i, j}. \begin{pmatrix} 0&1 & 8 & 1 &4 \\ 1& 0 & 12 & 4 & 9\\ 8 & 12 & 0 & 7 & 3\\ 1& 4& 7 & 0 &2 \\ 4& 9 & 3& 2 &0 \end{pmatrix}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?Q28.
Consider the following graph: Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal's algorithm?Q29.
Let s and t be two vertices in a undirected graph G=(V, E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s\inX and t\inY. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y. Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum congestion. Which one of the following paths is always such a path of minimum congestion?Q30.
An undirected graph G(V, E) contains n (n>2) nodes named v1 , v2 ,...,vn. Two nodes vi , vj are connected if and only if 0\lt |i-j|\leq2. Each edge (vi,vj ) 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