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

Finite math, Find the present value of an ordinary annuity which has paymen...

Find the present value of an ordinary annuity which has payments of 2300 per year for 15 years at 6% compounded annually

How high is a structure, One method of calculating the height of an object ...

One method of calculating the height of an object is to place a mirror on the ground and then position yourself so that the top of the object will be seen in the mirror. How high i

Describe real numbers, Q. Describe Real numbers? Ans. There are a ...

Q. Describe Real numbers? Ans. There are a few different ways to describe real numbers. Without going into any of the very technical definitions used by mathematicians, I'

Polynomials, zeroes of polynomial 2x2-3x-2

zeroes of polynomial 2x2-3x-2

Math, the size of my sitting room is 7metres by 6metres . i bought a rug fo...

the size of my sitting room is 7metres by 6metres . i bought a rug for covering the centre of its floor. one metre of the floor around the edge of the room is not to be covered by

Utilizes second derivative test to classify critical point, Utilizes the se...

Utilizes the second derivative test to classify the critical points of the function,                                               h ( x ) = 3x 5 - 5x 3 + 3 Solution T

Guess my number, My thousandths digit is twice the tenths digit. My tenths ...

My thousandths digit is twice the tenths digit. My tenths digit is one less than the hundredths digit. If my number is 5, what my number?

Probability distribution for continuous random variables, Probability Distr...

Probability Distribution for Continuous Random Variables In a continuous distribution, the variable can take any value within a specified range, e.g. 2.21 or 1.64 compared to

Integerts, how do u add and subtract integers

how do u add and subtract integers

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