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?

A

S1 is false and S2 is true.

B

S1 is true and S2 is false.

C

Both S1 and S2 are true.

D

Both S1 and S2 are false.

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?

A

I only

B

II only

C

Both I and II

D

Neither I nor II

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?

A

I only

B

II only

C

Both I and II

D

Neither I nor II

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

A

1

B

2

C

3

D

4

G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE? I. If e is the lightest edge of some cycle in G, then every MST of G includes e II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e

A

I only

B

II only

C

both I and II

D

neither I nor II

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?

A

T' = T with total weight t' = t²

B

T' = T with total weight t' < t ²

C

T' ≠ T but total weight t' = t²

D

None of the above

Let G be an undirected connected graph with distinct edge weights . Let emax be the edge with maximum weight and emin be the edge with minimum weight. Which of the following statements is false.

A

Every minimum spanning tree of G must contain e_min

B

If emax is in a minimum spanning tree, then its removal must be disconnected G.

C

No minimum spanning tree contains e_max

D

G has a unique minimum spanning tree.

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?

A

I only

B

II only

C

Both I and II

D

Neither I nor II

Let G be an undirected connected graph with distinct edge weight. Let emax be the edge maximum weight and emin the edge with minimum weight. Which of the following statements are false?

A

Every minimum spanning tree of G must contain e_min

B

If e_maxis in a minimum spanning tree, then its removal must disconnect G

C

No minimum spannig tree contains e_max

D

G has a unique spanning tree

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 ?

A

The edge with the second smallest weight is always part of any minimum spanning tree of G

B

One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G

C

Suppose S ⊆ V be such that S ≠ ϕ and S ≠ V. Consider the edge with the minimum weight such that one of its vertices is in S and the other in V \ S . Such an edge will always be part of any minimum spanning tree of G

D

G can have multiple minimum spanning tree

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

Related Questions