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 eII. If e is the heaviest edge of some cycle in G, then every MST of G excludes e

G = (V, E) is an undirected simple graph in which each edge has a dist

1.	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 eII. 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
Answer» C. both I and II

Discussion

No Comment Found

Related MCQs

Let G = (V, E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u, v) ϵ V × V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is
Depth First Search graph search algorithm uses _______ data structure for its implementation.
Consider a directed graph G = {V, E} with vertex set V = {A, B, C, D} and edge set E = {AB, AC, BC, BD, DC}. Which of the following is a valid topological ordering of graph G?
G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4, v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7}. A breadth first search of the graph is performed with v1 as the root node. Which of the following is a tree edge?
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following option is/are correct?
Consider the directed graph given below.Which one of the following is 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 changeQ: Shortest path between any pair of vertices does not change
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 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 |
A weighted complete graph with n vertices has weight 2|i - j| at edges (vi, vj). The weight of a minimum spanning tree is

Discussion

No Comment Found

Related MCQs

Reply to Comment