Algorithm
Q111.
Let G be any connection, weighted, undirected graph: I. G has a unique minimum spanning tree if no two edges of G have the same weight. II. G has a unique minimum spanning tree if, for every cut of G, there is a unique minimum weight edge crossing the cut. Which of the above two statements is/are TRUE?Q112.
Consider the following undirected graph G: Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is ______.Q113.
Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements: (I) Minimum spanning tree of G is always unique. (II) Shortest path between any two vertices of G is always unique. Which of the above statements is/are necessarily true?Q115.
Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1,2,3,4,5, and 6. The maximum possible weight that a minimum weight spanning tree of G can haveis .Q116.
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increasedby the same value ,then which of the following statements is/are TRUE? P: Minimum spanning tree of G does not change Q: Shortest path between any pair of vertices does not changeQ117.
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. The edge e must definitely belong to:Q118.
Consider the following graph: Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal's algorithm?Q119.
Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always TRUE?Q120.
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}