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

Fermats theorem, Fermat's Theorem  If f(x) has a relative extrema at x...

Fermat's Theorem  If f(x) has a relative extrema at x = c and f′(c) exists then x = c is a critical point of f(x). Actually, this will be a critical point that f′(c) =0.

Percent of a number, Pay $40 for plan offered for $30 for plan what percent...

Pay $40 for plan offered for $30 for plan what percentage of savings

Probability, Mike sells on the average 15 newspapers per week (Monday – Fri...

Mike sells on the average 15 newspapers per week (Monday – Friday). Find the probability that 2.1 In a given week he will sell all the newspapers

Trigonometry, if theta is a positive acute angle and 2sin theta +15cos squ...

if theta is a positive acute angle and 2sin theta +15cos square theta=7 then find the value of cot theta

Fiancial project, With your current loan, explain how much additional money...

With your current loan, explain how much additional money you would need to add to your monthly payment to pay off your loan in 20 years instead of 25. Decide whether or not it wou

Trigonometry, what are reason inside a circle?

what are reason inside a circle?

MATLAB, Program of "surface of revolution" in MATLAB

Program of "surface of revolution" in MATLAB

Exponential functions, The exponential functions are useful for descr...

The exponential functions are useful for describing compound interest and growth. The exponential function is defined as:          y = m. a x where '

Line with rise of five and run of two is positive, Draw a graph which has s...

Draw a graph which has slope of a line with rise of five and run of two is positive.

Number theory, formula for non negative solutions integral

formula for non negative solutions integral

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