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

Constructing a dfa/nfa or a regex), Let ∑ = (0, 1). Define the following la...

Let ∑ = (0, 1). Define the following language: L = {x | x contains an equal number of occurrences of 01 and 10} Either prove L is regular (by constructing a DFA/NFA or a rege

Inflation , Inflation The inflation rate for a given period can be ca...

Inflation The inflation rate for a given period can be calculated using the following formula; Inflation = (current retail price index/retail price index in the base year)

Age problem, three years ago,Rica was thrice as old as dandy.Three years he...

three years ago,Rica was thrice as old as dandy.Three years hence,she will be twice as old.Find their present.

Graphing , what effect is the constant in an equation have on an graph

what effect is the constant in an equation have on an graph

Find the function and domain, Consider the function f(x) = x + 1/x 2 + 2x ...

Consider the function f(x) = x + 1/x 2 + 2x - 3. (a) Find f(2) and f(-2). (b) Find the domain of f(x). (c) Does the range include 1? Show your working. (d) Find and si

Determine the angle in hexagonal-shaped nut, The figure provided below show...

The figure provided below shows a hexagonal-shaped nut. What is the measure of ∠ABC?   a. 120° b. 135° c. 108° d. 144° a. The measure of an angle of a regula

FRACTION, HOW TO ADD MIXED FRACTION

HOW TO ADD MIXED FRACTION

Ratio test - sequences and series, Ratio Test In this part we are goin...

Ratio Test In this part we are going to take a look at a test that we can make use to see if a series is absolutely convergent or not.  Remind that if a series is absolutely c

Online tutoring, how can i find the online students ?

how can i find the online students ?

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