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

SHARES AND DIVIDEND, PLEASE PROVIDE SOME STUFF TO WRITE ON SHARES AND DIVID...

PLEASE PROVIDE SOME STUFF TO WRITE ON SHARES AND DIVIDEND

Linear Equations of Parallel Lines, A line has the equation 2y=-3x+1. Find...

A line has the equation 2y=-3x+1. Find an equation of a line parallel to this line that has a y-intercept of -2.

Utilizes the infinite definition of the limit to prove limit, Utilizes the ...

Utilizes the definition of the limit to prove the given limit. Solution Let M > 0 be any number and we'll have to choose a δ > 0 so that, 1/ x 2   > M

Terminology related to division, Terminology related to division :   A goo...

Terminology related to division :   A good way to remedy this situation is to familiarise children with these concepts in concrete, contexts, to start with. For instance, if a chi

Each child is unique in learning development, Each Child Is Unique :  Alth...

Each Child Is Unique :  Although every child goes through similar stages of development, the process may vary from one set of children to another, and also from one child to anoth

Convert measurements between the english system, Convert measurements betwe...

Convert measurements between the English system? To convert measurements between the English system and the metric system: 1. Look up the conversion between the two units of

Conjugate of the complex number, The conjugate of the complex number a + b ...

The conjugate of the complex number a + b i is the complex number a - b i .  In other terms, it is the original complex number along the sign on the imaginary part changed.  Here

Dynamical system and differential equations, 1. Discuss lyapunov function t...

1. Discuss lyapunov function theory and how it can be used to prove global assmptotic stability of solutions.(Give an example form natural and engineering sciences.) --- Draw le

What is the probability of getting a royal flush, Q. What is the probabilit...

Q. What is the probability of getting a Royal Flush? Ans. Five cards are picked from a standard deck of 52 cards. How many different hands of five cards are possible? What

Product moment coefficient, Product Moment Coefficient This gives an i...

Product Moment Coefficient This gives an indication of the strength of the linear relationship among two variables. Note that this formula can be rearranged to have di

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