Jump to content

Directed Graph-weight

Featured Replies

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)??

Archived

This topic is now archived and is closed to further replies.

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.

Configure browser push notifications

Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.