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

Find the probability , 1.  What is the probability that the two beverages w...

1.  What is the probability that the two beverages will be of the same kind? 2.  What is the probability that the two beverages will be different? 3.  What is the probability

What is the maximum amount of hours cindy worked together, Carl worked thre...

Carl worked three more than twice as many hours as Cindy did. What is the maximum amount of hours Cindy worked if together they worked 48 hours at most? Let x = the amount of h

Find and classify the differential equation, Find and classify the equilibr...

Find and classify the equilibrium solutions of the subsequent differential equation. y' = y 2 - y - 6 Solution The equilibrium solutions are to such differential equati

How many cousins does robert have- miscellaneous math, Bonnie has twice as ...

Bonnie has twice as many cousins as Robert. George has 5 cousins, which is 11 less than Bonnie has. How many cousins does Robert have? Work backwards to find the solution. Geor

The fisher’s index, The Fisher's index The index of Fisher acts as a c...

The Fisher's index The index of Fisher acts as a compromise between Paasche' index and Laspeyre's index. This is calculated as a geometric mean of the two indexes.

Decision trees illustration, A company is considering whether to enter a ve...

A company is considering whether to enter a very competitive market. In case company decided to enter in market this must either install a new forging process or pay overtime wages

Divergence test - sequences and series, Divergence Test Once again...

Divergence Test Once again, do NOT misuse this test.  This test only says that a series is definite to diverge if the series terms do not go to zero in the limit.  If the

Transpose of a matrix, I didn't understand the concept of Transpose of a Ma...

I didn't understand the concept of Transpose of a Matrix, need assistance.

Subjective probability, Subjective Probability Probability may be de...

Subjective Probability Probability may be determined by a personal statement of how likely an outcome is in a single trial or repetition of the same experiment. Since sub

Brad class collected 320 cans of food how many did required, Brad's class c...

Brad's class collected 320 cans of food. They boxed them in boxes of 40 cans each. How many boxes did they required? To find the number of boxes required, you should divide the

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