Jump to content

Recommended Posts

Posted
Hii!!!

I hope someone can help me with the following exercise...!!!

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<=n-1), 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)??

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.