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

Focal chord of the parabola, show that the circle described on any focal c...

show that the circle described on any focal chord of the parabola touches the directrix

Applied Math, Calucations of gradients find f Graph some level curve f=cons...

Calucations of gradients find f Graph some level curve f=const. f=9x^2 = 4y^2

How much sales tax did she pay if items was 6 percent, Lindsay purchased a ...

Lindsay purchased a pocketbook for $45 and a pair of shoes for $55. The sales tax on the items was 6%. How much sales tax did she pay? Find out the price of the two items toget

Rewriting percent expressions, i have trouble going through problem in this...

i have trouble going through problem in this lesson. Markdown and Markups are theh ones im stuck in

Arc length - applications of integrals, Arc Length - Applications of integr...

Arc Length - Applications of integrals In this part we are going to look at determining the arc length of a function.  As it's sufficiently easy to derive the formulas that we'

What is combination formula, Q. What is Combination Formula? Ans. ...

Q. What is Combination Formula? Ans. The difference between combinations and permutations is that permutations take ordering into consideration, whereas combinations do no

Explain polynomials, P OLYNOMIALS : It is  not  once  nor  twice  b...

P OLYNOMIALS : It is  not  once  nor  twice  but  times  without  number  that the  same ideas make  their  appearance in the  world. 1.  Find the value for K for which

Saddle point-game theory, Saddle Point This point in a pay off matrix i...

Saddle Point This point in a pay off matrix is one which is the largest value in its column and the smallest value in its row. This is also termed as equilibrium point in the t

Calculate the equation, Problem1: Find the general solution on -π/2 Dy/...

Problem1: Find the general solution on -π/2 Dy/dx +(tan x)y =(sin 2 x)y 4

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