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

Minimum and maximum values, Minimum and Maximum Values : Several applicati...

Minimum and Maximum Values : Several applications in this chapter will revolve around minimum & maximum values of a function.  Whereas we can all visualize the minimum & maximum v

Multiplication of binomials, To understand the multiplication of binomials,...

To understand the multiplication of binomials, we should know what is meant by Distributive Law of Multiplication. Suppose that we are to multiply (a + b) and m. We

Exponential and geometric model, Exponential and Geometric Model Expo...

Exponential and Geometric Model Exponential model  y = ab x Take log of both sides log y = log a + log b x log y = log a + xlog b Assume log y = Y and log a

What are the average total repair costs per month, An automobile manufactur...

An automobile manufacturer needs to build a data warehouse to store and analyze data about repairs of vehicles. Among other information, the date of repair, properties of the vehic

Trig functions:, Trig Functions: The intent of this section is introducing...

Trig Functions: The intent of this section is introducing you of some of the more important (from a Calculus view point...) topics from a trig class.  One of the most significant

Properties of definite integral, Properties 1.  ∫ b a f ( x ) dx = -∫ ...

Properties 1.  ∫ b a f ( x ) dx = -∫ b a f ( x ) dx .  We can interchange the limits on any definite integral, all that we have to do is tack a minus sign onto the integral

Constructing tables versus rote learning maths, CONSTRUCTING TABLES VERSUS ...

CONSTRUCTING TABLES VERSUS ROTE LEARNING :  Ask any adult how she would help a child to acquire simple multiplication facts. There is a very strong possibility that she would say,

Real exponents, It is a fairly short section.  It's real purpose is to ackn...

It is a fairly short section.  It's real purpose is to acknowledge that the exponent properties work for any exponent.  We've already used them on integer and rational exponents al

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