Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x ϵ V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u, v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u) – d(v)?

Let G = (V, E) be a simple undirected graph, and s be a particular ver

1.	Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x ϵ V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u, v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u) – d(v)?
A.	-1
B.	0
C.	1
D.	2
Answer» E.

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