The Gateway to Computer Science Excellence
+1 vote
76 views
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$.
in Algorithms by Veteran (105k points)
edited by | 76 views

1 Answer

0 votes
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
by Boss (11.1k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
198,224 comments
104,909 users