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

Quadratic equation, how to solve this? y = 7x - 12 y = x2 Solve the sy...

how to solve this? y = 7x - 12 y = x2 Solve the system using substitution.

Center of mass - applications of integrals, Center of Mass - Applications o...

Center of Mass - Applications of integrals In this part we are going to find out the center of mass or centroid of a thin plate along with uniform density ρ. The center of mass

Fractions, what is equizilent to 2/5

what is equizilent to 2/5

Shares and dividend, a man in rested rupee 800 is buying rupee 5 shares and...

a man in rested rupee 800 is buying rupee 5 shares and then are selling at premium of rupee 1.15. He sells all the shares.find profit

Facts regarding linear equations, To solve out linear equations we will mak...

To solve out linear equations we will make heavy use of the following facts. 1. If a = b then a + c = b + c for any c.  All it is saying that we can add number, c, to both sides

Law of cosines - vector, Theorem a → • b → = ||a → || ||b → || cos• ...

Theorem a → • b → = ||a → || ||b → || cos• Proof Let us give a modified version of the diagram above. The three vectors above make the triangle AOB and note tha

Word problem solving, the traffic light at three different road crossing ch...

the traffic light at three different road crossing change after every 48 seconds, 72 seconds and 108 seconds respectively. if they change simultaneously at 7 a.m., at what time wil

Homogeneous differential equation, Assume that Y 1 (t) and Y 2 (t) are two ...

Assume that Y 1 (t) and Y 2 (t) are two solutions to (1) and y 1 (t) and y 2 (t) are a fundamental set of solutions to the associated homogeneous differential equation (2) so, Y

Fractions, What is two-thirds plus two-thirds?

What is two-thirds plus two-thirds?

Describe the introduction to integers, Describe the Introduction to Integer...

Describe the Introduction to Integers ? Integers include the positive and negative whole numbers, such as -4, -3, -2, -1, 0, 1, 2, 3, 4, and so on. A negative number has a "

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