CMI2012-B-05a

Question

Given an undirected weighted graph $G = (V, E)$ with non-negative edge weights, we can compute a minimum cost spanning tree $T = (V, E')$. We can also compute, for a given source vertex $s \epsilon V$ , the shortest paths from s to every other vertex in $V$. We now increase the weight of every edge in the graph by 1. Are the following true or false, regardless of the structure of $G$? Give a mathematically sound argument if you claim the statement is true or a counterexample if the statement is false.

$T$ is still a minimum cost spanning tree of $G$.

Answer 1

for statement 2:let there are three vertices and three edges(ABC) and cost of each is AB=1,BC=2,CA=3.

now from A TO C IS COST 3.    IF WE INCREASE THE COST BY 1 OF EACH EDGE THEN AB=2,BC=3,CA=4

NOW FROM A TO C IS 5.

SO SHORTEST PATH CHANGES

=>II IS FALSE.

FOR 1:

THE QUESTION DOES NOT SAY ANYTHING ABOUT THE WEIGHT OF ST THAT IS WHEATHER IT IS DISTINCT OR SAME.

HOWEVER THIS STATEMENT IS TRUE .

SO STMT 1 IS TRUE