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

Application of linear equations, Application of Linear Equations We ar...

Application of Linear Equations We are going to talk about applications to linear equations.  Or, put in other terms, now we will start looking at story problems or word probl

Initial recognition of the financial instruments, Grimm plc (Grimm) has the...

Grimm plc (Grimm) has the following transactions: a) On 1 st January 2010, Grimm issued 400,000 convertible £1 6% debentures for £600,000.  The professional fees associated wit

Critical points, Critical Point Definition : We say that x = c is a critic...

Critical Point Definition : We say that x = c is a critical point of function f(x) if f (c) exists & if either of the given are true. f ′ (c ) = 0        OR             f ′ (c

Evaluate relate rate in shape of a cone a tank , In the shape of a cone a t...

In the shape of a cone a tank of water is leaking water at a constant rate of 2 ft 3 /hour .  The base radius of the tank is equal to 5 ft and the height of the tank is 14 ft.

Solve following 4e1+3 x - 9e5-2 x = 0 logarithms, Solve following 4e 1+3 x...

Solve following 4e 1+3 x - 9e 5-2 x  = 0 . Solution Here the first step is to get one exponential on every side & then we'll divide both sides by one of them (that doesn'

Initial condition for differential equations, Initial Condition(s) are a se...

Initial Condition(s) are a set of conditions, or a condition on the solution which will permit us to find out that solution which we are after.  Initial conditions are frequently a

Possible outcome of a coin - probability based question, A coin is tossed t...

A coin is tossed twice and the four possible outcomes are assumed to be equally likely. If A is the event,  both head and tail have appeared , and B be the event at most one tail i

Slope, #question.Find the slope of the line that passes through (7, 3) and ...

#question.Find the slope of the line that passes through (7, 3) and (9, 6). Simplify your answer and write it as a proper fraction, improper fraction, or integer. .

Maths for Social Science, A retired couple has up to $30000 to invest in fi...

A retired couple has up to $30000 to invest in fixed-income securities. Their broker recommends investing in two bonds: one a AAA bond yielding 8%; the other a B+ bond paying 12%.

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