in Algorithms retagged by
242 views
0 votes
0 votes

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 change

Q: Shortest path between any pair of vertices does not change

 

  1. P only
  2. Q only
  3. Neither P nor Q
  4. Both P and Q
in Algorithms retagged by
242 views

1 comment

Answer: A

Shortest path may change.
0
0

1 Answer

0 votes
0 votes

A. P only ...

 

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight….

If edge weights are distinct then there exist unique MST....

 

Statement P: TRUE

Minimum spanning the tree of G does not change ...

 

Statement Q: False

Shortest path between any pair of vertices may change …

 

by

Related questions

0 votes
0 votes
1 answer
2