Follow Us :

DT Q34

34Let 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
  • Option : A
  • Explanation :
    Minimum sparring tree of G does not change, because every edge weight is positive and distinct, so to increase the value of each edge by same constant value it does not change tree.
    Q is false because path may be change. Here path from B to C can. be via A but after increase by 1 path must be from B to C direct.
    Example
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *