Algorithms
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 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?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.
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. What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?Q120.
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?