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

Integration, It is known that a radioactive material decays at a rate propo...

It is known that a radioactive material decays at a rate proportional to the amount present.If after a period of 12 years,a 2g piece of radium weighs 1.99g.How long will it be befo

Recognize the intervals for function h ( x ) = 3x5 - 5x3 + 3, For the given...

For the given function recognize the intervals where the function is increasing and decreasing and the intervals where the function is concave up & concave down. Utilizes this info

Solving algebraic word problems, Solving Algebraic Word Problems: What...

Solving Algebraic Word Problems: What are the capacities of two water storage tanks in a nuclear facility if one holds 9 gallons less than three times another, and their whole

Alphabet is any arrangement , A word on an alphabet is any arrangement of t...

A word on an alphabet is any arrangement of the letters in the alphabet. For example,ODD, DOD, DOO, DDD are three-letter words on the alphabet {D,O}. How many four-letter words are

Lim.., how can solve limits

how can solve limits

Evaluating a function, Evaluating a Function You evaluate a function by...

Evaluating a Function You evaluate a function by "plugging in a number". For example, to evaluate the function f(x) = 3x 2 + x -5 at x = 10, you plug in a 10 everywhere you

Definite integral, Definite Integral : Given a function f ( x ) which is c...

Definite Integral : Given a function f ( x ) which is continuous on the interval [a,b] we divide the interval in n subintervals of equivalent width, Δx , and from each interval se

Progressions, We will look at three types of progressions called Ar...

We will look at three types of progressions called Arithmetic, Geometric and Harmonic Progression. Before we start looking at the intricacies of these let us unders

Multistage sampling, Multistage sampling Multistage sampling is similar...

Multistage sampling Multistage sampling is similar to stratified sampling except division is done on geographical/location basis, for illustration a country can be divided into

Derivatives for logarithm, Logarithm Functions : Now let's briefly get the...

Logarithm Functions : Now let's briefly get the derivatives for logarithms.  In this case we will have to start with the following fact regarding functions that are inverses of ea

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