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

Limit comparison test - sequences and series, Limit Comparison Test Ass...

Limit Comparison Test Assume that we have two series ∑a n and ∑b n with a n , b n   ≥ 0 for all n. Determine, If c is positive (i.e. c > 0 ) and is finite (i.e. c

.., the circumference of a circle C of radius r is given by C=2pR.taking p ...

the circumference of a circle C of radius r is given by C=2pR.taking p to be 22/7 a)find the circumference when the radius is 28 cm b)find the radius when the circumference is 484

The mode -measures of central tendency, The mode - It is one of the me...

The mode - It is one of the measures of central tendency. The mode is defined as a value in a frequency distribution that has the highest frequency. Occasionally a single valu

Applications of derivatives, Applications of derivatives : At last, let's ...

Applications of derivatives : At last, let's not forget about our applications of derivatives. Example    Assume that the amount of air in a balloon at any time t is specified

Find out the mean time, 1 . The probability that a couple will have a child...

1 . The probability that a couple will have a child with black hair is 0.6. If this couple has 7 children what is (a) the probability that exactly 3 of these children have bl

Articulate reasons and construct arguments, By such interactions children l...

By such interactions children learn to articulate reasons and construct arguments. When a child is exposed to several interactions of this kind, she gradually develops the ability

MUTIPLYING FRACTIONS, EVERY TIME I TRY TO DO ANY KIND OF FRACTIONS WELL MUL...

EVERY TIME I TRY TO DO ANY KIND OF FRACTIONS WELL MULTIPLYING I ALWAYS GET IT WRONG

Lori, rewrite the problem so that the divisor is a whole number...8.5/2.3

rewrite the problem so that the divisor is a whole number...8.5/2.3

How many types of integer operatiions explain, How many types of Integer Op...

How many types of Integer Operatiions explain? Adding Integers The rules for adding integers are: 1. A positive number plus a positive number equals the sum of the two pos

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