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

Even and odd functions, Even and Odd Functions : This is the final topic ...

Even and Odd Functions : This is the final topic that we have to discuss in this chapter.  Firstly, an even function is any function which satisfies,

Mechanical vibrations, While we first looked at mechanical vibrations we lo...

While we first looked at mechanical vibrations we looked at a particular mass hanging on a spring with the possibility of both a damper or/and external force acting upon the mass.

Determine multiplications required to obtain the determinant, Don't count t...

Don't count the number of divisions. Do not use asymptotic notation, instead provide exact answers. (i) What is the maximum number of multiplications required to solve a system

Determine the critical points, Assume that the amount of money in a bank ac...

Assume that the amount of money in a bank account after t years is specified by, Find out the minimum & maximum amount of money in the account throughout the first 10 years

Working definition of function, A function is an equation for which any x w...

A function is an equation for which any x which can be plugged into the equation will yield accurately one y out of the equation. There it is. i.e. the definition of functions w

Theory of quadratic equations.., solve the following simultaneous equations...

solve the following simultaneous equations x+y=a+b ; a/x_b/y

Elli[ital paths of celestial bodies, Create a detailed diagram to describe ...

Create a detailed diagram to describe the equation of an ellipse in terms of it’s eccentricity and indicate how the foci and major and minor semi-axes are involved. Y

Evaluate following limits at infinity, Evaluate following limits. ...

Evaluate following limits. Solution In this part what we have to note (using Fact 2 above) is that in the limit the exponent of the exponential does this, Henc

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