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

Rectilinear figure, In a parallelogram ABCD AB=20cm and AD=12cm.The bisecto...

In a parallelogram ABCD AB=20cm and AD=12cm.The bisector of angle A meets DC at E and BC produced at F.Find the length of CF.

Calculate latest triangular area sail for his boat, Rick is order a latest ...

Rick is order a latest triangular sail for his boat. He needs knowing the area of the sail. Which formula will he use? The area of a triangle is 1/2 times the length of the bas

Trigonmetry, How do I find a bearring using trig?

How do I find a bearring using trig?

The formal algorithm in maths, When do you think you should introduce word ...

When do you think you should introduce word problems-before children master the formal algorithm, or after? What are your reasons for your choice? In any case, no textbook can s

Pair of st line, #qu Given the equation through what angle should the axes...

#qu Given the equation through what angle should the axes be rotated so that the term in xy be waiting from the transformed equation. estion..

Example of integration strategy - integration techniques, Evaluate the subs...

Evaluate the subsequent integral. ∫ (tan x/sec 4 x / sec 4 x)  dx Solution This kind of integral approximately falls into the form given in 3c.  It is a quotient of ta

Partial derivatives - set theory, Partial Derivatives Partial derivati...

Partial Derivatives Partial derivatives are used while we want to investigate the effect of one independent variable on dependent variable. For illustration, the revenues of a

Implicit - explicit solution, It's easier to describe an explicit solution,...

It's easier to describe an explicit solution, in this case and then tell you what an implicit solution is not, and after that provide you an illustration to demonstrate you the dif

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