
June 9th, 2013, 04:46 AM
#1
Directed Graphweight
Hi!!!
I'm facing some difficulties with the following exercise...I hope someone can help me!!!
Let G=(V,E) be a directed graph with weight w: E>R, n=V.
Let m( c )=1/k*sum(w(e_{i}), i=1,k) be the mean weight of a circle.
Let m*=min(m( c )), the minimum of the mean weights of the circles of G.
Is it correct to say that, since the minimum of the mean weight is 0 and not negative, there are no circles with negative weight? Or is there an other explanation that if m*=0 there are no circles with negative weight..???
And also, how could I explain that δ(s,v)=min(δ_{k}(s,v), o<=k<=n1), where δ(s,v) is the weight of the lightest path from s to v, and δ_{k}(s,v) is the weight of the lightest path from s to v that contains exactly k vertices (when there is no path from s to v with k vertices δ_{k}(s,v)=infinity)??
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
