Hallo,
ich habe noch ein paar Fragen zu (Netz-)Flussproblemen und Graphalgorithmen.
-
In einem Graph kann eine Kante auch negative Kosten haben (was ja dann bei negativen Zyklen zu bestimmten Problemen führen kann). Soweit ok. Aber ich hab nirgends gefunden wie überhaupt negative Kosten für eine Kante entstehen können oder beschrieben sind. Natürlich sind das theoretische Modelle, aber irgendwie möchte ich mir das auch vorstellen können !??!
-
Es wird ein sogenanntes Potential eines Knotens definiert. Und zwar ist das "eine Abbildung pi : V -> R . Also wird jedem Knoten eine Zahl pi(i) zugewiesen, das Potential von i ".
hmm… natürlich kann ich einfach jedem Knoten mal eben ne Zahl zuweisen, aber welche ? warum ? Wie kann ich dass mit einfachen Worten beschreiben ?
(oder ist dass einfach „nur so“ gewählt dann man sich folgende Defintion „bauen“ kann ?)
-> Definition : Reduzierte Kosten einer Kante(i,j)
c^pi (i,j) = c (i,j) - pi(i) + pi(j)
Also in Worten : Red. Kosten der Kante i,j ist gleich der Kosten von (i,j) minus des Potentials von i plus dem Potential von j .
Schön und gut, aber was genau steckt hinter dieser Defintion?
Was genau sagt mir das Potential ?
Und wo liegt dann genau der Unterschied von einem Pot. in einem Graphen/Netzwerk und einem Pot. in einem Restnetzerk.
- Was ist der Hintergrund/Sinn vom Union-Find(-Problem)? Ich verstehe zwar was die Operationen Union und Find machen (können), aber nicht wirklich was das wirklich soll ?
Denke da gehts dann wohl einfach um eine Realisierung einer bestimmten Datenstruktur. Oder wie kann man dies am besten mit Worten beschreiben ?
Hoffe es kann jemand ein wenig helfen!
Danke vorab.
Grüße