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

Repeated eigenvalues, It is the last case that we require to take a look at...

It is the last case that we require to take a look at. During this section we are going to look at solutions to the system, x?' = A x? Here the eigenvalues are repeated eigen

Calculate frequencies for two modes of vibration, A partially loaded passen...

A partially loaded passenger car has a mass of 1600 kg.  It has fully independent suspension in which each front spring has a stiffness of 19.0 kNm -1 and each rear spring has a s

Matrices, Ask qudefination of empty matrixestion #Minimum 100 words accepte...

Ask qudefination of empty matrixestion #Minimum 100 words accepted#

Find the angle of elevation, A 50-foot pole casts a shadow on the ground. ...

A 50-foot pole casts a shadow on the ground. a) Express the angle of elevation θ of the sun as a function of the length s of the shadow. (Hint you may wish to draw this firs

Probability, joey asked 30 randomly selected students if they drank milk, j...

joey asked 30 randomly selected students if they drank milk, juice, or bottled water with their lunch. He found that 9 drank milk, 16 drank juice, and 5 drank bottled water. If the

How much is invested at 8% if the total amount of interest, Kevin invested ...

Kevin invested $4,000 in an account which earns 6% interest per year and $x in a different account that earns 8% interest per year. How much is invested at 8% if the total amount o

Concurrent deviation method, Normal 0 false false false ...

Normal 0 false false false EN-IN X-NONE X-NONE

Seqence and seies, If the M-th term of an Ap is n andn-th term M.find the p...

If the M-th term of an Ap is n andn-th term M.find the p-th term

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