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

Determine the angle of depression to a ship, From the top of a 200 m lighth...

From the top of a 200 m lighthouse, the angle of depression to a ship in the ocean is 23 . How far is the ship form the base of the lighthouse?

Evaluate integrals (1 - (1 /w) cos (w - ln w) dw, Evaluate following integr...

Evaluate following integrals.                       ( (1 - (1 /w) cos (w - ln w) dw Solution In this case we know how to integrate only a cosine therefore let's makes th

Real number, if HCFof 657 and 963 is expressable in the form of 657x+963x-1...

if HCFof 657 and 963 is expressable in the form of 657x+963x-15findx

Logarithmic functions, If x = b y where both b > 0, x > 0, then we d...

If x = b y where both b > 0, x > 0, then we define y = log b x, which is read as "y is the log to the base b of x". This means that, log b x or y is the number to

The sum of two integers is 36 what is the smaller number, The sum of two in...

The sum of two integers is 36, and the difference is 6. What is the smaller of the two numbers? Let x = the ?rst integer and let y = the second integer. The equation for the su

Yield volatility and graph, This question has two related parts, (a) and (b...

This question has two related parts, (a) and (b). (a) Use the daily yields in the table below to compute a daily standard deviation of yields. Next annualize the daily standard

Permutations and combinations, Consider this. You have four units A, ...

Consider this. You have four units A, B, C and D. You are asked to select two out of these four units. How do you go about this particular task? Will your methodo

Relation is not a function, The following relation is not a function.   ...

The following relation is not a function.                   {(6,10) ( -7, 3)  (0, 4)  (6, -4)} Solution Don't worry regarding where this relation came from.  It is only on

Geometry, how do you do rotations

how do you do rotations

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