Relationship between the shortest path distances - tree, Mathematics

Assignment Help:

1. a)  Given a digraph G = (V,E), prove that if we add a constant k to the length of every arc coming out from the root node r, the shortest path tree remains the same.  Do this by using potentials: 

i)  Show there is a potential y* for the new costs for which the paths in the tree to each node v have cost  y*v, and

ii) explain why this proves it.  What is the  relationship between the shortest path distances of the modified problem and those of the original problem?   

b) Can adding a constant k to the length of every arc coming out from a non-root node  produce a change in the shortest path tree?  Justify your answer.


Related Discussions:- Relationship between the shortest path distances - tree

Rounding, round 200 to nearest hundreds

round 200 to nearest hundreds

Find x if one ball is drawn at random from the box, A box contains 12 balls...

A box contains 12 balls out of which x are black .if one ball is drawn at random from the box  what is the probability that it will be a black ball ? If 6 more black balls are   pu

Zero-day attack, What is Zero-Day Attack? Explain Zero-Day Attack

What is Zero-Day Attack? Explain Zero-Day Attack

Find the polynomial g(x), On dividing the polynomial 4x 4 - 5x 3 - 39x 2 ...

On dividing the polynomial 4x 4 - 5x 3 - 39x 2 - 46x - 2 by the polynomial g(x) the quotient is x 2 - 3x - 5 and the remainder is -5x + 8.Find the polynomial g(x). (Ans:4 x 2 +

What is converse- inverse and contrapositive, What is Converse, Inverse, an...

What is Converse, Inverse, and Contrapositive In geometry, many declarations are written in conditional form "If ...., then....." For Example: "If two angles are right angles,

Determine the length of the rectangle, The height of a rectangle is 20 cm. ...

The height of a rectangle is 20 cm. The diagonal is 8 cm more than the length. Determine the length of the rectangle. a. 20 b. 23 c. 22 d. 21 d. To determine the len

Statistics., the mean and standarddeviation of set a is -x ans s respective...

the mean and standarddeviation of set a is -x ans s respectively.find the mean and standard deviation of set b

Inverse functions, We have seen that if y is a function of x, then fo...

We have seen that if y is a function of x, then for each given value of x, we can determine uniquely the value of y as per the functional relationship. For some f

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd