NPTEL Assignment Question

Question

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

 

• A. P only
• B. Q only
• C. Neither P nor Q
• D. Both P and Q

Comments

Answer: A

Shortest path may change.

Answer 1

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 …