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

Vectors, A triangle has vertices A (-1, 3, 4) B (3, -1, 1) and C (5, 1, 1)....

A triangle has vertices A (-1, 3, 4) B (3, -1, 1) and C (5, 1, 1). The area of ABC is a) 30.1 b) 82.1 c) 9.1 d) 52.1

Method for simultaneous equations of two or more variables, Method In ...

Method In this method we eliminate either x or y, get the value of other variable and then substitute that value in either of the original equations to

How many hours will it take for them to be 822 miles apart, Two trains leav...

Two trains leave the same city at the same time, one going east and the other going west. If one train is traveling at 65 mph and the other at 72 mph, how many hours will it take f

I NEED HELP, Teng is designing a house and in each room he can choose from ...

Teng is designing a house and in each room he can choose from tiles, floorboards, or carpet for the floor. a. How many combinations of flooring materials are possible if he designs

Find out primes of each denominator, Find out primes of each denominator: ...

Find out primes of each denominator: Add 1/15 and 7/10 Solution: Step 1:             Find out primes of each denominator. 15 = 5 x 3 10 = 5 x 2 Step 2:

AREA, How do you find the distributive property any faster?

How do you find the distributive property any faster?

Decimals, how to make 2.3 into a fraction?

how to make 2.3 into a fraction?

Show that p ( x ) = 2 x3 - 5x2 -10 x + 5 intermediate value , Example   Sh...

Example   Show that p ( x ) = 2 x 3 - 5x 2 -10 x + 5 has a root somewhere in the interval [-1,2]. Solution What we're actually asking here is whether or not the function wi

Simplify compound fractions, A compound fraction is a fraction that has oth...

A compound fraction is a fraction that has other fractions inside its numerator or denominator. Here's an example: While compound fractions can look really hairy, they're r

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