Let G = (V, E) be a directed, weighted graph with weight function w:E → ℝ.For some function f:v → ℝ, for each edge (u, v) ϵ E, define w’(u, v) as w(u, v) + f(u) – f(v).Which one of the options completes the following sentence so that it is TRUE?“The shortest paths in G under w are shortest paths under w’ too, ______”.

if and only if ∀u ϵ V, f(u) is positive

if and only if ∀u ϵ V, f(u) is negative

if and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every vertex of G

Let G = (V, E) be a directed, weighted graph with weight function w:E

1.	Let G = (V, E) be a directed, weighted graph with weight function w:E → ℝ.For some function f:v → ℝ, for each edge (u, v) ϵ E, define w’(u, v) as w(u, v) + f(u) – f(v).Which one of the options completes the following sentence so that it is TRUE?“The shortest paths in G under w are shortest paths under w’ too, ______”.
A.	for every f: v → ℝ
B.	if and only if ∀u ϵ V, f(u) is positive
C.	if and only if ∀u ϵ V, f(u) is negative
D.	if and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every vertex of G
Answer» B. if and only if ∀u ϵ V, f(u) is positive

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