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

Describe vibration absorber and white noise, Describe what is meant by eac...

Describe what is meant by each of the following NVH terms and explain their importance in vehicle refinement: (a)  Vibration absorber (b)  Fast Fourier Transform (c)  Whit

Technical Mathematic, Convert or Reduce Reduce 4,500 micrograms to grams

Convert or Reduce Reduce 4,500 micrograms to grams

Summation notation, SUMMATION NOTATION Under this section we require to...

SUMMATION NOTATION Under this section we require to do a brief review of summation notation or sigma notation.  We will start out with two integers, n and m, along with n a

What did she pay per pound, Mona purchased one and a half pounds of turkey ...

Mona purchased one and a half pounds of turkey at the deli for $6.90. What did she pay per pound? Divide the cost of the turkey by the weight; $6.90 ÷ 1.5 = $4.60.

Adding integers, Do you subtract when you add integers.

Do you subtract when you add integers.

Find out the surface area of the solid, Find out the surface area of the so...

Find out the surface area of the solid acquired by rotating y = √ (9-x 2 ), - 2 x 2 about the x-axis. Solution The formula that we'll be using here is, S = ∫ 2Πyds

Michael has 16 cds how many cds does kathleen have, Michael has 16 CDs. Th...

Michael has 16 CDs. This is four more than twice the amount that Kathleen has. How many CDs does Kathleen have? Let x = the number of CDs Kathleen has. Four more than twice th

Equilibrium solutions, In the earlier section we modeled a population depen...

In the earlier section we modeled a population depends on the assumption that the growth rate would be a constant. Though, in reality it doesn't make much sense. Obviously a popula

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