Bissoy.com
Doctors Medicines MCQs Q&A

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?

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? Correct Answer I only

Concept:

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Example:

Graph G(V, E)

[ alt="Assignment 3 Neetu GATE 2017 Set 1 21 - 30 10 Qs 1&2Marks Solution Modified images Raju D 2" src="//storage.googleapis.com/tb-img/production/19/12/Assignment%203_Neetu_GATE%202017%20Set%201_21%20-%2030_10%20Qs_1%262Marks_Solution_Modified_images_Raju_D%202.PNG" style="width: 148px; height: 114px;">

G(V, V – 1) → minimum spanning tree

[ alt="Assignment 3 Neetu GATE 2017 Set 1 21 - 30 10 Qs 1&2Marks Solution Modified images Raju D 3" src="//storage.googleapis.com/tb-img/production/19/12/Assignment%203_Neetu_GATE%202017%20Set%201_21%20-%2030_10%20Qs_1%262Marks_Solution_Modified_images_Raju_D%203.PNG">

If edge weights are distinct then there exist unique MST.

Hence Statement I is correct.

When edge weights are distinct and positive in that case shortest path between any two vertices of the graph is not always unique. Shortest path can be different even if the edge weights are unique.

Example:

[ alt="F1 R.S Madhu 4.12.19 D 7" src="//storage.googleapis.com/tb-img/production/19/12/F1_R.S_Madhu_4.12.19_D%207.png" style="width: 154px; height: 115px;">

Distance between A → C (3) and A → B → C (1 + 2 = 3), both paths has same distance.

Hence statement II is incorrect.

Related Questions

Let G be any connected, 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?
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by 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 change
Let G be a connected undirected weighted graph. Consider the following two statements. S1: There exists a minimum weight 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 one of the following options is correct?
Which of the following statements regarding tree are correct? (A) All the links of a tree together does not constitute the complement of the corresponding tree (B) A connected subgraph of a connected graph is a tree if there exist (n - 1) nodes of the group (C) A connected subgraph of a connected graph is a tree if there exist many paths between any pair of nodes in it (D) The number of terminal nodes of end vertices of every tree are atleast two (E) Every connected graph has atleast one tree Choose the correct answer from the options given below: (1) (A) and (B) only (2) (B) and (C) only (3) (B) and (D) only (4) (D) and (E) only
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?
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?
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD .) (II) For every edge (u, v) of if u is at depth i and v is at depth j in TB , then |? − ?| = 1. Which of the statements above must necessarily be true?
The line graph L(G) of a simple graph G is defined as follows: There is exactly one vertex v(e) in L(G) for each edge e in G. For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e' are incident with the same vertex in G. Which of the following statements is/are TRUE? (P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.
Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE ?