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

Complex numbers, Complex Numbers In the radicals section we noted that...

Complex Numbers In the radicals section we noted that we won't get a real number out of a square root of a negative number.  For example √-9 isn't a real number as there is no

Describe graphing equations with a positive slope, Describe Graphing Equati...

Describe Graphing Equations with a Positive Slope? There are 3 steps to graphing a linear equation: 1. Identify and plot the y-intercept. 2. Determine the slope. Use the slope

Algebra, (x+15)/y=10 where y=5

(x+15)/y=10 where y=5

Function, f(x)=x^2-5x+6, determine inverse of f(x)!

f(x)=x^2-5x+6, determine inverse of f(x)!

Finding the side of a triangle only using equations, In triangle DEF, angle...

In triangle DEF, angle E is congruent to angle F. If side DE = 3x-6, Side EF = x+2 and Side DF = 18-5x. Find the length of side DE

Derivatives, Derivatives The rate of change in the value of a...

Derivatives The rate of change in the value of a function is useful to study the behavior of a function. This change in y for a unit change in x is

Reduction formulae, Reduction formulae Script for Introduction: ...

Reduction formulae Script for Introduction: First let us know what is meant by reduction formula. In simple words,                 A formula which expressess(or re

Define markov chain, Define Markov chain Random processes with Markov ...

Define Markov chain Random processes with Markov property which takes separate values, whether t is discrete or continuous, are known as Markov chains.

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