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

Time & distance., Q4. Assume that the distance that a car runs on one liter...

Q4. Assume that the distance that a car runs on one liter of petrol varies inversely as the square of the speed at which it is driven. It gives a run of 25km per liter at a speed o

Factoring out a common monomial factor, Factoring Out a Common Monomial Fac...

Factoring Out a Common Monomial Factor? Say you have a polynomial, like 3x 4 y - 9x 3 y + 12x 2 y2 z and you want to factor it. Your first step is always to look for t

Introduction To Numerical Methods & Matlab, Can you help me with the course...

Can you help me with the coursework i have in Matlab?

Comercial maths, solve a trader purchases coffee at the rate of Rs. 350 per...

solve a trader purchases coffee at the rate of Rs. 350 per kg and mixes it with chicory bought at the rate of Rs.750 per kg in the ratio 5:2.If he sells the mixture at the rate of

What percentage of the soda purchased was cola, 3/5 of the soda purchased a...

3/5 of the soda purchased at the football game was cola. What percentage of the soda purchased was cola? Change the fraction to a decimal through dividing the numerator through

Scale Drawing, Model of 180 meter tall building using a scale of 1.5 centim...

Model of 180 meter tall building using a scale of 1.5 centimeters = 3.5 meters. How tall will the model be?

Use mathematical induction and prove equation, 1. Use mathematical inductio...

1. Use mathematical induction to prove whenever n is a positive integer. 2. Use loop invariant to prove that the program for computing the sum of 1,...,n is correct.

The new area is 168 square inches how many inches increase, A 4-inch by 6-i...

A 4-inch by 6-inch photograph is going to be enlarged through increasing each side by the similar amount. The new area is 168 square inches. How many inches is each dimension incre

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