The Gateway to Computer Science Excellence
For all GATE CSE Questions
Email or Username
I forgot my password
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
(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:
Nov 6, 2016
Nov 6, 2016
to add a comment.
← Prev. Qn. in Sub.
Next Qn. in Sub. →
GEEKS FOR GEEKS GATE 2017 MOCK
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)
Jun 9, 2019
GATE | GATE-CS-2003
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
Mar 31, 2019
#Algortihms Gate 2000 Question Self Doubt
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 ... being, since (u,v) is an edge in G therefore they can only be SIBLINGS in DFS tree and never have descendant relationship?
May 29, 2018
#Algorithms Gate 2005 Question Self Doubt.
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 ... the diagonal elements in adjacency matrix is = 0. You can take a Graph with 4 vertices and make anyone of them as a sink.
May 23, 2018
Quick search syntax
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Programming and DS
Theory of Computation
CO and Architecture
Tier 1 Placement Questions
Recent Blog Comments
Very slim chances..FML
I am getting 151 marks excluding question not...
everyone will be surprised seeing the cutoff this...
There is no point of any debate/discourse here....