Log In

Gate 2016 [closed]

0 votes
Let G be aweighted 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
P: Minimum spanning tree of G does notchange
Q: Shortest path between any pair of vertices doesnot change
(A) P only
(B) Q only
(C) NeitherPnorQ
(D) Both PandQ


answer is a.

why not D ,I think Shortest path between any pair of vertices will also not change.
closed as a duplicate of: GATE2016-1-14
in Algorithms
closed by

Related questions

2 votes
3 answers
If Kruskal’s algorithm is used for finding a minimum spanning tree of a weighted graph G with n vertices and m edges and edge weights are already given in a sorted list, then, What will be the time complexity to compute the minimum cost spanning tree given that union and find operations take amortized O(1) ? A O(m logn) B O(n) C O(m) D O(n logm)
asked Jun 9, 2019 in Algorithms Hirak 504 views
0 votes
0 answers
Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between (A) k and n (B) k – 1 and k + 1 (C) k – 1 and n – 1 (D) k + 1 and n – k The answer is C . how is it k-1?? I mean if we have only one component .?Please explain
asked Mar 31, 2019 in Algorithms Doraemon 175 views
1 vote
1 answer
Source - Here Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the ... edge. Point being, since (u,v) is an edge in G therefore they can only be SIBLINGS in DFS tree and never have descendant relationship?
asked May 29, 2018 in Algorithms iarnav 241 views
3 votes
1 answer
Source of the question - here A sink in a directed graph is a vertex i such that there is an edge from every vertex $j ≠ i $ to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where ... sink as all the diagonal elements in adjacency matrix is = 0. You can take a Graph with 4 vertices and make anyone of them as a sink.
asked May 23, 2018 in Algorithms iarnav 539 views