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

Launching of a new product, Launching a new product (Blackberry Cube) Analy...

Launching a new product (Blackberry Cube) Analysis (target market) Product features Promotions and advertisement sample design (location)

Definition of laplace transforms, You know that it's all the time a little ...

You know that it's all the time a little scary while we devote an entire section just to the definition of something. Laplace transforms or just transforms can appear scary while w

Luis runs rate of 11.7 feet per second how far does he run, Luis runs at a ...

Luis runs at a rate of 11.7 feet per second. How far does he run in 5 seconds? You must multiply 11.7 by 5; 11.7 × 5 = 58.5. To multiply decimals, multiply generally, then coun

Solve by factorization, Solve by factorization X 2 +(a/a+b + a+b/a)x+...

Solve by factorization X 2 +(a/a+b + a+b/a)x+1 = 0 X 2 +(a/a+b + a+b/a)x+1 =>  X 2 +(a/a+b x a+b/ax + a/a+b .a+b/a) =>  X[x+a/a+b] +a+b/a[a+a*a+b]= 0 =>  X= -a

Patrice has worked a certain how many hours has she worked, Patrice has wor...

Patrice has worked a certain amount of hours so far this week. Tomorrow she will work four more hours to finish out the week along with a total of 10 hours. How many hours has she

How long will he have to ride to burn 750 calories, Jeff burns 500 calories...

Jeff burns 500 calories per hour bicycling. How long will he have to ride to burn 750 calories? To find out the number of hours required to burn 750 calories, divide 750 throug

Factoring polynomials with higher degree, Factoring Polynomials with Degree...

Factoring Polynomials with Degree Greater than 2 There is no one method for doing these generally.  However, there are some that we can do so let's take a look at a some exa

Area and Perimeters, The top of the new rectangular Big Gig Thingamajig is ...

The top of the new rectangular Big Gig Thingamajig is 80 inches long and 62 inches wide. What is the top''s perimeter?

Integral calculus, I need help to understand: fxx for f(x,y)=x^2+y^2-2xy

I need help to understand: fxx for f(x,y)=x^2+y^2-2xy

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