Algorithms
Q121.
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?Q122.
Let G be an undirected connected graph with distinct edge weights. Let e_{max} be the edge with maximum weight and e_{min} the edge with minimum weight. Which of the following statements is false?Q124.
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?Q125.
For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Span?ning Tree?Q126.
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 treeQ127.
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?Q128.
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?Q129.
The correct matching for the following pairs is \begin{array}{ll|ll}\hline \text{A.} & \text{All pairs shortest path} & \text{1.} & \text{Greedy} \\\hline \text{B.} & \text{Quick Sort} & \text{2.}& \text{Depth-First Search} \\\hline \text{C.}& \text{Minimum weight spanning tree} & \text{3.} & \text{Dynamic Programming} \\\hline \text{D.} & \text{Connected Components} &\text{4.} & \text{Divide and Conquer} \\\hline \end{array}Q130.
G is a graph on n vertices and 2n-2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?