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

Do yall, do yall help kids in 6th grade

do yall help kids in 6th grade

Find out if the sets of vectors are parallel or not, Determine or find out ...

Determine or find out if the sets of vectors are parallel or not. (a) a → = (2,-4,1), b = (-6, 12 , -3) (b) a → = (4,10), b = (2,9) Solution (a) These two vectors

How much did donald earn in commissions last month, Donald sold $5,250 wort...

Donald sold $5,250 worth of latest insurance policies last month. If he receives a commission of 7% on new policies, how much did Donald earn in commissions last month? To ?nd

Find x if one ball is drawn at random from the box, A box contains 12 balls...

A box contains 12 balls out of which x are black .if one ball is drawn at random from the box  what is the probability that it will be a black ball ? If 6 more black balls are   pu

Theorem of reduction of order, In this theorem we identify that for a speci...

In this theorem we identify that for a specified differential equation a set of fundamental solutions will exist. Consider the differential equation  y′′ + p (t ) y′ + q (t

Gravity, There is a list of the forces which will act on the object. Gr...

There is a list of the forces which will act on the object. Gravity, F g The force because of gravity will always act on the object of course. Such force is F g   = mg

Break even point, what is break even point and how can it helps managers to...

what is break even point and how can it helps managers to make decisions?

Sin[cot-1{cos(tan-1x)}], sin (cot -1 {cos (tan -1 x)}) tan -1 x = A  ...

sin (cot -1 {cos (tan -1 x)}) tan -1 x = A  => tan A =x sec A = √(1+x 2 ) ==>  cos A = 1/√(1+x 2 )    so   A =  cos -1 (1/√(1+x 2 )) sin (cot -1 {cos (tan -1 x)}) = s

Question, Hi I have a maths question related to construction as its a cons...

Hi I have a maths question related to construction as its a construction management course...i could send some example sheets too...could it be done?

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