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

Determine the second derivative of q (t ) = sec (5t ), Determine the secon...

Determine the second derivative for following functions.                             Q (t ) = sec (5t ) Solution : Following is the first derivative.              Q′ (t

Proof of the derivative of a constant, Proof of the Derivative of a Constan...

Proof of the Derivative of a Constant : d(c)/dx = 0 It is very easy to prove by using the definition of the derivative therefore define, f(x) = c and the utilize the definiti

Strategic , Hi need a help for marketing strategic assignment Could you ab...

Hi need a help for marketing strategic assignment Could you able to help me???

Precalculus, describe the end behavior of the following function using Limi...

describe the end behavior of the following function using Limit notation f(x)= 2x-1/x-1

How to find the range of a function, How to Find the range of a function ? ...

How to Find the range of a function ? Sigh. Students ask me this all the time. They don't want an explanation, they want a procedure. "Tell me the steps!" Unfortunately, th

Differential equation of newton’s law of cooling , 1. A direction ?eld for...

1. A direction ?eld for a differential equation is shown. Draw, with a ruler, the graphs of the Euler approximations to the solution curve that passes through the origin. Use step

How to join as maths expert, Sir, I am a Maths teacher from kolkata,India....

Sir, I am a Maths teacher from kolkata,India.i want to join your website as Maths'' expert.Please guide me as to how to join your website and earn some money. I will be really grat

Fracrions, how do u do fractions on a nummber line

how do u do fractions on a nummber line

Build a fine automaton which accept all words, Build a Fine Automaton which...

Build a Fine Automaton which accept all words which have different first and last letters (that is if the word starts with an "a" to be accepted it should end with "b" and vice ver

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