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

Process for solving linear equations, 1. If the equation has any fractions ...

1. If the equation has any fractions employ the least common denominator to apparent the fractions. We will do this through multiplying both sides of the equation by the LCD. Al

Estimate how long did michael practice- algebra, Suppose that the number of...

Suppose that the number of hours Katie spent practicing soccer is represented through x. Michael practiced 4 hours more than 2 times the number of hours that Katie practiced. How l

What is the new price of the coat, An $80.00 coat is marked down 20%. It do...

An $80.00 coat is marked down 20%. It does not sell, so the shop owner marks it down an additional 15%. What is the new price of the coat? Find out 20 percent of the original p

Assignment Help, I would like to work on Assignment help in Mathematics

I would like to work on Assignment help in Mathematics

Markup & markdown, if prices are calculatead with a 35% markup based on cos...

if prices are calculatead with a 35% markup based on cost,what is the percent that those prices should be marked down to get back to their original cost?Choose any convenient cost

Multiplying fractions involving negative numbers, Q. Multiplying Fractions ...

Q. Multiplying Fractions Involving Negative Numbers? Ans. If you have only one negative sign, the result is still negative: If you have more than one, just remembe

Taylor series, If f(x) is an infinitely differentiable function so the Tayl...

If f(x) is an infinitely differentiable function so the Taylor Series of f(x) about x=x 0 is, Recall that, f (0) (x) = f(x) f (n) (x) = nth derivative of f(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