|
  |
 MST, Änderung von Kantengewichten. |
|
|
| MST, Änderung von Kantengewichten. |
     |
Es geht um folgendes:
Ich habe einen Graphen G=(E,V) und seinen minimalen Spannbaum T jeweils als Adjazenzliste gegeben.
Jetzt soll ich eine Methode angeben, mit der in O(|E|) der neue Spannbaum erstellt werden kann, wenn die Länge einer Kante w(e) erhöht wird....
Ich muss gestehen ich hab nicht die geringste Ahnung, wie ich da ran gehn soll.
Spontan dachte ich erstmal daran, dass Kruskal den MST ja relativ einfach kosntruiert. Kruskal arbeitet ja auf einer Ordnung der Menge der Kanten, in der Form, dass die Menge der Kanten nach Gewichten geordnet verarbeitet wird. Erst leichteste Kanten, dann schwere (oder kurze und dann lange, wie man will).
Ich bin aber nicht sicher, wie ich von Adjazenzlisten (die ich persönlich so gar net mag, weil ich noch nie mit ihnen gearbeitet habe) zu der Lösung meines Problems komme.
Für einen Ansatz oder ein Tip, der mich in die richtige Richtung treibt, wäre ich sehr dankbar!
__________________
I'm 71% Megatron!
|
|
15.01.2008 16:58 |
|
|
|
|
Angenommen, eine Kante (a,b) wird länger. Muss ich dann nicht einfach nru eine neue Kante suchen, die entweder die Form (...,b) oder (b,...) hat, und die bedingung stellen, dass kein Zyklus entsteht?!
__________________
I'm 71% Megatron!
|
|
|
15.01.2008 17:28 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
 |
|
Versuch es mal mit dieser Idee:
Entfernt man die neugewichtete Kante e aus dem Spannbaum T, zerfällt T-e in zwei knotendisjunkte Teilbäume mit den Knotenmengen V1 und V2.
Sucht man nun die kürzeste Kante e', die jeweils einen inzidenten Knoten in der Menge V1 bzw. V2 hat, ist T-e+e' ein MST unter der neuen Gewichtungsfunktion.
Ob das in O(|E|) geht habe ich mir noch nicht angeschaut.
Übrigens: Man nennt bei einem Graphen die Knotenmenge für gewöhnlich zuerst. Ich gehe trotzdem mal davon aus, dass E die Kanten bei dir sind.
|
|
|
15.01.2008 20:14 |
|
|
|
|
ach sorry, aus irgendeinem grund schreibe ich das AUS PRINZIP falsch herum, war natürlich G = (V,E) gemeint.
Vielen Dank für die Hilfe, das mit den beiden Bäumen kam mir dann auch irgendwann, nach ein bisschen rumspielen und einen tip von noch wem anders.
Vielen Dank!
__________________
I'm 71% Megatron!
|
|
|
16.01.2008 14:08 |
|
|
|
|
Ich habe jetzt ein ähnliches Problem und zwar gehts darum, dass diesmal ein Kantengewicht "verkleinert" wirt. Ich soll eine Methode konstruieren, die in O(|V|) einen neuen MST konstruiert. Ich hab mich mal dran orientiert, dass bei dem Bsp. oben Laufzeit O(|E|) gegeben war und dann die Menge der Kanten durchsucht werden musst ...
Diesmal ist Laufzeit O(|V|) gegeben. Also dachte ich mir spontan schaust DU Dir mal die Knoten an. Wenn eine Kante günstiger wird, dann ist ja im Grunde nur von bedeutung, welche beiden Knoten durch sie verbunden werden. Und ob durch das Senken der Kantenlänge die beiden Knoten günstiger in den MST integriert werden können, als vorher. Alles natürlich untern den Bedingungen von wegen Zyklen und so ...
Ich hatte zuerst überlegt, man könnte ja auch einfach die Lösung von oben anwenden. Dann hab ich mir aber über den Zusammenhang von Knoten und Kanten Gedanken gemacht. Und es sah für mich so aus, dass die maximale Kanten über ne Summenformel irgendwie zusammenhängen, in der Form: menge der kanten ist die summe von i = 1 bis |v| über i ....sehe aber gerade, dass die summe von 1 bis n quadratisch ist, das dann wohl nicht mehr in |E| ist
__________________
I'm 71% Megatron!
|
|
|
17.01.2008 20:52 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Sei uv die Kante, die verkleinert wird.
Nun gibt es zwei Möglichkeiten:
1.) Die Kante uv ist bereits im Spannbaum enthalten. Dann ändert sich der MST natürlich nicht.
2.) Die Kante uv ist im ursprünglichen Spannbaum nicht enthalten. Dann existiert ein eindeutiger Weg von u nach v im MST und durch Hinzunahme von uv entsteht genau ein Zyklus. Aus diesem Zyklus musst du nun die schwerste Kante herausnehmen um wieder einen MST zu erhalten.
|
|
|
17.01.2008 21:55 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
| Zitat: |
| Aus diesem Zyklus musst du nun die schwerste Kante herausnehmen um wieder einen MST zu erhalten. |
|
|
|
18.01.2008 00:29 |
|
|
|
|
sorry, ich hab gepennt ...
1. Irgendwie ist mir das "Zyklus" in dem Satz total entgangen.
2. Mein Beispiel war totaler Käse. die Kante, die dann günstiger wird, würde ohnehin nicht in den MST aufgenommen ... das ist mit genau DANN eingefallen, als ich den PC gerade ausgemacht hatte ...
Jetzt hab ich nur ein Problem mit der Laufzeit. Sicher, dass das in O(|V|)
Ich hab mal versucht GANZ am Anfang meines Studiums Kruskal zu implementieren und bin genau an dem Zyklusding gescheitert.
Wie implementiere ich denn effektiv die Abfrage nach Zyklen!?
__________________
I'm 71% Megatron!
|
|
|
18.01.2008 09:01 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Hier musst du dich daran erinnern, dass der Zyklus durch den eindeutigen Weg von u nach v im bereits vorhandenen MST beschreiben wird, zu dem zusätzlich die Kante uv zugefügt wird. Was du also tun musst, ist den Weg von u nach v im Baum zu finden. Und das ist auf jeden Fall in O(|V|) machbar. Wichtig ist dafür die Erkenntnis, dass für jeden Baum stets gilt: |E| = |V| - 1
|
|
|
18.01.2008 14:09 |
|
|
|
|
AAAAACH klasse. Ich arbeite also eigendlich nur am MST und mache mir da zu nutze, dass eben diese minimale Spannbaum in O(|E|) bearbeitbar ist?!
Müsste ich den Graphen durchsuchen, dann wäre das aufwendiger, oder?!
__________________
I'm 71% Megatron!
|
|
|
18.01.2008 15:24 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Was du ja willst ist der Weg von u nach v im MST. Im Graphen G gibt es evt. mehr als einen Weg von u nach v. Deshalb bringt dir das Suchen dort garnichts .
|
|
|
18.01.2008 15:41 |
|
|
|
|
klasse, ich danke DIr, bist ne riesen hilfe!
__________________
I'm 71% Megatron!
|
|
|
18.01.2008 16:11 |
|
|
|
|
|
|
|
|
