0 Daumen
861 Aufrufe

Sei G=(V,E) ein gerichteter, gewichteter Graph mit Kantengewicht w(u,v)∈R für jede Kante (u,v)∈E. Sei ferner f eine Funktion, die jedem Knoten v∈V eine Zahl f(v)∈R zuordnet und sei G′ der Graph, der die gleichen Knoten und Kanten, wie G enthält und in dem jede Kante (u,v)∈E das Gewicht w′(u,v)=w(u,v)+f(u)−f(v) erhält.

Wie könnte ich das zeigen?

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

Hallo Gucki,

v, w zwei Knoten und \( v \to p_1 \to \dotsm \to p_n \to w \) der kürzeste Pfad zwischen v und w. Sei \( v \to q_1 \to \dotsm \to q_m \to w \) ein anderer Pfad. Mit \( v = p_0 = q_0 \) und \( w = p_{n+1} = q_{m+1} \) ist

$$ \sum_{i=0}^n w(p_i, p_{i+1}) \le \sum_{i=0}^m w(q_i, q_{i+1}) $$

nach der Definition des kürzesten Pfads. Teleskopsumme:

$$ \sum_{i=0}^n w'(p_i, p_{i+1}) = \sum_{i=0}^n \left( w(p_i, p_{i+1}) + f(p_i) - f(p_{i+1}) \right) = f(p_0) - f(p_{n+1}) + \sum_{i=0}^n w(p_i, p_{i+1}) $$

Analog:

$$ \sum_{i=0}^m w'(q_i, q_{i+1}) = f(q_0) - f(q_{m+1}) + \sum_{i=0}^m w(q_i, q_{i+1}) $$

Da \( f(p_0) = f(v) = f(q_0) \) und \( f(p_{n+1}) = f(w) = f(q_{m+1}) \) folgt

$$ \sum_{i=0}^n w'(p_i, p_{i+1}) \le \sum_{i=0}^m w'(q_i, q_{i+1}) $$

Somit bleibt der kürzeste Pfad in G auch der kürzeste Pfad in G'.

Avatar von 6,0 k

"Die Distanzen können sich sehr wohl verändern" stand auch noch dabei. Wie soll ich das verstehen?

Damit ist wohl gemeint, dass sich die Distanz zwischen v und w in beiden Graphen unterscheiden kann. Nimm z.B.

~draw~ ;dreieck(-2|-2 2|-2 0|2)#;punkt(-2|-2 "A");punkt(2|-2 "B");punkt(0|2 "C");zoom(3);aus ~draw~

mit den Gewichten w(A,B)=1, w(B,C)=1, w(A,C) = 10. Dann ist der kürzeste Pfad von A nach C ja wohl A -> B -> C mit einem Pfadgewicht von 2=1+1.

Jetzt setze f(A) = 0, f(B) = 3, f(C) = -20. Dann ist im neuen Graph G' immer noch A -> B -> C der kürzeste Pfad, aber jetzt ist

w'(A,B) = 1 + 0 - 3 = -2

w'(B,C) = 1 + 3 - (-20) = 24

und hat damit hat der Pfad ein Gesamtgewicht von 22.

Danke für deine detaillierte Antwort, aber es könnte doch sein das der Weg von w(a,c) kürzer ist, weil eben andere Gewichtung. Ist mit Distanz das Gwicht gemeint oder die Anzahl der Kanten? Verwirrt mich.

Mit Distanz ist in diesem Fall sicherlich die summierte Gewichtung gemeint.

In diesem Fall ist w(A,C) ≥ w(A,B) + w(B,C) und deshalb ist auch w'(A,C) ≥ w'(A,B) + w'(B,C) wie ich oben in meiner Antwort gezeigt habe. also ist stets A->B->C der kürzeste Pfad.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community