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

Additionally functions in substitution rule, Substitution Rule Mostly ...

Substitution Rule Mostly integrals are fairly simple and most of the substitutions are quite simple. The problems arise in correctly getting the integral set up for the substi

Harold used a 3% iodine solution and a 20% iodine solution, Harold used a 3...

Harold used a 3% iodine solution and a 20% iodine solution to make a 95- ounce solution in which was 19% iodine. How many ounces of the 3% iodine solution did he use? Let x = t

1 application of complex analysis in THERMODYNAMICS, Hi, this is EBADULLA ...

Hi, this is EBADULLA its about math assignment. 1 application of complex analysis used in thermodynamics. . what all uses are there in that... plz let mee know this answer.

Find integer if consecutive even integers is the number 126, The sum of two...

The sum of two consecutive even integers is the number 126. What are the integers? Two consecutive even integers are numbers in sequence, such as 4 and 6 or -30 and -32, that a

Proof of root test - sequences and series, Proof of Root Test  Firstly...

Proof of Root Test  Firstly note that we can suppose without loss of generality that the series will initiate at n = 1 as we've done for all our series test proofs.  As well n

lmc, what is the concept of lm

what is the concept of lmc

Find the average, The center of a national park is located at (0,0). A spec...

The center of a national park is located at (0,0). A special nature preserve is bounded by by straight lines connecting the points A at (3,2), B at (5,1), C at (8,4) and D at (6,5)

Solve the initial value by laplace transform method, Question: Solve the i...

Question: Solve the initial value problem 2x'' +x'-x =27 Cos2t +6 Sin 2t, x(0)=2 , x'(0)= -2 by using Laplace transform method.

Example of inflection point-differential equation, Example of inflection po...

Example of inflection point Determine the points of inflection on the curve of the function y = x 3 Solution The only possible inflexion points will happen where

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