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

Standard basis vectors - calculus, Standard Basis Vectors The vector th...

Standard Basis Vectors The vector that is, i = (1, 0,0) is called a standard basis vector.  In three dimensional (3D) space there are three standard basis vectors, i → = (1

Cylindrical coordinate system, how to describe the locus of the equation x^...

how to describe the locus of the equation x^2+6xy+y^2+z^2=1 in cylindrical polar coordinates?

Evaluate the circumference of circle, If the diameter of a circle is triple...

If the diameter of a circle is tripled times, the circumference is a. multiplied by 3. b. multiplied by 6. c. multiplied by 9. d. multiplied by 12. a. The formula fo

Shares and dividend, want to make an assignment on shares and dividend for ...

want to make an assignment on shares and dividend for class 10

Photogrammetry, basic linear algebra concepts and calculations in photogram...

basic linear algebra concepts and calculations in photogrammetry

1, what''s the beneit of study mathematics ?

what''s the beneit of study mathematics ?

Introduction to learning to count, INTRODUCTION : Most of us, when plannin...

INTRODUCTION : Most of us, when planning the first mathematical experience for three-year olds, think in terms of helping them memorise numbers from 1 to 20. We also teach them to

Domain and range of a function , Domain and range of a functio:  One of th...

Domain and range of a functio:  One of the more significant ideas regarding functions is that of the domain and range of a function. In simplest world the domain of function is th

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