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

Example on abels theorem, Without solving, find out the Wronskian of two so...

Without solving, find out the Wronskian of two solutions to the subsequent differential equation. t 4 y'' - 2t 3 y' - t 8 y = 0 Solution : First thing that we want to d

Help, draw a right angle isosceles triangle with 9 triangles in it

draw a right angle isosceles triangle with 9 triangles in it

Theorem to computer the integral, Use green's theorem to computer the integ...

Use green's theorem to computer the integral F . dr where F = ( y^2 + x, y^2 + y) and c is bounded below the curve y= - cos(x),, above by y = sin(x) to the left by x=0 and to the r

gauss elimination method , Question: Use  Gauss elimination method to ...

Question: Use  Gauss elimination method to solve the following system of equations.  -y +3z=4  2x-y-2z= 2  2x-2y+z =6  4x-y-7z= 0

What is the expected value of perfect information, Question: The follow...

Question: The following payoff table shows profit for a decision analysis problem with two decision alternatives and three states of nature. (a) Construct a decision tr

What percentage of the soda purchased was cola, 3/5 of the soda purchased a...

3/5 of the soda purchased at the football game was cola. What percentage of the soda purchased was cola? Change the fraction to a decimal through dividing the numerator through

Marketig research report , need help to write Marketing research reprot abo...

need help to write Marketing research reprot about IBM company using spss (statistical program) to analys the given data about the company and write the report according to given i

Functions and graphs, Functions and Graphs Need assistance, Please de...

Functions and Graphs Need assistance, Please describe Functions and Graphs.

Describe the types of triangles, Describe the Types of triangles ? Tria...

Describe the Types of triangles ? Triangles can be classified according to the lengths of the sides or the measures of the angles. 1. Naming triangles by sides An

What is the maximum number calories which consume from fats, Josephine is o...

Josephine is on an 1,800 calorie per day diet. She tries to remain her intake of fat to no more than 30% of her overall calories. Based on an 1,800 calorie a day diet, what is the

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