---

Geschrieben von marie m am 09.06.2013 um 12:40:

  Frage->Gerichteter Graph

Hallooo!!!!!
Ich habe mal wieder eine Frage...
Gegeben sei ein gerichteter Graph G = (V, E) mit Gewicht w: E-> R, n = | V |.
m (c) = 1 / k * Summe (w (e_ {i}), i = 1, k) ist das Durchschnittsgewicht eines Kreises.
m * = min (m (c)),ist das Minimum der Durchschnittsgewichte der Kreise von Graph G.
Ist es richtig zu sagen, dass, da das Minimum des Durchschnittsgewichte 0 ist und nicht negativ ist, gibt es keine Kreise mit negativem Gewicht? Oder gibt es eine andere Erklärung, dass, wenn m * = 0 gibt es keine Kreise mit negativem Gewicht ..??
Und, wie könnte ich erklären, dass ´ (s, v) = min (´_ {k}(s, v), o <= k <= n-1), wobei ´ (s, v) ist das Gewicht des leichtesten Weges von s zu v und ´_ {k} (s, v) das Gewicht der leichtesten Weges von s zu v, der genau k Ecken enthält (wenn es keinen Weg von s zu v mit k Ecken gibt ist ´_ {k} (s, v) = unendlich)?