Relationship between the shortest path distances - tree, Mathematics

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.

Posted Date: 3/22/2013 3:59:36 AM | Location : United States







Related Discussions:- Relationship between the shortest path distances - tree, Assignment Help, Ask Question on Relationship between the shortest path distances - tree, Get Answer, Expert's Help, Relationship between the shortest path distances - tree Discussions

Write discussion on Relationship between the shortest path distances - tree
Your posts are moderated
Related Questions
Ask if tanA+sinA=m and m^2-n^2=4 rute mn show that tanA-sinA=n

Assume E is the event that a randomly generated bit string of length 4 starts with a 1 and F is the event that this bit string consists of an even number of 1's. Are E and F indepe

Hypothesis Testing Of The Difference Between Proportions Illustration Ken industrial producer have manufacture a perfume termed as "fianchetto." In order to test its popul

A small square is located inside a bigger square. The length of the small square is 3 in. The length of the large square is 7m. What is the area of the big square if you take out t


Product Moment Coefficient (r) This gives an indication of the strength of the linear relationship among two variables.                                     N

Extrema : Note as well that while we say an "open interval around x = c " we mean that we can discover some interval ( a, b ) , not involving the endpoints, such that a Also,


Ask quHarvesting prevents the population size of a species from attaining its natural carrying capacity. We can add harvesting to the logistic model by assuming that the per capita

X-intercept  If an intercept crosses the x-axis we will call it as x-intercept .  Y-intercept Similar, if an intercept crosses the y-axis we will call it as a y-inter