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

Compound interest, some experts estimate that the cost of education in the ...

some experts estimate that the cost of education in the US increases by 6% p.a. An Ivy League college currently costs $24,502 for one year''s study today. Using compound interest r

Operations Research inventory , A firm buys a product using the price sched...

A firm buys a product using the price schedule given in the table: The company estimate holding costs at 10% of the purchase price per year and ordering costs at $40 per order .

Solving decimal equations, The distance around a square photograph is 12.8 ...

The distance around a square photograph is 12.8 centimeters. What is the langth of each side of the fotograph?

What is a percentage, Q. What is a percentage? Ans. Percent  mean...

Q. What is a percentage? Ans. Percent  means "per hundred", or "out of 100". A percentage can be written as a ratio, or fraction, where the denominator (bottom) is 100.

What is the minimum number of students, Question 1: What is the minimum...

Question 1: What is the minimum number of students each of whom comes from one of the 50 different states, enrolled in a university to guarantee that there are at least 100 who

The formal algorithm in maths, When do you think you should introduce word ...

When do you think you should introduce word problems-before children master the formal algorithm, or after? What are your reasons for your choice? In any case, no textbook can s

Introduction to technical mathmatic, 81 miles equal how many inches simplif...

81 miles equal how many inches simplify your answer integer od decimal..

Given a differential equation will a solution exist?, All differential equa...

All differential equations will doesn't have solutions thus it's useful to identify ahead of time if there is a solution or not. Why waste our time trying to get something that doe

Estimate the area of this field in terms of x and y, Jonestown High School...

Jonestown High School has a soccer field whose dimensions can be expressed as 7y 2 and 3xy. What is the area of this field in terms of x and y? Since the area of the soccer ?e

Find the area of the remaining part of cardboard, From a sheet of cardboard...

From a sheet of cardboard in the shape of a square of side 14 cm, a piece in the shape of letter B is cut off. The curved side of the letter consists of two equal semicircles & 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