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

Liniar Algebra, Assume A and B are symmetric. Explain why the following are...

Assume A and B are symmetric. Explain why the following are symmetric or not. 1) A^2 - B^2 2) (A+B)(A-B) 3) ABA 4) ABAB 5) (A^2)B

Riddles, I am a number yell my identity subtract 20 from me and add 30 make...

I am a number yell my identity subtract 20 from me and add 30 make the total twice to reach century you still need eight

Harold used a 3% iodine solution and a 20% iodine solution, Harold used a 3...

Harold used a 3% iodine solution and a 20% iodine solution to make a 95- ounce solution in which was 19% iodine. How many ounces of the 3% iodine solution did he use? Let x = t

Which kevin gets paid is represented by x what does paid, Patrick gets paid...

Patrick gets paid three dollars less than four times what Kevin gets paid. If the number of dollars which Kevin gets paid is represented through x, what does Patrick get paid?

Probability, I don''t understand the AND/OR rules and how they apply to pro...

I don''t understand the AND/OR rules and how they apply to probability

Rounding, the number is 605176 the underline digit is 0

the number is 605176 the underline digit is 0

Perform algebraic operation , Perform each of the following algebraic expr...

Perform each of the following algebraic expression as instruction says;- I.Multiply 5x+6m+4y by5 II.Divide 4ax+6ay-10az by 2a

Percentage profit and loss, #a grocer buys a box of 200oranges for $25 he s...

#a grocer buys a box of 200oranges for $25 he sells them for 15c caluclate his percentage profit

Limits, lim(x->0) xln²(xln(x))

lim(x->0) xln²(xln(x))

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