edited by
22,397 views
62 votes
62 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$
edited by

8 Answers

Best answer
97 votes
97 votes

Statement $P$ is true.

For statement $Q$ consider a simple graph with $3$ nodes.
$$\begin{array}{|l|l|l|l|} \hline \textbf{} & \textbf{A} & \textbf{B} & \textbf{C} \\\hline \textbf{A} & \text{0} & \text{1} & \text{100}  \\\hline\textbf{B} & \text{1} & \text{0} & \text{2} \\\hline  \textbf{C} & \text{100} & \text{2} & \text{0} \\\hline \end{array}$$
Shortest path from A to C is A-B-C $= 1 + 2 = 3$ 

Now if the value of each edge is increased by $100$,
$$\begin{array}{|l|l|l|l|} \hline \textbf{} & \textbf{A} & \textbf{B} & \textbf{C} \\\hline \textbf{A} & \text{0} & \text{101} & \text{200}  \\\hline\textbf{B} & \text{101} & \text{0} & \text{102} \\\hline  \textbf{C} & \text{200} & \text{102} & \text{0} \\\hline \end{array}$$
The shortest path from A to C is A-C $= 200$, (A-B-C $= 101 + 102 = 203$)

Hence, option A is correct.

edited by
70 votes
70 votes

P is True:-> Bcz distinct edge weights and all the edge cost are increasing with same value so edges which forms MST will remain intact.

Q is false . See counter example

See here shortest path from S to U was initially S-T-U  but after increasing there value by  2 it becomes S-U.

Note here Min Spanning tree edges remains same ST and TU.

So P true and Q false  So Option A is Ans.

edited by
5 votes
5 votes
Both are correct...option is D
2 votes
2 votes

P: True.

Q: If every edge weight is increased by the same value, the shortest path between any pair of vertices does not change. This statement will be true for trees as there will be a unique path between any pair of vertices in a tree. But here in this question, we are asked for any graph in general so there are possibilities of multiple paths.

--------------------------------------------------------------------------------------------------------------------------------------------------------

Suppose in a graph with 3 vertices a,b,c vertices are connected like this a-b-c and also a is directly connected to c. Edge weights are (a,b,2),(b,c,3),(a,c,6). Here shortest path between (a,c) is a to c via b. Now each edge weight is increased by the same value(suppose some value > 2). Now you will find a-c direct path as the shortest one, so our shortest path changed.

So Q False.

Answer:

Related questions

85 votes
85 votes
18 answers
2
Sandeep Singh asked Feb 12, 2016
35,080 views
Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3, 4, 5,$ and $6$. The maximum possible weight that a minimum weight s...
61 votes
61 votes
5 answers
3
Sandeep Singh asked Feb 12, 2016
28,244 views
Consider the following directed graph:The number of different topological orderings of the vertices of the graph is _____________.